기말 준비 - 균형 검색 트리 (Balanced Search Tree)

종류

 1. AVL Tree (트리에서 설명함)

 

 

 2. B-Tree ( Bayer & McCreight , 1972 )

  이진트리, 2-3트리, 2-3-4트리 등을 일반화 시킨 트리로, 현재까지도 계속 알고리즘이 업그레이드 되고 있음.

 

  2-1. 정의

   모든 노드가 좌에서 우로갈수록 증가하는 k개의 데이터를 가짐. ( 이때, 데이터의 개수 k는 n의 절반 이상, n 이하 )

    - n = 1, (0 <= K <= 1) : 이진트리

    - n = 2, (1 <= K <= 2) : 2-3 트리

    - n = 3, (1 <= K <= 3) : 2-3-4 트리

  노드의 자식의 수가 아니라, 노드가 보유한 데이터의 수.

 

 2-2. 특징

  1) 일반적인 이진검색트리(BST)의 향상된 형태이다.

  2) 자동으로 균형을 맞추기 때문에, 최악의 경우에도 검색/삽입/삭제에서 O(lg N)의 속도를 가짐

  3) Rotation으로 재균형하는 AVL, Red-Black Tree보다 효율적임.

  4) Slow Memory(HDD, SSD 같은거)에 최적화 되어짐.

  5) 이름의 유래는 몰?루 (제작자들이 설명안해줌)

  

 

3. 2-3 트리 ( Hopcraft, 1970 )

 Slow memory에 최적화 된 검색트리로, B-Tree로 일반화 된 트리이다.

 

 3-1) 정의

  B-Tree에서 n=2인 형태로, 각 노드는 1~2개의 원소를 갖고, 그 수에 따라 자식노드는 2~3개가 된다.

  노드의 원소는 Left <= Right이고, 노드의 자식도 Left <= Mid <= Right 이다.

  이때 자식 Mid는 부모의 Left와 Right의 사잇값이다. L<=PL<=M<=PR<=R

  삽입/삭제 후에도 모든 단말노드는 동일한 레벨을 유지한다. [자동 균형]

 

 3-2) 삽입 (Insert)

  data K는 일반적인 트리처럼 비교하면서 단말 노드에 추가된다.

  이 때, 추가된 노드 X의 원소가 3개 이상이 되면 Overflow 함수를 호출해 균형을 맞춘다.

  Overflow 함수

   1. 노드 X의 부모 Parent가 null 인 경우 [ 노드 X가 root임. ] Empty root를 새로 만들어 X의 Parent로 둔다.

   2. X의 원소중 가운데 값을 Parent로 올리고, Left값을 Parent.Left, Right값을 Parent.Right. Parent의 자식으로 만든다.

만약 이 과정 중 새로운 원소가 3개인 노드가 생겼다면, 그 노드를 대상으로 overflow를 다시 실행한다. (재귀적 진행)

35를 추가해서 {25,30,35}가 된걸 Overflow햇더니 그 Parent가 3개가 되서 또 Overflow를 진행..

 

 3-2) 삭제 (Delete)

  지울 데이터 K가 속한 노드는 X라고 함.

  노드 X가 비-단말 노드인 경우, K의 후속자 노드 Y를 찾고, X와 Y의 위치를 바꾼 후, K를 삭제함.

  K 삭제 후 노드 X의 원소가 0개가 되면 Underflow를 실행 해 균형을 맞춤.

  Underflow 함수

   1. 노드 X의 부모 Parent가 null 이면 [ 노드 X는 root ], root를 노드의 자식으로 바꾼다.

   2. 노드 X의 형제 Brother의 원소가 2개이면 [ Parent의 X말고 다른 자식이 형제가 됨 ], 회전을 통해 균형을 맞춘다.

    -> 노드 X가 Parent.Right라면, Brother의 데이터중 큰쪽이 Parent data가 되고, 기존 Parent data가 X의 데이터로 됨.

 3. 노드 X의 형제 Brother의 원소가 1개라면, Brother와 Parent의 data를 병합한 뒤, 하나의 노드로 만든다.

 

Delete 진행의 예시

 1.

 14 -> {11}, {13} 에서 13이 제거된 상태

  1. Brother의 원소가 1개이므로, Parent와 합해서 {11,14}가 된다. 그러므로, Parent가 Empty node가 됨.

  2. Delete(Parent)를 진행해서, 원소가 2개인 Brother {17,20}에서 작은쪽인 17을 받아오기로 한다.

  3. 회전을 통해, Parent에 17을 넣고, 중간값인 15를 아래로 가져온다.

  4. 기존 {17,20}의 자식이던 16을 가져와서 15의 자식으로 넣어 단말노드의 level을 맞춘다.

 

2.

 ex)옆의 노드에서 11을 삭제함.

  1. Brother의 원소가 1개이므로, Parent와 합해서 {13,14}가 된다. Parent가 Empty node가 됨.

  2. Delete(Parent)를 했는데, 이번에도 Brother의 원소가 1개이므로, 합쳐서 {5,10}이 되고, Parent.Parent가 Empty node가 됨.

  3. Delete(Parent.Parent)를 했는데, root노드임. 그래서 자식을 root로 만들고 종료.

 

 

4. Red-Black 트리 ( Guibas & Sedgewick, 1978 )

- Self balancing BST로 실제 사용에 효율적임.

 

4-1) 정의

 Balanced BST중에 하나로, 삽입/삭제 후 Rotation으로 균형을 맞춘다.

 모든 node는 Red or Black의 색을 가진다. (Node에 Color bit가 추가됨)

 Root 노드부터 각 단말노드 까지의 black node 개수는 항상 동일하다. (Black Height)

 모든 단말노드는 data가 없는 가상의 노드(NIL)로서 데이터 노드에 부착된다.

   -> (실제로는 한 NIL을 모두가 공유하는 방식으로 구현된다.)

 Root와 단말노드(NIL)은 Black이며, Red의 자식은 항상 Black이다.

 

4-2) 삽입(Insert)

 노드 X를 색을 Red로 지정한 후, 일반적인 BST의 방식으로 삽입한다.

 삽입이 완료되면 노드 X에 black NIL을 2개 부착한다.

 만약 노드 X의 부모가 Black이면 정상 종료,

 노드 X의 부모가 Red이면 균형 유지를 위한 수정을 해야함.

  -> 수업시간 부족으로 진행되지 않음.