균형
-
4. AVL 트리의 Rebalance 함수C 자료구조/7. Binary Search Tree Advanced - AVLTRee 2020. 6. 19. 23:06
앞에서 균형 인수는 다음과 같이 정의한다고 했다. '균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리 높이' 그리고 트리에서 트리의 높이를 구하는 함수 또한 만들었다. 1. 균형 인수를 구하는 함수 2. 트리의 균형 여부를 판단하고, 트리를 균형 트리로 만드는 함수 그리고, 트리가 비 균형 상태일 때, 균형 상태로 만들어주는 함수를 Rebalance 라 하고 이를 만들어 보자. 우선 트리가 균형 상태 인지 아닌지를 먼저 확인을 한다. 비 균형 상태이면, 균형 상태로 만들면 된다. 앞에서 말했듯이, 균형이 깨지는 경우는 4가지의 경우가 있다고 했다. 각 경우를 파악하고, 각 경우 맞게 회전시키면 된다. 그리고 앞에서, 균형을 이룬 이진 탐색 트리에서 균형 상태가 깨지는 이유는 노드의 삽입과 삭제 ..