[자료구조] 이진탐색, Splay, AVL, BB트리

1. 이진 탐색 트리

-이진 탐색트리 :== 트리에서 특정 데이터의 효과적인 검색을 위해 제한점을 가지는 이진트리

-특정 데이터를 검색하고, 노드를 삽입/삭제하는 응용 문제에 가장 효과적인 트리

-탐색에 최적화된 이진 트리

-키: 이진 트리 노드의 데이터

 

이진 탐색 트리의 특징

 

- 왼쪽 서브트리에 있는 모든 노드의 자식 키값은 작다.

- 반대로 서브트리에 있는 모든 노드의 자식 키값은 크다.

 

왼쪽은 이진 탐색트리이고, 오른쪽은 이진 탐색 트리가 아니다.

이진 탐색 트리의 단점

 

- BS 트리의 성능은 트리의 구조와 특정 노드에 접근할 확률에 영향을 받음

- 트리의 성능이 구조에 영향을 받기 때문에 최적의 BS 트리구조를 결정하기 어려움

 

좋은 성능의 BS 트리를 구축하는 방법(휴리스틱)

 

- 자주 탐색하는 키를 가진 노드를 트리의 루트에 가깝게 놓는다.

- 트리가 균형이 되도록 유지한다. 즉, 각 노드에 대해 왼쪽과 오른쪽 서브트리가 가능한 한 같은 수의 노드를 갖게 한다.

 

2. Splay 트리

 

-Splay트리 :== 자주 탐색하는 키를 가진 노드를 루트에 가깝게 위치하도록 구성한 BS트리

-휴리스틱 알고리즘을 사용

- 이 트리는 Splay 연산을 적용하여 최근에 접근한 노드를 루트에 위치시켜 트리를 재구성한다.

 

Splay 트리의 연산

Zig

Zig-Zag

- zig: p가 트리의 루트면 p와 x의 간선 연결을 회전시킨다.

- zig-zag: p가 루트가 아니고 x와 p가 동일하게 왼쪽 자식들 또는 오른쪽 자식들이면 p와 조부모 g와의 간선 연결을 회전시키고 그 다음에 x와 p의 간선 연결을 회전시킨다.

 

3. AVL 트리

 

- 제한 조건을 완화하여 트리가 균형이 아닌 것을 허용함

- 무너진 균형의 정도는 작아야함, 평균 탐색 길이도 완전 균형 트리의 탐색 길이와 크게 차이가 나지 않아야 함

- 거의 완전한 균형 트리의 한 형태로 높이가 균형잡힌 높이 균형 트리

-직접 탐색 성능이 매우 좋음

 

AVL 트리의 조건

 

-AVL 조건: 노드의 왼쪽 서브트리 높이와 오른쪽 서브트리 높이가 최대 1만큼 차이가 남

 

AVL 조건에 위배된 트리의 예시

4. BB트리

 

- BB 트리 :== 거의 완전히(대략) 균형 잡힌 트리의 다른 종류로 무게가 균형잡힌 트리

- 각 노드의 양쪽 서브트리 무게가 균형을 유지하는 트리

 

균형 트리

 

-AVL 또는 BB 트리에 대하여 각각 무게 또는 크기 제한 조건을 만족시키는데 드는 비용은 트리를 완전히 균형 잡히게 유지하는 비용이나 노력보다 훨씬 작음

- 삽입이나 삭제 후에 트리를 완전히 균형 잡히게 유지하기 위해서는 O(n)의 노드를 옮겨야 하는 반면에 AVL 또는 BB 트리는 O(log2n) 개의 노드를 옮기면 되는 것으로 알려져 있음