3. AVL 트리의 RL회전, LR회전

1. RL회전

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

발생한다.

RL회전은 균형 트리를 만들기 위해서 2번의 회전이 필요하다.

LL회전을 한 다음에, RR회전을 하면 된다.

아래 [ 그림 2 ]과 같이 AVL 트리의 노드 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 새로운 노드를 추가하면 비균형 트리가 되고, 이를 바로 잡기 위해서는 LL회전과 RR회전의 2번의 회전이 필요하다.

 

아래의 그림과 같이 트리가 있다고 하자.

[ 그림 1 ]

위의 트리에서 데이터의 삽입이 이루어졌다고 가정하자.

 

그러면 아래의 그림이 된다.

[ 그림 2 ] 

위에서 데이터의 삽입이 이루어짐과 동시에 균형 트리를 맞춰야 한다.

먼저, LL회전 시키면, 아래의 그림이 된다.

그리고, RR회전 시키자.

 

 

2. LR회전

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

발생한다.

LR회전은 균형 트리를 만들기 위하여 2번의 회전이 필요하다.

RR회전을 한 다음, LL회전을 하면 된다.

아래와 같이 균형 트리가 하나 있다고 가정하자.

위의 균형트리에 데이터가 삽입이 되었다고 가정하자.

 

데이터가 삽입된 이후의 트리는 아래와 같다.

위의 트리에서 RR회전 하면 아래와 같은 트리가 된다.

그리고 위의 트리에서 다시 LL회전 하면 아래와 같은 트리가 된다.

 

 

3. RL회전, LR회전 알고리즘

 

4. RL회전, LR회전의 함수

(1). RL회전 함수

(2). LR회전 함수