알고리즘 이론 12강(2). AVL 트리

 

[균형잡힌 이진 검색 트리]

: BST의 최악 케이스의 시간 복잡도는 O(n)이고 이는 트리가 선형 형태일때를 의미한다.

: 그래서 시간 복잡도를 줄이기 위해 트리 균형을 유지하기 위한 여러가지 방법이 있다.

  - 아무것도 안하는 방법

  - 엄격한 균형 (어느시점에서든 완벽히 균형잡게 하는 방법)

  - 일정 수준의 불균형까지만 허용하는 방법

  - 자가-조절

: 이때 엄격한 균형을 유지하기 위한 방법은 비싼 비용이 필요하다(O(n))

: 여기서 설명할 AVL 트리도 이런 균형 잡힌 이진 검색 트리를 유지하기 위한 트리이다.

 

 

 

[AVL 트리]

: Adelson-Velskill and Landis 가 고안한 트리

: 균형잡힌 높이의(height-balanced) 이진 검색 트리이다.

: 트리의 | 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이 | <= 1 까지만 허용.

: 기존의 AVL 트리의 조건에 알맞던 트리에 INSERT가 발생시, 이 트리의 균형이 깨질 수 있다. ( = 2 or -2 가 될수 있다)

: 그리고 이러한 불균형이 발생했을때, 트리의 해당 node 주변을 회전(rotation)함으로써 해결한다.

 

 

 

[AVL 트리의 삽입]

: 트리의 잎 부분에 삽입.. 균형 깨지면 아래와 같은 작업 수행한다.

: 4가지의 경우를 고려한다.

# Outside Cases ( 단일 회전 필요 )

  1) 노드 a의 왼쪽 자식노드의 왼쪽 서브트리로 삽입되는 경우

  2) 노드 a의 오른쪽 자식 노드의 오른쪽 서브트리로 삽입되는 경우

# Inside Cases ( 이중 회전 필요 )

  3) 노드 a의 왼쪽 자식노드의 오른쪽 서브트리에 삽입되는 경우

  4) 노드 a의 오른쪽 자식 노드의 왼쪽 서브트리에 삽입되는 경우

 

# Outside Case - 1번 케이스 예시 (2번 케이스는 미러링)

1번 케이스 문제 발생

1번 케이스 문제 해결

 

# Inside Case - 3번 케이스 예시 (4번 케이스는 미러링)

3번 케이스 문제 발생

해결 과정 1 (Y서브트리 분할)

해결 과정 2 ( rotate 1번 수행 결과 )

3번 케이스 문제 해결 ( rotate 2번 완료 )

 

 

 

[AVL 트리의 노드 구성]

: 해당 노드의 height를 저장하는 것이 아니라, height의 차이값만 기억 하고 있는다.

 

 

 

[AVL 트리 삽입 예시]

: 생략

# 코드같은거 외울 필요 없고, 예시로 AVL 트리에 삽입 주어졌을때, 해당 트리 균형 잡는 과정을 숙지해야한다.

 

 

[AVL 트리 삭제]

: 삽입보다 어렵다. (안다룸)

 

 

[AVL 트리의 장단점]

- 장점

  1) 트리의 검색이 항상 O(logn)으로 균형잡혀 있다.

  2) 트리의 삽입과 삭제 또한 O(logn)이다.

- 단점

  1) 프로그래밍과 디버깅이 어렵다 (구현이 어려움)

  2) 빠르지만, 재균형 잡는 시간이 든다

  3) 일반적으로 사용되는 균형 트리에 최적화된 다른 트리가 존재한다. (B-Tree)