#AVL 트리에 대해서 설명해주세요

AVL 트리는 이진 탐색 트리의 단점을 보완한 이진 탐색 트리이다

이진 탐색 트리가 효율적이기 위해서는 균형이 잡혀있어야한다

 

1. 이진 탐색 트리의 속성을 가진다

2. 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다

3. 높이 차이가 1보다 커지면 회전(Rotation)을 통해 균형을 맞춰 높이 차이를 줄인다

4. 삽입, 검색, 삭제의 시간 복잡도가 O(log N)이다(N: 노드의 개수)

 

AVL 트리는 회전 과정을 통해 균형을 잡는다

 

균형이 무너졌는지 판단하기 위해서 Balance Factor 라는 것을 활용한다

BF(K) = K의 왼쪽 서브트리의 높이 - K의 오른쪽 서브트리의 높이

 

우회전(Right Rotation)

1. y노드의 오른쪽 자식 노드를 z노드로 변경한다.
2. z노드 왼쪽 자식 노드를 y노드의 오른쪽 서브트리(T2)로 변경한다.

 

좌회전(Left Rotation)

1. y노드의 왼쪽 자식 노드를 z노드로 변경한다.
2. z노드 오른쪽 자식노드를 y노드의 왼쪽 서브트리(T2)로 변경한다.