AVL tree

/*

The source of this article is from

1 Geeks For Geeks (https://www.geeksforgeeks.org/avl-tree-set-1-insertion/)
2 Wikipedia (https://en.wikipedia.org/wiki/AVL_tree)

*/

AVL tree의 생성과 삽입, 순회에 대해

이번 시간에는 AVL Tree에 대한 개론과 생성과 삽입, 순회에 대한 구현을 말하려고 한다.

개요

AVL Tree는 BST의 일종이다. BST는 Binary Search Tree이며 원어 뜻 그대로 Search 하는데에 특화된 Tree이며, 거기에 더해 삽입, 삭제 등을 하는데에 효율적으로 설계 되어있다. 

naive 한 이진검색트리에 대해서 이전 포스트에서 이미 다루었다.

이진검색트리 보러가기 (이 포스팅 읽기 전에 이진검색트리에 대한 학습이 선행 되면 더 좋을것이다) 

http://ingyeoking13.tistory.com/224

사실 나에겐 이런 것들을 딱히 구현할 일이 별로 없다. DB에서 알아서 효율적으로 데이터들을 관리 해주기 때문에 실제로 만들일들이 없는 것이다. DB 파일으로 떨어뜨리지 않고 코드가 돌아가는 런타임때 하더라도 C/C++/C#에서 제공해주는 library를 쓰면 되는거니까...

그렇지만 흠... 왜하는것일까? 어쨋든, 머 알고리즘 같은걸 하기위해서 하겠지. 그렇지만 구현하는 그런 문제들을 직접구현하면서 풀어본적이 많이 없다. 왜나하면 왠만한 자료구조 library로 대체가 가능하기 때문에.... 흠....보통은 set, map 이런 library를 쓰지..... 일단은 내가알기론 C++ map이 BST의 일종, Red Black Tree 기반으로 되어있다고 들었던거같다. 물론 완벽히 똑같다고 하지는 않았던거같다....머 어쩄든... 각설하고... 그래도 응용할데가 분명히 있다고 생각한다. 왜냐하면 흥미로운 주제이긴하고, 응용된 library에 대한 기본적 지식이고, 또 많은 전공생들이 공부를 하고 있다고 생각하니까. 해야겠다..!

자자자자자자 , naive한 BST는 작업 수행 복잡도에 대해 O(h)을 제공한다. 이는 O(n) 또는 O(lg n)이며 O(n)은 일차원 배열과 비교하여 전혀 나아지지 않은 시간 복잡도이다. 물론 랜덤하게 tree를 구성했을 때 , BST는 O(lg n) 을 준수하지만, 최악의 경우는 BST의 모양이 편향되어 있으며 O(n)을 뛰는 선형적인 형태의 Tree가 생성된다는 것이다.

그래서 나온것이 Balanced Binary Search Tree의 개념이다. 어떠한 경우에도 임의의 노드의 양 옆 subtree의 Height를 Balanced 하게 유지하여 O(h) 복잡도를 O(lg n)으로 만드려고 노력하는 것이다.

삽입

새로운 노드의 삽입마다 tree를 밸런스있게 유지하려면, BST의 삽입을 조금 더 보완해줘서 어떤 밸런싱 작업을 할 수 있게해줘야한다. 다음 기본적인 두 작업을 통해 BST 속성을 유지할 수 있다.

BST의 속성이란?

"x를 이진 검색 트리의 노드라고 하자. 만약 노드 y가 x의 왼쪽 subtree에 있다면, y.key <= x.key 이다. 만약 y가 x의 오른쪽 subtree에 있다면, y.key >= x.key를 만족한다." (기억이 안난다면 여기를 클릭)

다음은 기본적인 두 작업에 대한 것이다.

1. Left Rotation 2. Right Rotation

위의 그림을 살펴보자. x, y, 그리고 삼각형 모양의 노드 들이 있다. 이때 x, y는 단 하나의 노드라고 생각하고, 삼각형 모양의 노드는 어떤 노드들의 집합, 즉 subtree를 그린것으로보자. 이 때 Rotation 이라는 이러한 연산 으로 우리는 tree 자체를 밸런스 하게 놓을 수 있다는 것이다. 당장 와닿지 않아도 괜찮다. 아래 그림을 잠깐 보자.

이렇게 우측 subtree와 좌측 subtree의 height가 비교적 같아진다. 

자, 그렇다면 Balance란?

Balance는 다음과 같이 정의된다. 

1. 만약 트리가 비어있다면 balance 하다는 것이다.

2. 트리가 비어있지 않은 경우에 대해서, 모든 노드에 대하여 | height (left subtree) -heigh (right subtree) | <= 1 을 만족해야한다.

사실 지금에서 트리 내 임의의 노드에 대해 ABS( H ( left subtree )-  H( right subtree ) ) 가 <=1 을 만족해야한다는 것은 터무니 없는 논리적 진전이다. 그러나, 이것을 유지할 수 있다면 BST에 이득인 점이라는 것을 스스로 설득하면서 시작해보자. 만약, 모든 노드에 대해 ABS ( H (left subtree ) - H (right subtree) )<=1 를 만족한다면, 모든 노드에 대해 그 것의 서브트리의 높이 차가 -1 , 0, 1 임을 개념적으로 확실히 하고 가자. 이 때, 이상적으로 만약 모든 노드가 자신의 양옆 subtree 차를 0으로 가진다면 n 개의 노드가 있을 때 그 트리의 높이는 lg n이 되고 이상적인 시간 복잡도를 제공해 줄 것이다.

삽입의 순서 ... =_= 흐흠..;;

Insert하려는 노드를 z라고 해보자

1) 일반적인 BST 삽입을 수행한다. 루트 노드에서부터 선택하면서 큰지 작은지 판단하면서 트리를 따라 내려가 리프노드에 노드를 삽입한다.

2) w부터 시작해서, 트리를 타고올라가는데 첫 번째로 unbalanced한 노드를 찾는다. 여기서 z가 첫 번째 언밸런스드 노드라고 하자. 그리고 y를 w에서 z로 타고 올라오는데 만날 수 있는 z의 자식 노드라고 하자. 그리고 x를 z의 손자 노드라고하자. 이때 z 또한 w에서 z로 타고 올라오는데 만날 수 있다.

3) z를 루트로 삼는 sbutree를 적절한 rotation operation을  해주어야한다. 이때 x, y, z 를 밸런스 있게 정렬 해주려면 4가지 경우의 수를 고려해주면된다.

a) y가 z의 왼쪽 child 이고 x가 y의 왼쪽 child 이다.  LL Case
b) y가 z의 왼쪽 child 이고 x가 y의 오른쪽 child 이다.  LR case
c) y가 z의 오른쪽 child이고 x가 y의 오른쪽 child 이다. RR Case
d) y가 z의 오른쪽 child이고 x가 y의 왼쪽 child 이다. RL Case

ㅇㅇ 케이스를 분류 해줘서 하면된다.

햐 쓰려고보니까 귀찮았다. B+Tree도 완료한지 꽤 됐는데 정리하기가 너무 귀찮다. 

햐~~ 할게 너무많다

Geeks for Geeks 에 잘나와있다.

그리고 AVL Tree를 이용하여 백준의 포켓몬스터 이다솜 문제를 해결했다.

백준 이진검색트리 문제 포켓몬스터 이다솜 문제 + 정답 소스(AVL) 보러가기