Binary Search Tree (이진탐색트리 )

이진탐색트리

정의

• 이진탐색(binary search)과 연결리스트(linked list)를 결합한 자료구조

  이진탐색 : 탐색에 소요되는 시간복잡도는 O(logN), but 삽입, 삭제가 불가능
  연결리스트 : 삽입, 삭제의 시간복잡도는 O(1), but 탐색하는 시간복잡도가 O(N)

이 두가지의 장점을 합하여 만든 것
즉, 효율적인 탐색 능력을 가지고, 자료의 삽입•삭제도 가능하게 만드는 것

특징

• 각 노드의 자식이 2개 이하
• 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼
• 왼쪽•오른쪽 서브트리 또한 이진탐색트리이다.
• 중복 노드가 없어야 함

  중복 노드가 없어야 하는 이유는?
  검색 목적 자료구조인데, 굳이 중복이 많은 경우에 트리를 사용하여 검색 속도를 느리게 할 필요가 없음.
  (트리에 삽입하는 것보다, 노드에 count 값을 가지게 하여 처리하는 것이 훨씬 효율적)

순회 방식

• 이진탐색트리를 순회할 때는 중위순회(왼쪽 - root - 오른쪽) 방식을 사용합니다.
• 중위 순회로 정렬된 순서를 읽을 수 있음

중위 순회 : 1 → 3 → 5 → 7 → 8 → 10

BST 핵심 연산

검색

• 부모노드가 왼쪽 자식노드보다 크거나 같고, 오른쪽 자식노드보다 작거나 같다는 점에 착안하여 효율적인 검색이 가능합니다.

삽입

• 트리의 중간에 새 데이터를 삽입하게 되면 서브트리의 속성이 깨질 수 있다.
• 그러므로, 삽입 연산은 반드시 잎새노드에서 이뤄지게 됩니다.

삭제

• 1. 자식노드가 없는 경우
  해당 노드를 그냥 없애기만 하면 됩니다.
  

• 2. 자식노드가 하나 있는 경우
  해당 노드를 지우고, 해당 노드의 자식노드와 부모노드를 연결해주면 됩니다.
  

• 3. 자식노드가 두 개 있는 경우
  1. 삭제 대상 노드의 오른쪽 서브트리를 찾는다.

  2. successor(1에서 찾은 서브트리의 최소값) 노드를 찾는다.
  3. 2에서 찾는 successor의 값을 삭제 대상 노드에 복사한다.
  4. successor 노드를 삭제한다.
     

트리 생성
트리 삭제

시간 복잡도

• 균등 트리 : 노드 개수가 N개일 때 O(logN)
• 편향 트리 : 노드 개수가 N개일 때 O(N)

  삽입, 검색, 삭제 시간복잡도는 트리의 Depth에 비례