AVL 트리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
AVL 트리의 시간복잡도
평균 최악의 경우
공간
검색
삽입
삭제

AVL 트리(AVL tree)는 가장 초기에 나온 균형 잡힌(balanced) 이진 탐색 트리이다. 1962년 G.M. Adelson-Velskii와 E.M. Landis 가 그들의 논문 "An algorithm for the organization of information"[1] 을 통해 발표했고 그들의 이름을 따서 지어졌다. AVL 트리는 각각의 노드(node, 분기점)마다 왼쪽과 오른쪽 부분 트리(sub-tree)의 높이 차이에 대한 정보를 가지며 부분 트리의 높이 차이가 1보다 크지 않은 성질을 가진다. 균형 잡힌 AVL 트리는 n개의 원소가 있을 때 O(log n) 의 시간복잡도로 검색, 삽입, 삭제를 할 수 있다. 그러나 삽입과 삭제를 할 때에는 원하는 노드를 찾기 위해 2개의 경로가 필요하기 때문에 레드-블랙 트리 만큼 효율이 좋지 않아 자주 쓰이지는 않는다.[2]

정의와 성질[편집]

  • 높이 균형 성질(height-balance property): 트리 의 모든 내부 노드(internal node) 에 대하여 의 자식 노드들의 높이 차이가 최대 1이다.
  • 임의의 이진 탐색 트리: 가 높이 균형 성질을 만족할 때 AVL 트리라고 한다.

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

이진 탐색 트리에서의 검색 시간복잡도는 트리의 높이 이므로 AVL 트리의 검색 시간이 임을 알 수 있다.

동작[편집]

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

삽입[편집]

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

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

회전[편집]

트리 의 재구성 작업을 회전(Rotation)이라 한다.

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

가 이진 탐색 트리 의 노드이고 가 부모, 가 할아버지 노드일 때 다음과 같이 재구성한다.

  1. , , 를 왼쪽-오른쪽 순서 (inorder)로 나열 한 순서대로 , , 라고 하고, , , 의 4개의 부분 트리들을 왼쪽-오른쪽 순서 (inorder)로 나열한 것을 , , , 라고 하자.
  2. 가 root인 부분 트리를 를 root로 하는 새로운 부분 트리로 바꾼다.
  3. 의 왼쪽 자식이 되고 , 은 각각 의 왼쪽, 오른쪽 자식이 된다.
  4. 의 오른쪽 자식이 되고, , 는 각각 의 왼쪽, 오른쪽 자식이 된다.

이 작업을 구상화하면 일 때 와 회전시키는 것처럼 보인다. 이 작업을 single rotation이라고 한다.

일 때 와 회전시키고 다시 와 회전시키는 것처럼 보인다. 이 작업을 double rotation이라고 한다.

이 재구성 방법은 의 부모-자식 관계만을 바꾸는 것이기 때문에 시간이 걸린다.

삭제[편집]

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

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

각주[편집]

  1. Adelson-Velskii, G.; E. M. Landis (1962). “"An algorithm for the organization of information"”. 《Proceedings of the USSR Academy of Sciences》 146: 263–266.  (Russian) English translation by Myron J. Ricci in Soviet Math. Doklady, 3:1259–1263, 1962.
  2. Robert Lafore(1998), Data Structures & Algorithms in JAVA, Sams, p. 334. ISBN 1-57169-095-6.

참고문헌[편집]

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