Binary Search Tree

Binary Tree + 특정한 룰

예시

BST에서 어떤 값이 존재하는지 확인하기 위해서는, 트리의 최대 깊이만큼만 탐색해서 찾을 수 있다.

N개의 노드가 밸런싱되어 꽉찬 경우에도 시간복잡도는 O(logN)이 소요된다.

이미 정렬된 배열이라도 사실 Binary Search 가 가능하다.

1 2 5 7 9 10

하지만 배열은 삽입/삭제 등은 기존에 저장된 데이터를 밀어내는 과정이 추가로 필요하므로 O(N)의 시간복잡도를 가지게 된다.

BST는 삽입/삭제 역시 평균적으로 O(logN)만에 수행할 수 있기 때문에 효과적이다.

삭제의 경우가 조금 신경써야 할 부분이 있다. 삭제가 되었을때도 BST의 형태를 유지해야 한다.

자식이 없는 경우 - 삭제할 대상을 NULL로 변경하기만 하면 된다. ¹

  50         50
 /  \   ->  /  \
30  70    NULL 70

자식이 하나만 있는 경우 - 삭제하려는 노드의 자식들을 부모의 자식으로 연결한다.

    50                    50
   /  \                  /  \
  30  70 (30 제거) ->   40   70
 /
40

자식이 둘 다 있는 경우 - 삭제하려는 대상의 오른쪽 자식에서 가장 작은 값으로 대체한다.

  50                  70
 /  \                /  \
30  80  (50 제거) -> 30  80
   /  \                   \
  70  90                  90

극단적으로는 다음과 같은 형태도 BST에 속한다.

1
 \
  2
   \ 
    3...

트리의 깊이가 계속해서 깊어져 검색 효율이 좋지 못할 수 있다. 이를 방지하기 위해 밸런스를 알아서 잡는 트리들이 존재한다. 이들은 검색도 항상 O(logN)의 시간복잡도를 보장하게 된다.

balance factor라는 것을 통해 스스로 균형을 유지한다. balance factor란 어떠한 노드의 왼쪽 서브트리와 오른쪽 서브트리의 값 차이를 말한다.

모든 노드의 balance factor가 {-1, 0, 1}을 충족할 때 AVL Tree가 된다. 밸런스 팩터 체크는 트리의 삽입 혹은 삭제 후 균형을 맞추는 작업을 진행하게 된다.

50           
 \          70
  70  ->   /  \
   \      50  90
    90

balance factor 동작 시 AVL Tree를 만족하면서도 BST를 만족해야 한다. 예를 들어 오른쪽-왼쪽으로 꺾인 트리의 경우는 다음 과정을 통해 균형을 맞추게 된다.

50      50       
 \       \          60
 70 ->   60  ->    /  \
 /        \       50  70
60        70

AVL Tree는 밸런스를 스스로 잡게 되므로, 기존 BST 최악의 경우 O(N)의 시간복잡도를 O(logN)으로 개선한다. 다만 밸런스 팩터 동작 과정에서 루트 노드까지 탐색을 하는 과정이 있어 이러한 시간이 걸리는 것도 고려해야 한다.

root 노드 black부터 시작하여 black의 자식은 red, 그 자식은 다시 black 번갈아가면서 트리 형태를 유지하는 BST의 일종이다. NULL 대신 nil 노드를 사용한다는 특징이 있다.

red-black tree

모든 노드가 red/black으로 구성된다.
루트 노드는 항상 black으로 구성된다.
모든 leaf 노드는 null 대신 nil 노드라는 개념을 사용한다. nil 노드는 항상 블랙이고 red/black 노드와 동등하게 취급한다.
red의 자식은 black이다. 그리고 red가 연속적으로 존재할 수 없다.
임의의 노드에서 nil 노드까지 가는 모든 경로의 black의 개수는 같다. (노드 x의 모든 nil 노드까지의 경로는 black height가 모두 같다.)

삽입/삭제 시 Red-Black Tree의 특성을 위반할 경우 트리 구조를 재조정한다.

삽입하는 노드의 색은 항상 Red이다. RBT의 black height 특성을 유지하기 위해서이다.

삽입 후에 RBT의 형태를 유지하고 있는지 체크한다. 삽입 시 발생하는 RBT 위반 케이스는 크게 3가지로 나뉘며, 이에 따라 다르게 트리가 조정된다.

BST 삭제와 동일하게 동작한다. 이후 RBT의 속성을 위반했는지 체크하고, 일치하지 않다면 다시 재조정을 진행한다.

삭제의 경우 어떤 색이 삭제되는가가 속성 위반 여부를 판단하는데에 중요하다.

삭제되는 색이 Red일 경우 어떠한 속성도 위반하지 않는다.

다만 삭제하려는 색이 Black일 경우, 임시로 extra black이라는 것으로 black으로 취급 후 재조정을 진행한다.(자세한 내용은 중략…) ³