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

이진 탐색 트리

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

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

탐색에 최적화된 이진 트리

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

같은 순서 데이터에 대해 BS 트리를 다양하게 만들 수 있음

 

BS 트리 연산

SPLAY 트리 : 편향된 이진트리

BB 트리, AVL 트리 : 루트를 중심으로 균형된 이진트리 (탐색을 위한)

 

 

 

SPLAY 트리

휴리스틱 알고리즘을 사용 (경험적 알고리즘)

자주 탐색하는 키를 가진 노드를 트리의 루트에 가깝게 위치하도록 구성

Splay 연산 : Zig, Zag, Zig-Zag

Zig: 찾는 것이 트리의 루트 노드이면 간선 연결을 회전

Zig-Zag : 루트가 아니고 왼쪽/오른쪽 자식들이면 조부모와의 간선 연결을 회전

 

AVL 트리

균형을 잡는 트리

균형을 위해서는 많은 트리가 이동해야함

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

 

BB 트리

거의 완전히 균형 잡힌 트리의 다른 종류로 무게가 균형 잡힌 트리 (무게 : 서브트리의 개수)

 

---

	정답 4
	정답 3