AVL

 

AVL은 균형 잡힌 이진트리 종류 중 하나 입니다.

이진트리의 종류는 대략적으로 다음과 같습니다

- AVL

- 2-3 트리

- 2-3-4 트리

- Red-Black 트리

- B 트리

 

 

자동으로 균형을 잡는 AVL 트리와 균형 인수(Balance Factor)

 

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

 

균형 인수를 통해서 해당 트리의 균형을 잡기 위한 척도를 잡을 수 있다.

AVL트리는 균형 인수의 절대값이 2 이상인 경우에 균형을 잡기 위한 트리의 재조정을 진행한다.

 

 

이 그림과 반대로 오른쪽 트리의 깊이가 3이고 왼쪽 트리의 깊이가 1라면

균형 인수는 -2일것이다.

 

 

AVL 트리의 균형이 무너지는 상태(= 이를 리밸런싱이 필요한 상황이라한다. )를

바로잡는 회전은 4가지로 정리가 된다.

 

 

1. LL회전
2. RR회전
3. LR 회전
4. RL 회전

 

LL회전

 

LL 회전이 필요한 경우는?

자식 노드 두 개가 왼쪽으로 연이어 연결되어서 균형 인수 +2가 연출되는 경우

 

균형 인수가 +2가 연출된 이 상태를 가리켜 'Left Left' 상태라고 한다.

이러한 LL상태를 해소하는 것이 LL회전이라고 한다.

 

LL회전이란?

LL상태에서 균형을 잡기 위해 필요한 회전을 의미하는 것이다.

 

1) 자식노드가 없는 경우

 

해당 부분을 함수로 틀만 만들고자 하면 다음과 같이 표현할 수 있다.

ChagneRightSubTree(cNode, pNode);

 

 

2) 자식노드가 있는 경우

 

 

위 그림에서 보이듯이 cNode가 가리키는 노드의 오른쪽 서브 트리를

pNode가 가리키는 노드의 왼쪽 서브 트리로 옮기기 위한 함수는 다음과 같이

대략적으로 만들어 놓을 수 있다.

 

ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
ChangeRightSubTree(cNode, pNode);

 

 

RR회전

 

LL회전과 유일한 차이점은 방향에 있다.

LL회전은

왼쪽으로 길게 늘어진 트리를 회전시키는 것이라면(LL상태에서 균형을 맞춰주는 것)

RR회전은

오른쪽으로 길게 늘어진 트리를 회전시키는 것(RR상태에서 균형을 맞춰주는 것)

 

 

위 그림에서 주목할 것은 다음 두 가지이다.

 

• 5가 저장된 노드가 7이 저장된 노드의 왼쪽 자식 노드가 되었다.
• T3는 5가 저장된 노드의 오른쪽 서브 트리가 되었다.

 

이 둘을 코드화하면 다음과 같다.

ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
ChangeLeftSubTree(cNode, pNode);

 

 

LR회전

 

LR회전은 자식노드가 왼쪽으로 하나 그리고 이어서 오른쪽으로 하나 달린 상태에서

균형을 잡기 위한 회전을 뜻한다.

 

LR 상태 해결 방안

 

1) LR상태를 한 번의 회전으로 균형이 잡히는 LL상태나 RR상태로 일단 바꾼다.

 

즉, LR상태는 RR회전을 통해서 LL회전이 되게 할 수 있다.

RR회전을 하면 부모 노드와 자식 노드의 관계가 바뀐다.

더불어서 오른쪽으로 형성된 부모와 자식의 관계가 왼쪽으로 바뀐다.

 

이를 그림으로 표현하면 다음과 같다.