[자료구조] AVL Tree

Binary search tree에 대해 이야기해 보았고, 삽입/삭제 시 생길 수 있는 unbalance 문제에 대해서도 이해할 수 있었다. AVL tree는 가장 초기에 나온 self-balanced binary search tree로, "An algorithm for the organization of information"이라는 논문에 의해 발표되었다. AVL tree의 'AVL'은 논문을 발표한 Adelson-Velskii와 Landis의 이름을 따 지어졌다.

AVL tree에서는 트리의 모든 internal node(leaf node가 아닌 노드)에 대하여, child node들의 높이 차이가 최대 1인 것을 높이 균형 성질이라 부른다. 임의의 binary search tree가 높이 균형 성질을 만족할 때 AVL tree라고 한다. 이진 탐색 트리가 높이 균형 성질을 만족하려면 삽입과 삭제 시 추가적인 동작이 하나 있어야 하고, AVL tree는 이에 대해 '회전'이라는 동작을 수행한다.

삽입

회전

삭제