똑똑한 코드 작성을 위한 실전 알고리즘

206

똑똑한 코드 작성을 위한 실전 알고리즘

그림

6-10

값을 두 개 삽입한 뒤 불균형 트리가 되었다

[그림

6

-

10

]의 맨 왼쪽 완전 이진 트리는 완전히 균형을 이룬 구조다. 각 잎새 노드는 높이가

0

이고 루트 노드는 높이가

2

다. 그림 가운데 트리처럼

29

를 삽입하면 알맞은 위치에 새로운 잎

새 노드가 생성된다.

29

의 모든 조상 노드는 높이가

1

만큼 증가하고 이에 따라 음영이 바뀐다.

그림 맨 오른쪽 트리처럼

27

을 삽입하면 트리는 균형을 잃는다.

14

를 루트로 하는 왼쪽 하위

트리는 높이가

1

이지만

53

을 루트로 하는 오른쪽 하위 트리는 높이가

3

이다.

26

,

53

등 다른

노드도 비슷하게 균형을 잃는다. 다음 절에서는 이진 탐색 트리의 불균형 탐지 및 재균형 전략

을 알아보자.

6.7

자가 균형 이진 트리

AVL

트리

4

는 최초로 알려진 자가 균형 이진 트리로,

1962

년에 개발되었다. 전제는 이진 탐색

트리에 값이 삽입되거나 제거된 후에 트리 구조에서 약점이 감지되고 복구가 된다는 것이다.

AVL

트리에서는 각 노드의 왼쪽 하위 트리의 높이에서 오른쪽 하위 트리의 높이를 뺀 값, 즉

4

AVL

트리는 발명가 아델슨-벨스키(

Adelson

-

Velskii

)와 랜디스(

Landis

) 이름을 따서 지어졌다.

29

삽입

높이 =

0

높이 =

1

높이 =

2

높이 ...