AVL트리(Adelson-Velskii / Landis)

http://blog.naver.com/tlstmdrb8862/70163870063

AVL트리란? 

- 항상 균형을 유지하는 이진트리

- 어느 노드 기준으로 좌측 또는 우측 자식 노드의 트리가 불균형하게 상대적으로 너무 길거나, 잛은 형태의 트리구조를 같은 길이의 형태로 변환 시켜주는 알고리즘을 가지고 있는 트리

 

특징

- 모든 노드의 서브트리 높이 차이가 1이하이다. 만약 높이 차이가 2이상이 된다면 노드들은 스스로 재배치하여 균형 상태를 유지 해야 한다.

- 탐색은 이진트리 탐색과 동일하다.

 

장점

- 탐색속도가 빠르다

- 트리 전체를 재배열시키지도 않아도 트리의 균형이 유지된다.

 

AVL트리의 균형이 깨지는 경우

- 트리의 균형은 노드를 삽입하거나 삭제할 때 깨질 수 있다.

삽입,삭제 연산을 할 경우 근접한 노드 뿐 아니라 루트까지의 경로에 있는 노드에도 영향을 줄 수 있다. 만약 그 영향으로 균형차가 2이상 되는 노드가 생긴다면 그 노드의 서브트리들을 회전 하여 트리의 균형을 잡는다.

 

( N은 삽입된 노드, A는 N에서 가장 가까운 균형 인수 2이상이 된 노드 )

 

LL 타입

- A의 균형인수가 2가 된다. LL( A의 Left자식의 Left자식)에 삽입 되면서 문제가 발생한 경우

해결방법

- B의 오른쪽 자식을 A의 왼쪽 자식으로 연결해준 후, B의 오른쪽 자식을 A로 바꿔준다.

 

RR 타입

- RR( A의 Right자식의 Right자식)에 삽입 되면서 문제가 발생한 경우다.

해결 방법

- LL과 반대로 B의 왼쪽 자식을 A의 오른쪽 자식으로 연결해주고, B의 왼쪽 자식을 A로 연결합니다.

 

LR 타입

- LR( A의 Left자식의 Right자식)에 삽입 되면서 문제가 발생한 경우다.

해결방법

-  처음에 노드를 Left(시계반대)방향로 회전으로 하여 정렬된후 Right(시계)방향으로 또 한번 회전하혀 정렬한다.

 

RL 타입

- RL( A의 Right자식의 Left자식 )에 삽입 되면서 문제가 발생한 경우다.

해결방법

- LR의 반대로 처음에 노드를 Right(시계)방향로 회전으로 하여 정렬된후 Left(시계반대)방향으로 또 한번 회전하혀 정렬한다.

 

참고 URL

http://girlsy7.tistory.com/134

http://blog.naver.com/ellay06?Redirect=Log&logNo=120171026944

[출처] [자료구조] AVL( Adelson-Velskii / Landis )트리 |작성자 ㅋing