2JINISHAPPY 2JINISHAPPY

AVL Tree AVL 트리는 아래의 성질을 만족하는 BST(Binary Search Tree)의 한 종류다 Tree 상의 모든 Node p에 대해 p의 left subtree와 right subtree의 height 차이가 최대 1을 넘을 수 없다 이러한 성질을 AVL 트리의 Balanced Property라고 하며, 일반적인 BST와 비교했을 때, Search 연산은 완전히 동일하지만 Insert/Delete 연산을 할 때 이 성질이 깨지지 않도록 추가적인 연산을 수행한다 위의 그림에서 12라는 노드를 추가했을 때, 해당 노드를 자손으로 가지는 노드들(4, 8, 15, 10, 12)의 height가 변한다 그리고 노드 15를 봤을 때 왼쪽 서브트리의 height가 2, 오른쪽 서브트리의 height가..