탐색(Search) 2

이진 탐색 트리의 문제점 : 이진 탐색 트리의 연산은 O(log2 n)의 시간 복잡도를 가진다. 그런데 균형이 맞지 않을수록 O(n)에 가까운 시간 복잡도를 보인다.

이러한 이진  탐색 트리의 단점을 해결한 트리를 가리켜 균형 잡힌 이진 트리라 하며, 그 종류 중 AVL 트리를 선택한다.

 

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

LL회전 : LL상태 : 균형 인수 +2가 연출된 상태. 

RR회전 : RR상태 : 균형 인수 -2가 연출된 상태. 

LR회전 : LR상태 : 자식 노드가 왼쪽으로 하나, 그리고 이어서 오른쪽으로 하나 달린 상태. RR회전을 통해 LL상태로 

RL회전 : RL상태 : 자식 노드가 오른족으로 하나, 그리고 이어서 왼족으로 하나 달린 상태. LL회전을 통해 RR상태로