AVL 트리의 모든 것

소개글

알고리즘 수업이나, 자료구조 수업 때 다루게 되는 AVL 트리에 대해
정말 많은 것들을 정리했습니다.
각종 수학적인 증명과정과 트리의 구현에 대해 그림도 첨부했고
끝으로 AVL 트리를 구현하는 C 코드와 스크린 샷까지 모았습니다.
큰 도움이 될 거라고 생각합니다.

목차

1. 트리

2. AVL 트리
[증명] n개의 항목을 저장하는 AVL 트리의 높이는 O(log n)

3. 자료의 삽입과 균형 맞추기
[삽입 알고리즘 분석]

4. 자료의 삭제

5. 자료의 탐색

6. 여러 구조들의 비교

7. AVL 트리의 구현 < C 소스코드 >

8. 스크린 샷

본문내용

AVL 트리는 1962년에 Adel’son-Vel’skii와 Landis에 의해 제안된 트리로, 제안자의 이니셜을 따서 명명되었으며 서브 트리들의 높이에 관해 균형을 이루는 이진 트리다. 이 균형 트리로 인해 n 개의 노드를 가진 트리에 대해 동적 검색을 O(log n) 시간 내에 할 수 있고, 새로운 키를 O(log n) 시간 내에 삽입하거나 삭제할 수도 있다.

일반적인 이진 트리는 동적인 검색 방법이지만 트리의 모양이 불균형일 경우에 효율이 크게 저하된다. AVL 트리는 이를 방지하기 위해 트리의 불균형을 삽입과 삭제 연산에서 자동으로 해결한다. AVL트리의 모든 노드에 대해서, 이 노드를 루트로 하는 트리 T는 왼쪽 서브트리인 TL과, 오른쪽 서브트리 TR 을 갖게 된다. 이 때, 이 서브 트리의 높이 차가 1이상 나지 않는 구조를 유지한다. 역도 성립하며 이러한 특징을 가졌기 때문에 높이 균형 이진 트리(Height Balanced Binary Tree)라고도 한다.
(트리의 노드 v의 높이는 v에서 외부노드까지의 가장 긴 경로의 길이다.)

높이 균형 특성의 직접적인 결과는 AVL 트리의 서브트리가 바로 AVL 트리라는 것이다. 즉, 모든 서브 트리도 높이가 균형을 이루어야 한다.
[정리] n개의 항목을 저장하는 AVL 트리의 높이는 O(log n)이다.
[증명] 직접 AVL트리 높이의 상한을 찾는 노력 대신에, 높이가 h인 AVL트리의 내부 노드 n (h)가 최소한 지수적으로 성장함을 보인다.
즉, 어떤 상수 c > 1에 대해 n (h)는 Ω (ch) 이다. 이로부터 n개의 키를 저장하는 AVL 트리의 높이가 O(log n) 임을 유도하는 것이 쉬운 방법이다.

먼저, 높이가 1인 AVL 트리는 최소한 하나의 내부 노드를 가져야만 하고, 높이가 2인 AVL 트리는 최소한 두 개의 내부 노드를 가져야하기 때문에 n (1) = 1 이고, n (2) = 2 임을 알 수 있다.

참고 자료

없음