AVL Tree 개념
-
1. AVL 트리의 개념C 자료구조/7. Binary Search Tree Advanced - AVLTRee 2020. 6. 18. 19:46
1. 이진 탐색 트리의 단점 이진 탐색 트리에서의 삽입, 삭제 연산을 앞에서 다루었지만, 이들 연산들은 이진 탐색 트리를 유지시키기는 하지만, 균형 트리를 보장하지는 않는다. 만약 이진 탐색 트리가 균형 트리가 아닐 경우에는 탐색의 시간이 높아지게 된다. 예를 들어, {5,2,8,1,7,3,9}와 같은 순서로 정수를 공백 이진 탐색 트리에 삽입하면 아래 [그림 1]과 같은 이진 탐색 트리가 만들어 진다. 그러나, 만약 {1,2,3,5,7,8,9}의 순으로 입력 된다면 [그림 2 ]와 같은 트리가 만들어 질 것이다. [그림 1 ] [그림 2 ] 위의 [ 그림 1]의 이진 탐색 트리에서 최대 비교 횟수는 3회인 반면, [그림 2 ]의 트리에서는 7회가 된다. 이진 탐색 트리가 [그림 2 ]와 같이 경사 트리..