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가..

BST(Binary Search Tree)는 아래와 같은 편향 이진 트리(Skewed Binary Tree)일 경우, 성능이 악화된다 Complete Binary Tree일 때 탐색 시간복잡도는 O(log N)이지만, (최악의 경우) 연결리스트의 형태를 한 Skewed Binary Tree일 경우 시간 복잡도가 O(N)에 수렴한다 이러한 편향 현상은 BST에서 Insert, Delete 연산으로 인해 발생할 수 있어서, 이를 보완하기 위한 자료구조로 자가 균형 이진 탐색 트리(Self-Balanced Binary Search Tree)가 존재한다 그 대표적인 예시인 AVL Tree와 Red-Black Tree에서도 아래에서 소개할 Rotation 연산을 이용해서 스스로 Height 균형을 유지하기 때문에..