이진 탐색 트리

이진 탐색 트리(Binary Search Tree)는 다음과 같은 속성을 가진다.

    1. 노드의 왼쪽 서브 트리는 노드의 값보다 작은 값으로 이루어진다.

    2. 노드의 오른쪽 서브 트리는 노드의 값보다 큰 값으로 이루어진다.

    3. 노드의 좌우 서브 트리는 모두 이진 탐색 트리여야 한다.

    4. 중복되는 노드가 없어야 한다.

이진 탐색 트리의 시간 복잡도는 최악일 경우 O(n)이며 최선일 경우 O(log n)이다.

 

최악의 경우

        5
       /
      4
     /
    3
   /
  2
 /
1

최선의 경우

     10
   /   ＼
  5     15
 / ＼   / ＼
2   7 12  17

 

삽입

    1. 검색을 수행한다.

    2. 검색 중 중복되는 노드가 있는지 확인

    3. 검색 중 하위 노드에 노드가 없는 경우 노드를 삽입

 

삭제

삭제하려는 노드의 자식 수에 따라 방식이 달라진다.

    1. 자식 노드가 없는 경우 노드를 삭제한다.

    2. 자식 노드가 1개인 경우 노드를 삭제하고 그 위치에 자식 노드를 대입하고 기존의 자식 노드는 제거한다.

    3. 자식 노드가 2개인 경우 삭제하고자 하는 노드의 왼쪽 서브 트리에서 가장 큰 값으로 변경하거나, 오른쪽 서브 트리에서 가장 작은 값으로 변경한 뒤 기존에 서브 트리에 있던 노드는 제거한다. (제거되는 노드에 자식 노드가 있으면 다시 정리가 필요하며 정상적인 트리의 모습이 될 때까지 반복한다.)