자료 구조 - Chapter 12

탐색의 이해2

이진 트리의 단점

저장 순서에 따라 탬색의 성능에 큰 차이를 보인다.

따라서 이러한 단점을 해결한 트리를 가리켜 '균형 잡힌 이진트리'라고 한다.

• AVL 트리
• 2 - 3 트리
• 2 - 3 - 4 트리
• Red - Black 트리
• B 트리

 

AVL 트리 (AVL Tree)

AVL 트리는 G.M.Adelson-Velskii와 E.M.Landis에 의해 고안되었다.

AVL트리는 토드가 추가될 때, 그리고 삭제될 때 트리의 균형 상태를 파악해서 스스로 그 구조를 변경하여

균형을 잡는다. 

 

균형 인수(Balance Factor)

AVL 트리가 균형을 잡기 위해 지표로 사용하는 것

균형 인수 = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이

AVL 트리는 균형 인수의 절대값이 2 이상인 경우에 균형을 잡기 위한 트리의 재조정을 진행한다.

 

리밸런싱(Rebalancing)

• LL 회전
• LR 회전
• RL 회전
• RR 회전

 

RL 및 RR회전의 경우 한번의 회전을 통해 LL 또는 RR 상태로 바꾸어 접근하면 해결하기 편리하다.

 

예제 : AVL트리 구현하기

기존에 제작한 BinarySearchTree에 Rebalance함수를 추가하여 자료를 삽입하고 삭제할 때 마다

트리의 균형에 신경쓴다.

 

AVL 트리 구현하기

AVLRebalance.c

0.00MB

AVLRebalance.h

0.00MB

BinarySearchTree3.c

0.00MB

BinarySearchTree3.h

0.00MB

BinaryTree3.c

0.00MB

BinaryTree3.h

0.00MB

ex12 AVLTree.c

0.00MB