AVL 트리: balanced binary search tree
지난 포스팅에서 이진 탐색 트리(Binary Search Tree, BST)에 대해 알아보았다. 오늘은 BST의 단점을 보완한 AVL 트리(AVL Tree)에 대해 자세히 알아보겠다. BST는 삽입, 삭제 과정에서 트리가 한쪽으로 치우쳐 성능이 저하될 수 있다는 단점이 있었다. AVL 트리는 이러한 문제를 해결하기 위해 균형을 유지하는 규칙을 추가한 똑똑한 자료구조이다.
Balanced Search Tree
AVL 트리를 이해하기 전에 먼저 Balanced Search Tree에 대해 간략히 알아보겠다. Balanced Search Tree는 삽입, 삭제 연산 후에도 트리의 높이가 항상 O(log n)을 유지하도록 균형을 맞추는 트리다. 이를 통해 탐색, 삽입, 삭제 연산의 시간 복잡도를 항상 O(log n)으로 보장할 수 있다. 대표적인 Balanced Search Tree에는 AVL 트리, red-black 트리, B-트리 등이 있다.
Trinode Restructuring
Balanced Search Tree의 주요 연산 중 하나는 Trinode Reconstruction다. 이 연산은 삽입 또는 삭제 후 트리의 균형이 깨졌을 때, 균형을 복원하기 위해 사용한다. Trinode Reconstruction은 세 개의 노드(x, y, z)와 네 개의 서브트리(T0, T1, T2, T3)를 이용하여 트리의 구조를 변경한다.
Trinode reconstruction
AVL 트리 (Adelson-Velsky and Landis Tree)
AVL 트리는 모든 노드에 대해 왼쪽 자식과 오른쪽 자식의 높이 차이가 최대 1인 이진 탐색 트리다. 균형 조건을 통해 AVL 트리는 탐색, 삽입, 삭제 연산의 시간 복잡도를 O(log n)으로 유지할 수 있다.
AVL 트리의 삽입 (Insertion)
AVL 트리에 새로운 노드를 삽입하는 과정은 다음과 같다.
- 탐색: 먼저 이진 탐색 트리와 동일하게 삽입할 위치를 찾는다.
- 삽입: 새로운 노드를 외부 노드(external node)로 삽입한다.
- 균형 확인: 삽입된 노드의 부모 노드부터 루트 노드까지 거슬러 올라가며 각 노드의 균형을 확인한다.
- 재구성: 만약 균형이 깨진 노드를 발견하면, Trinode Reconstruction을 통해 균형을 복원한다.
AVL tree balancing
 |
| AVL tree insertion |
AVL 트리의 삭제 (Removal)
AVL 트리에서 노드를 삭제하는 과정은 다음과 같다.
 |
| AVL tree deletion |
- 탐색: 먼저 이진 탐색 트리와 동일하게 삭제할 노드를 찾는다.
- 삭제: 이진 탐색 트리의 삭제 규칙에 따라 노드를 삭제한다.
- 균형 확인: 삭제된 노드의 부모 노드부터 루트 노드까지 거슬러 올라가며 각 노드의 균형을 확인한다.(삭제된 노드의 부모 노드에서 불균형 발생함)
- 재구성: 만약 균형이 깨진 노드를 발견하면, Trinode Reconstruction을 통해 균형을 복원한다.
AVL tree balancing
AVL 트리의 성능 (Performance)
AVL 트리는 균형을 유지하기 위한 추가적인 연산이 필요하지만, 탐색, 삽입, 삭제 연산의 시간 복잡도를 O(log n)으로 보장한다는 큰 장점이 있다. 따라서 데이터의 삽입 및 삭제가 빈번하게 발생하는 동적 데이터 환경에서 효율적인 자료구조이다.
마무리하며
이번 포스팅에서는 AVL 트리의 개념, 삽입, 삭제 과정, 그리고 성능에 대해 알아보았다. AVL 트리는 균형 잡힌 이진 탐색 트리의 대표적인 예시로, 균형을 유지하면서도 효율적인 연산을 지원한다. 다음 포스팅에서는 스플레이 트리(Splay Tree)에 대해 알아보도록 하겠다. Splay tree는 접근 지역성(locality of reference)을 활용하여 자주 접근하는 노드를 루트 노드에 가깝게 위치시키는 특징을 가지고 있다.
추천글 :
