AVL 이진트리(개념설명)

이진 탐색트리가 자동으로 균형을 잡을 수 있도록 개선된것이

AVL 트리

 

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

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

 

LL회전

자식 노드 두개가 왼쪽으로 연이어 연결되어 부모의 균형인수가 2가 되는 것

    3

  2

1

이런경우를 말하고..LL회전을 거치면

   2

1     3

이렇게 된다. 2를 중심으로 오른쪽으로 3이 돌면됨..

RR은 그와 반대로..

3

   2

      1

RR회전을 거치면

   2

3     1

이런식으로 된다.

LR과 RL도 있는데 우선 LR의 경우

   1

2

   3

이런식을 말하고..

우선 LR상태에서 한번의 회전으로 균형이 잡히는 LL이나 RR로 바꾼다

LR상태에서 RR회전을 하면 LL상태가 된다.

2, 3을 먼저 떼어서 RR회전을 하면

   2

3

으로 되고 그걸 다시 붙이면

   1

  2

3

이렇게 된다. 이것은..? 맞다 LL이다

그럼 RL은? 반대이다 부분 LL 하면 RR이 된다

개념설명은 이정도로..