C 자료구조/7. Binary Search Tree Advanced - AVLTRee
-
4. AVL 트리의 Rebalance 함수C 자료구조/7. Binary Search Tree Advanced - AVLTRee 2020. 6. 19. 23:06
앞에서 균형 인수는 다음과 같이 정의한다고 했다. '균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리 높이' 그리고 트리에서 트리의 높이를 구하는 함수 또한 만들었다. 1. 균형 인수를 구하는 함수 2. 트리의 균형 여부를 판단하고, 트리를 균형 트리로 만드는 함수 그리고, 트리가 비 균형 상태일 때, 균형 상태로 만들어주는 함수를 Rebalance 라 하고 이를 만들어 보자. 우선 트리가 균형 상태 인지 아닌지를 먼저 확인을 한다. 비 균형 상태이면, 균형 상태로 만들면 된다. 앞에서 말했듯이, 균형이 깨지는 경우는 4가지의 경우가 있다고 했다. 각 경우를 파악하고, 각 경우 맞게 회전시키면 된다. 그리고 앞에서, 균형을 이룬 이진 탐색 트리에서 균형 상태가 깨지는 이유는 노드의 삽입과 삭제 ..
-
3. AVL 트리의 RL회전, LR회전C 자료구조/7. Binary Search Tree Advanced - AVLTRee 2020. 6. 19. 19:03
1. RL회전 RL타입은 조상 노드 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 노드가 추가됨으로해서 발생한다. RL회전은 균형 트리를 만들기 위해서 2번의 회전이 필요하다. LL회전을 한 다음에, RR회전을 하면 된다. 아래 [ 그림 2 ]과 같이 AVL 트리의 노드 A의 오른쪽 서브 트리의 왼쪽 서브 트리에 새로운 노드를 추가하면 비균형 트리가 되고, 이를 바로 잡기 위해서는 LL회전과 RR회전의 2번의 회전이 필요하다. 아래의 그림과 같이 트리가 있다고 하자. [ 그림 1 ] 위의 트리에서 데이터의 삽입이 이루어졌다고 가정하자. 그러면 아래의 그림이 된다. [ 그림 2 ] 위에서 데이터의 삽입이 이루어짐과 동시에 균형 트리를 맞춰야 한다. 먼저, LL회전 시키면, 아래의 그림이 된다. 그리고, RR회..
-
2. AVL 트리의 LL회전, RR회전C 자료구조/7. Binary Search Tree Advanced - AVLTRee 2020. 6. 19. 00:42
시작 하기에 앞서, AVL 트리의 구현에 이진 탐색 트리의 모든 헤더 파일과 소스 파일이 필요 지금부터 만드는 모든 함수들은 AVLTree헤더 파일과 AVLTree 소스 파일에 정의함. 1. LL회전 아래 [그림 1]의 LL타입의 경우 6,5,2순으로 노드를 삽입했을 경우에 만들어 진다. 노드6은 균형인수가 2로서 불균형하다. 그러나 오른쪽으로 회전을 시키면 다시 균형 트리를 만들 수 있다. [그림 1 : LL 타입 ] [그림 2 : LL 회전 결과 ] LL회전을 보다 일반적인 경우로 정리해보자. LL타입은 조상 노드A의 왼쪽 서브 트리의 왼쪽 서브 트리에 노드가 추가됨으로 해서 발생한다. 아래의 그림을 보자. LL회전은 노드들을 오른쪽으로 회전시키면 된다. 회전을 시키면 아래와 같다. 2. RR회전 ..
-
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 ]와 같이 경사 트리..