균형 잡힌 이진 탐색 트리
: AVL 트리의 구현
이렇게 구현과 이해를 구분한 이유는 이해만으로도 매우~ 의미 있기에 그랬다!
그러니 이제 이 의미있는 것을 구현해보자!
AVL 트리를 어떻게 구현할 것인가?
이또한 이진탐색트리이므로
- BinaryTree3.h
- BinaryTree3.c
- BinarySearchTree2.h
- BinarySearchTree2.h
를 확장해서 구현하자 !
그럼 어떤 파일을 확장해야할까?
BinaryTree3 는 이미 2차례 확장을 해왔고 AVL트리를 구현하는데 지장이 업다.
그렇다면 BinartSearchTree2.c를 변경해야하는가!?
정답이다!!
이 소스코드에 리밸런싱 기능만 추가하면 이것이 바로 AVL트리가 되기 때문이다!
참고로 함수를 추가한다는 의미가 아니고!
노드의 추가 및 삭제 시 자동으로 리밸런싱이 진행되도록 그 기능을 확장하겠다는것이다.
이제 다음 두 파일을 추가 생성하여 리밸런싱을 진행하는데 필요한 도구들을 선언하고 정의하자 !
- AVLReBalance.h,c
그러므로!
BinarySearchTree3.c 에 담길 AVL트리는 위의 도구들을 이용해서 리밸런싱을 진행하는 형태가 될것이다!!
이렇게 리밸런싱 도구를 별도의 파일로 구분해놓으면 코드 분석하는데 도움이 된다!
BinarySearch2.c의 확장 포인트
생각을 해보자!
이진 탐색 트리가 언제 균형이 깨질까?
탐색의 과정?
아니다!
바로
삽입과 삭제의 과정에서 발생한다
따라서 삽입함수와 삭제함수를 확장해야한다!!
균형을 재조정하는 함수의 이름을 Rebalance라고 했을 때, 다음과 같은 방식으로 확장되어야 한다.
위의 리밸런싱 함수를 보면 인자로 루트노드의 정보를 전달함을 알 수 있다!
이는 트리의 불균형 여부를 루트 노드를 기준으로 확인해야 하기 때문이다.
실제로 우리는 균형의 재조정이 필요한지 살펴보고 리밸런싱을 진행하는!!!
Rebalance 함수를 정의해야한다!!
리밸런싱에 필요한 도구들의 정의 : 균형을 이루고 있는가?
리밸런싱에 앞서 고민해야하는 부분은
"이거 리밸런싱이 필요한 불균형 상태야??" 이다.
물론 불균형의 여부는 위에 말했듯이 "루트 노드"를 기준으로 판단한다.
따라서 우리는 위의 질문에 답하기 위해 다음 질문에 답을 할수 있어야한다.
"왼쪽 서브 트리의 높이는 어떻게되나요? 오른쪽은요?"
루트 노드의 왼쪽 - 오른쪽 서브트리를 통해 불균형 여부를 확인할 수 있기 떄문이다.
따라서 첫 번째 도구로 다음 함수를 정의하여야한다!
트리는 단말 노드의 수만큼 경로가 나뉘기 때문에, 트리의 높이는 그 중에서 가장 깊이 뻗은 경로를 기준으로 결정되기ㄷ 때문에 재귀적인 형태를 뛰어야한다.
GetHeight 함수가 호출될 때마다 높이를 1씩 더해가는 구조로 정의되어 있다.
그리고 왼쪽 서브트리와 오른쪽 서브트릐 높이를 비교하여 큰 값이 반환 되도록 하고 있어서 트리의 모든 경로 중 가장 깊이 뻗은 경로의 높이를 반환하게 한다.
이렇게 높이를 계산하는 함수를 만들었지만!
균형 인수를 계산해서 반환하는 도구가 있다면 사용하기 편할것이다!
그러므로 다음과 같은 함수를 정의했다.
어떤가!
그저 왼쪽 서브트리의 높이를 구하고 오른쪽 서브트리의 높이를 구하고 빼는 도구를 만들었다!
이로써 불균형의 여부를 판단하는 필요한 도구는 모두 마련됐다.
이제 다음 포스트에서 LL/RR 회전등을 위한 도구를 마련해보자 !
