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