비어있는 이진 트리에서 다음 순서로 값을 넣어보자

insert(1,2,3,4,5)

그러면 다음과 같은 형태의 이진트리가 나온다.

?? 이렇게 되면 O(logn)을 자랑하는 이진 트리가 연결리스트의 O(n)의 시간복잡도이 되었다. 

무엇을 위해서 그 복잡한 트리를 공부했는가 아까워서라도 트리의 탐색시간을 다시 O(logn)으로 만들어야한다. 그래서 나온 것이 AVL 트리이다. AVL 트리는 균형을 유지하는 알고리즘을 가지고 있는 균형 이진 트리이다. AVL 트리를 만든 아델슨 베스키와 E.M 랜디가 저렇게 트리가 편향되는 경우를 찾아보니 4가지 형태로 편향된다는 것을 찾았고 그 편향됨을 다시 고치는 방법 또한 만들었다. 따라서 AVL 트리는 편향된 트리를 고치는 4가지 방법 + 균형이 무너졌는지 알아내는 알고리즘을 가지고 있다. 

먼저 균형이 무너졌는지 알아내는 알고리즘을 알아보자 AVL 트리에서는 밸런스 팩터(Balance Facter)가 바로 이 것인데 밸런스 팩터는 왼쪽 서브 트리의 높이 - 오른쪽 서브트리의 높이 이다. 이 밸런스 팩터 값이 2이상이면 트리를 고치는 알고리즘이 작동한다. 

이제 균형이 무너지는 상태 4개와 고치는 방법 4개를 알아보자. 이진트리에서 균형이 무너지는 상태 LL, RR, LR, RL이 있다. 약간 복잡하니 심호흡 한번하고 보는게 좋다. 이것을 이해하면 그 복잡한 레드-블랙 트리도 쉽게 이해할 수 있다.

1. LL

위의 노드를 보면 71을 기준으로 왼쪽 왼쪽 이렇게 2개의 노드가 달려있는 것을 볼 수 있다. 참고로 사이트 오류인지 맨 마지막 노드의 숫자가 안보인다 넣은 숫자는 40이다.

아무튼 왼쪽 왼쪽 이렇게 2개 있으므로  LL이라고 부른다.

이를 해결하기 위해 LL회전이라는 것을 하는데 바로 무너진 지점을 루트로 보고 균형을 맞춘다.

즉 50이 루트가 되며 자동적으로 나머지 40은 왼쪽자식 71은 오른쪽 자식이 된다.

2.RR

이 역시 위의 기준과 같다. 그냥 대칭 구조일 뿐이다. 7을 루트로 만들어 주면 1은 왼쪽 자식 9는 오른쪽 자식이 된다.

3. LR

이번엔 복잡하다 정신 바짝 차리고 이해해보자.
이렇게 골때리는 형태로 있으면 일단 아는것은 LL와 RR 수리는 방법 뿐이요 그렇다면 그 방법을 쓰면 된다. 여기서 3의 오른쪽 자식에 NULL 노드를 붙이자 그러면 1,3,null 이렇게 RR편향이 된다. 그러면 고치면 1노드 자리에는 3이 들어가고 3노드 왼쪽에는 1이 있으며 오른쪽 자식은 NULL이다. 이제 NULL 노드를 떼면 다음과 같이 된다.
그렇다 LL 노드가 되었다 이제 LL 회전을 하면 다음과 같이 균형을 맞출 수 있다.

우린 답을 찾을 것이다 늘 그랬듯이...

4. RL
이제 균형을 어떻게 맞추는지 대략적으로 알았으므로 이번엔 실전 예제처럼 해보자 실제 트리에서는 자식 밑에 서브 트리가 주렁주렁 매달려 져 있는 경우가 있다.

AVL 트리의 시간 복잡도는 다음과 같다.

얼마나 외우기도 쉽고 아름다운가!

3. 구현