2. AVL 트리의 LL회전, RR회전

시작 하기에 앞서, AVL 트리의 구현에

이진 탐색 트리의 모든 헤더 파일과 소스 파일이 필요

지금부터 만드는 모든 함수들은 AVLTree헤더 파일과 AVLTree 소스 파일에 정의함.

 

1. LL회전

아래 [그림 1]의 LL타입의 경우 6,5,2순으로 노드를 삽입했을 경우에 만들어 진다.

노드6은 균형인수가 2로서 불균형하다.

그러나 오른쪽으로 회전을 시키면 다시 균형 트리를 만들 수 있다.

 

[그림 1 : LL 타입 ]

[그림 2 : LL 회전 결과 ]

 

LL회전을 보다 일반적인 경우로 정리해보자.​

LL타입은 조상 노드A의 왼쪽 서브 트리의 왼쪽 서브 트리에 노드가 추가됨으로 해서

발생한다.

아래의 그림을 보자.

LL회전은 노드들을 오른쪽으로 회전시키면 된다.

회전을 시키면 아래와 같다.

 

2. RR회전

아래[ 그림 1]은 왼쪽 회전의 경우로 6,8,9 순으로 노드를 삽입했을 경우에 만들어진다.

마찬가지로 트리를 왼쪽으로 한 번 회전하면 균형 트리로 만들 수 있다.

여기서 회전한다는 의미는 루트와 자식 노드를 바꾼다는 것이다.

[그림 1 : RR 타입 ]

[그림 2 : RR 회전 결과 ]

 

RR회전을 보다 일반적인 경우로 정리하여 보자.

위에서 RR타입은

조상 노드A의 오른쪽 서브 트리의 오른쪽 서브 트리에 노드가 추가됨으로 해서 발생한다.

아래의 그림을 보자.

일반적인 경우의 RR타입은 노드A와 B의 위치를 바꾸어 주고 서브 트리들을 정리하면

균형 트리로 만들 수 있다. 아래의 그림을 보자.

 

3. LL회전과 RR회전의 알고리즘

(1). LL 회전

(2). RR회전

4. LL회전과 RR회전의 구현

(1). LL회전

(2). RR회전