균형을 유지하는 AVL-Tree

정의

AVL Tree(Adelson-Velsky and Landis 만든 사람 이름)

 

* 이진탐색 트리의 일종이기 때문에  이진탐색 트리의 특성을 모두 만족한다.

 

- 스스로 균형을 잡는 데이터 구조 중 처음으로 발명되었다.

- AVL 트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이만 난다.

- 삽입, 삭제 시점에 특정 노드를 기준으로 양쪽의 두 서브 트리의 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 균형을 잡는다.

 

검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(log n)의 시간복잡도가 걸린다.

삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있다

 

이진트리에서 데이터가 아래와 같이 한쪽으로 편향되어서 저장이 된다면, O(n) 시간복잡도가 걸린다. 

이것을 해결하기 위해 나온 트리이다. 

 

이진트리의 불균형을 해소하는 방법

데이터 삽입 또는 삭제후 균형이 잡힌상태(모든 노드에서 높이차가 2이상 나지 않음)인지 확인한다.

 

1. LL(Left, Left) 방향으로 트리가 편향된 상태

 

노드(3)을 기준으로 왼쪽으로 높이가 2가 높아지는 편향된 상태이다.

 

중간 노드(2)를 기준으로 오른쪽 방향으로 트리를 회전시킨다,

중간노드(2)가 부모가 되고 노드(3)이 노드(2)의 자식이 된다. 부모,자식관계가 역전 되는데 이때 참조하는 방향을 잘 바꾸어준다. 

2. LR(Left, Right) 방향으로 트리가 편향된 상태

 

노드(3)을 기준으로 왼쪽으로 높이가 2가 높아지는 편향된 상태이다.

 

중간 노드(1)를 기준으로 왼쪽 방향으로 트리를 회전시킨다.

노드(1), 노드(2) 부모 자식 관계 참조를 바꾸고, 노드(3) 왼쪽자식을 노드(2)로 바꾸어 준다.

이후, LL편향 상태가 되며 1번의 해결방법으로 해결하면 된다.

 

3. RR(Right, Right) 방향으로 트리가 편향된 상태

 

노드(1)을 기준으로 오른쪽으로 높이가 2가 높아지는 편향된 상태이다. 

 

중간 노드(2)를 기준으로 왼쪽 방향으로 트리를 회전시킨다,

중간노드(2)가 부모가 되고 노드(1)이 노드(2) 자식이 된다. 부모,자식관계가 역전 되는데 이때 참조하는 방향을 잘 바꾸어준다. 

4.  RL(Right, Left) 방향으로 트리가 편향된 상태

 

아래 예시를 보면, 노드(1)을 기준으로 오른쪽으로 높이가 2가 높아지는 편향된 상태이다. 

 

중간 노드(3)를 기준으로 오른쪽 방향으로 트리를 회전시킨다.

노드(3), 노드(2) 부모 자식 관계 참조를 바꾸고, 노드(1) 오른쪽 자식을 노드(2)로 바꾸어 준다.

이후, RR편향 상태가 되며 3번의 해결방법으로 해결하면 된다.

시간 복잡도

 

* 이진탐색트리의 편향되는 점을 개선하긴 했지만 삽입 및 삭제시 높이 차이를 계산하고,

불균형이 나타났다면, 이를 해소하기 위한 비용이 들어간다.