균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점

Presentation on theme: "균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점"— Presentation transcript:

1 균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
이진 탐색과 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조 이진 탐색은 자료들이 배열에 저장되어 있으므로 삽입과 삭제가 상당히 힘들다. 즉 자료를 삽입하고 삭제할 때마다 앞뒤의 원소들을 이동시켜야 한다. 이진 탐색 트리는 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조 삽입, 삭제가 빈번히 이루어진다면 반드시 이진 탐색 트리를 사용하여야 한다. 이진탐색트리에서의 시간복잡도 균형트리: O(logn) 불균형트리: O(n), 순차탐색과 동일

2 AVL 트리 Adelson-Velskii와 Landis에 의해 1962년에 제안된 트리
각 노드에서 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이 차이가 1 이하인 이진 탐색 트리 트리가 비균형 상태로 되면 스스로 노드들을 재배치하여 균형 상태로 만든다. AVL 트리는 균형 트리가 항상 보장되기 때문에 탐색이 O(logn)시간 안에 끝나게 된다. 균형 인수(balance factor)=(왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이) 모든 노드의 균형 인수가 ±1 이하이면 AVL 트리이다.

3 AVL 트리의 연산 탐색연산: 이진탐색트리와 동일
균형을 이룬 이진 탐색 트리에서 균형 상태가 깨지는 것은 삽입 연산과 삭제 연산시이다. 삽입 연산시에는 삽입되는 위치에서 루트까지의 경로에 있는 조상 노드들의 균형 인수에 영향을 줄 수 있다. 따라서 즉 새로운 노드의 삽입 후에 불균형 상태로 변한 가장 가까운 조상 노드, 즉 균형 인수가 ±2가 된 가장 가까운 조상 노드의 서브 트리들에 대하여 다시 균형을 잡아야 한다.

4 AVL트리의 삽입연산 균형트리로 만드는 방법: 회전(rotation)
AVL 트리에서 균형이 깨지는 경우에는 다음의 4가지의 경우가 있다. 새로 삽입된 노드 N로부터 가장 가까우면서 균형 인수가 가 된 조상 노드를 A라고 하자. LL 타입: N이 A의 왼쪽 서브 트리의 왼쪽 서브 트리에 삽입된다. LR 타입: N이 A의 왼쪽 서브 트리의 오른쪽 서브 트리에 삽입된다. RR 타입: N이 A의 오른쪽 서브 트리의 오른쪽 서브 트리에 삽입된다. RL 타입: N이 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 삽입된다.

5 종합적인 예제

6

7 회전방법 LL 회전:A부터 N까지의 경로상의 노드들을 오른쪽으로 회전시킨다.
LR 회전: A부터 N까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전시킨다. RR 회전: A부터 N까지의 경로상의 노드들을 왼쪽으로 회전시킨다. RL 회전: A부터 N까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전시킨다.

8 회전방법(cont.)

9

10