10. 탐색구조

- 최악의 경우에도 insert, search, delete가 O(log n)을 유지

10.2 AVL tree

- 정의 : Binary tree + label

- 각각의 node에 left, right label 표기

-left label : 왼쪽 subtree의 depth

-right label : 오른쪽 subtree의 depth

- left label과 right label이 2 이상 차이가 안 나게 유지.

(항상 같거나 1 차이.)

-Search : binary search tree와 동일. O(log n)

-Insert : binary search tree Insert + Tree 보정 ( label 조건을 만족시키기 위함)

-일단 insert를 시키고 난 후, search한 PATH를 따라 올라가다가 최초로 조건을 만족시키지 않는 node에서 Rotation.

 *Rotation

-LL, LR, RL, RR

-LL의 경우: 최초로 조건을 만족시키지 않는 node를 right child로 만들고, 그 자리에 left child를 올림.

 left child의 right child는 원래 root node의 left child로 바꿈.

 RR의 경우 좌우 대칭

-LR의 경우 : 최초로 조건을 만족시키지 않는 node를 right child로 만들고, 그 자리에 left child의 right child를 올림.

 root로 올린 node의 left child는 원래 자리의 parent에 붙이고, right child는 원래의 root node에 붙임.

 - Rotiation을 진행 하더라도 기본적인 크기 관계가 변하면 안 됨.

10.3   2-3 tree

- 정의 : 각 node에 키가 1개 혹은 2개, 따라서 각 node의 child가 2개 혹은 3개. 모든 leaf는 같은 level.

- search : O(log n)

- insert : search를 한 후에, leaf에 빈자리가 있으면 그냥 insert, 빈자리가 없으면 leaf를 split해서 중간값을 parent로 올려보내고 반복.

10.4   2-3-4 tree

- 각 node에 키가 1개 혹은 2개 혹은 3개.

- 나머지는 2-3 tree와 같으나 insert를 할 때, split을 하면서 내려오게 할 수 있다.-> tree를 한번 내려오면 insert가 끝남.

10.5 Red-Black tree

- 2-3-4 tree의 변형

- 2-3-4 tree를 binary tree형태로 표현.

- child node로 가는 link를 black으로, 같은 node에 있는 키로 가는 link를 red로 표시.

-특징 : root에서 leaf까지 black link의 수는 항상 동일, 어떤 path에서도 red link가 연속으로 등장하지 않는다.

-insert 과정은 AVL tree의 Rotation과 같다.

- AVL, 2-3, 2-3-4, Red-Black tree를 통틀어 Balanced tree라 부른다.

 * Skip list

- head와 tail이 더미 노드인 링크드 리스트가 층으로 쌓여있는 자료구조

- 모든 동작이 O(log n)에 된다.