AVL 트리 문서 원본 보기

{{위키데이터 속성 추적}}
[[파일:AVLtreef.svg|섬네일|같은 트리를 높이 균형을 맞춘 후의 상태; 평균 이동 비용이 3.00 노드 접근(node access)로 감소되었다.]]

{| class="infobox"
|-
! colspan="3" | AVL 트리의 시간복잡도
|-
! |
| 평균
| 최악의 경우
|-
! 공간
| <math>O(n)</math>
| <math>O(n)</math>
|-
! 검색
| <math>O(\log n)</math><ref name="wiscurl">{{웹 인용|last=Eric Alexander |title=AVL Trees |url=http://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html |archive-url=https://web.archive.org/web/20190731124716/https://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/index.html |archive-date=July 31, 2019}}</ref>
| <math>O(\log n)</math><ref name="wiscurl" />
|-
! 삽입
| <math>O(\log n)</math><ref name="wiscurl" />
| <math>O(\log n)</math><ref name="wiscurl" />
|-
! 삭제
| <math>O(\log n)</math><ref name="wiscurl" />
| <math>O(\log n)</math><ref name="wiscurl" />
|}

[[컴퓨터 과학]]에서 '''AVL 트리'''(발명자의 이름인 '''A'''delson-'''V'''elsky and '''L'''andis에서 따온 이름)는 [[자가 균형 이진 탐색 트리]]이다. 스스로 균형을 잡는 데이터 구조 중 처음으로 발명되었다. AVL 트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다. 만약 어떤 시점에서 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 스스로 균형을 잡는다. 검색, 삽입, 삭제는 모두 평균과 최악의 경우 [[점근 표기법|O]](log ''n'')의 시간복잡도가 걸린다. 삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있다.

== 정의와 성질 ==
* '''높이 균형 성질'''(height-balance property): 트리 <math>T</math>의 모든 내부 노드(internal node) <math>v</math>에 대하여 <math>v</math>의 자식 노드들의 높이 차이가 최대 1이다.

* 임의의 이진 탐색 트리 <math>T</math>가 높이 균형 성질을 만족할 때 AVL 트리라고 한다.

높이 균형 성질(height-balance property)로부터 <math>n</math>개의 원소를 갖는 AVL 트리의 높이는 <math>log n</math>이라는 사실을 알 수 있다.

이진 탐색 트리에서의 검색 시간복잡도는 트리의 높이 이므로 AVL 트리의 검색 시간이 <math>O(\log n)</math> 임을 알 수 있다.

== 동작 ==
AVL 트리에서 노드를 일반적인 이진 탐색 트리처럼 삽입, 삭제 시키면 높이 균형 성질을 만족하지 않게 된다. 노드가 삽입, 삭제될 때 회전(rotation)을 통해 트리를 재구성하여 높이 균형 성질을 유지시킨다.

=== 삽입 ===
AVL 트리 T에 새로운 노드 d를 삽입(Insertion)하는 방법은 T에서 d가 단말 노드(leaf node)로 삽입될 수 있도록 하는 노드 w를 찾고 w의 자식으로 d를 삽입한다.

d를 삽입하면 불균형해질 수 있는데 세 노드를 기준으로 회전(rotation)시킴으로써 균형을 맞춘다.

=== 회전 ===
트리 <math>T</math>의 재구성 작업을 회전(Rotation)이라 한다.

회전의 기준이 되는 세 노드 <math>x</math>, <math>y</math>, <math>z</math>는 다음과 같다.
<math>z</math>는 <math>w</math>로부터 root로 가는 경로상에 가장 처음으로 위치한 불균형한 노드이다.
<math>y</math>는 <math>z</math>의 자식 중에서 가장 큰 높이를 갖는 노드이다.
<math>x</math>는 <math>y</math>의 자식 중에서 가장 큰 높이를 갖는 노드이다.

<math>x</math>가 이진 탐색 트리 <math>T</math>의 노드이고 <math>y</math>가 부모, <math>z</math>가 할아버지 노드일 때
다음과 같이 재구성한다.
# <math>x</math>, <math>y</math>, <math>z</math>를 왼쪽-오른쪽 순서 (inorder)로 나열 한 순서대로 <math>a</math>, <math>b</math>, <math>c</math> 라고 하고, <math>x</math>, <math>y</math>, <math>z</math>의 4개의 부분 트리들을 왼쪽-오른쪽 순서 (inorder)로 나열한 것을 <math>T_{0}</math>, <math>T_{1}</math>, <math>T_{2}</math>, <math>T_{3}</math> 라고 하자.
# <math>z</math>가 root인 부분 트리를 <math>b</math>를 root로 하는 새로운 부분 트리로 바꾼다.
# <math>a</math>가 <math>b</math>의 왼쪽 자식이 되고 <math>T_{0}</math>, <math>T_{1}</math>은 각각 <math>a</math>의 왼쪽, 오른쪽 자식이 된다.
# <math>c</math>가 <math>b</math>의 오른쪽 자식이 되고, <math>T_{2}</math>, <math>T_{3}</math>는 각각 <math>c</math>의 왼쪽, 오른쪽 자식이 된다.

이 작업을 구상화하면
<math>b=y</math> 일 때 <math>y</math>를 <math>z</math>와 회전시키는 것처럼 보인다. 이 작업을 single rotation이라고 한다.

<math>b=x</math> 일 때 <math>x</math>를 <math>y</math>와 회전시키고 다시 <math>z</math>와 회전시키는 것처럼 보인다. 이 작업을 double rotation이라고 한다.

이 재구성 방법은 <math>T</math>의 부모-자식 관계만을 바꾸는 것이기 때문에 <math>O(1)</math> 시간이 걸린다.

=== 삭제 ===
AVL 트리 <math>T</math>에서 노드 <math>d</math>를 삭제(Removal)하는 방법은 root부터 <math>d</math>를 검색한다.
<math>d</math>가 단말 노드가 아니라면 자신의 왼쪽 부분 트리 중에서 최댓값을 갖는 노드나 오른쪽 부분 트리 중에서 최솟값을 갖는 노드를 <math>d</math>와 바꾼다.
이 작업을 <math>d</math>가 단말 노드가 될 때까지 반복하여 단말 노드 <math>d</math>를 삭제한다.

삭제 역시 트리가 불균형해질 수 있는데 삽입과 동일한 방법으로 <math>d</math>의 부모를 <math>w</math>라고 한 뒤 회전시켜 균형을 맞춘다.

== 같이 보기 ==
* [[B 트리]]
== 각주 ==
{{각주}}

== 참고 문헌 ==
* Robert Lafore(1998), ''Data Structures & Algorithms in JAVA'', Sams, {{ISBN|1-57169-095-6}}
* Michael T.Goodrich, Roberto Tamassia(2006), ''Data Structures & Algorithms in JAVA(4th edition)'', John Wiley & Sons, {{ISBN|0-471-73884-0}}
* [[도널드 커누스|Donald Knuth]]. ''[[컴퓨터 프로그래밍의 예술|The Art of Computer Programming]]'', Volume 3: ''Sorting and Searching'', Third Edition. Addison-Wesley, 1997. {{ISBN|0-201-89685-0}}. Pages 458–475 of section 6.2.3: Balanced Trees.
* {{앵커|Haeupler}}{{인용|last1=Haeupler |first1=Bernhard |title=Rank-balanced trees |url=http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf |journal=ACM Transactions on Algorithms |volume=11 |issue=4 |page=Art. 30, 26 |year=2015 |doi=10.1145/2689412 |mr=3361215 |s2cid=1407290 |last2=Sen |first2=Siddhartha |last3=Tarjan |first3=Robert E. |author-link3=로버트 타잔}}.

[[분류:이진 트리]]
[[분류:소련의 발명품]]
[[분류:1962년 컴퓨팅]]
[[분류:분할 상환 자료 구조]]
[[분류:탐색 트리]]