[자료구조]AVL Tree(Adelson-Velskii and Landis Tree)

소개글

AVL Tree(Adelson-Velskii and Landis Tree) 는 최악의 경우에도 일정 수준의 연산 시간을 보장하기 위해 한 노드로부터 서브 트리들의 높이의 균형을 유지하는 자료구조입니다. 이 트리에서의 자료의 탐색, 삽입 및 균형을 맞추는 방법에 대한 설명입니다.

목차

1. AVL Tree
2. 자료의 탐색
3. 자료의 삽입 및 균형 맞추기
- LL
- LR
- RR
- RL

본문내용

// AVL Tree
일반적인 binary tree는 동적인 검색 방법이지만 tree의 모양이 불균형적일 경우에 효율이 크게 저하되는데, AVL Tree는 이를 방지하기 위해서 tree의 불균형을 삽입과 삭제 연산에서 자동으로 해결한 방식입니다. AVL Tree는 한 노드에서 양쪽 서브 트리들의 높이가 균형을 이루는 binary tree 구조입니다. 이 트리의 모든 Node에 대해서, 이 Node를 root로 하는 트리 T는 왼쪽, 오른쪽 서브트리를,을 갖게 됩니다. 이 때, 이 서브 트리의 높이차 가 1이상이 나지 않는 구조를 유지합니다.

// 자료의 탐색
AVL Tree class는 자료의 삽입과 탐색 기능을 가지고 있는데, 탐색은 기존의 binary search와 같은 방식을 사용합니다. 즉, 찾으려는 자료가 현재 노드보다 작으면 left child로, 크면 right child로 가는 방식을 찾거나, leaf node에 도달할 때까지 반복하는 방식입니다.

// 자료의 삽입 및 균형 맞추기
AVL Tree에서 주목할 점은 삽입을 하는 방식입니다.
삽입 메커니즘을 간략하게 나타내면 다음과 같습니다.

① 삽입될 노드를 key로 root부터 leaf node 까지 순회한 후 null 위치에 삽입
(처음 삽입 위치는 binary search tree와 동일)
② 관련된 node(삽입된 위치로부터의 부모 node)의 BF를 갱신
③ BF의 절대값이 2이상인 경우 ‘Rotation’을 수행하여 Balance를 맞추고 BF를 조절한다.

Tree의 균형을 맞춰주기 위해서, Balance factor(이하 BF)라는 것을 정의합니다. 이것은 한 노드에서 왼쪽, 오른쪽 sub Tree의 높이 차를 의미하는데, 이 프로그램에서는 (오른쪽 sub Tree의 높이 - 왼쪽 sub Tree의 높이) 값을 사용했습니다. AVL Tree의 정의에 따라서, BF는 항상 -1, 0, 1 중의 한 값을 갖게 됩니다.

참고 자료

없음