CH12-2 균형잡힌 이진탐색트리 : AVL트리의 구현(3)

12-2. 균형 잡힌 이진 탐색 트리: AVL 트리의 구현 ③

교재에서 보충하지 못했던 부분들을 여기서 설명하겠다.

우리는 전에 리밸런싱 함수를 만들고나서 이렇게 추가할 계획이었다.(추가후, 제거후) 그런데 이렇게 추가하면 사실 모든 밸런스가 무너지는 현상이 다 커버되는건 아니다!

이걸 이렇게 바꿔야 한다.

왜냐하면 리밸런싱 과정에서 루트노드가 변경될수도 있기 때문이다.

인서트와 리무브 함수는 루트노드의 주소를 가지고 있는 이중포인터 변수를 인자로 받는다. 리밸런싱 과정에서 루트노드가 바뀌는 케이스에서 가장 위의 그림처럼 Rebalance(pRoot)만 하면 함수밖으로 나왔을때 루트노드가 바뀐 트리는 함수와 함께 사라진다. 실제 리밸런싱된 이진탐색트리로 갱신을 위해선 포인터 변수인 pRoot의 실제 노드를 갱신해야 하고, 이를 위해선 이중포인터로 인자를 받아야 한다.

여기까지가 교재의 내용이었다.

교재처럼 추가하면 1,2,3,4,5…처럼 정렬된 데이터를 추가하면 사실 다음의 결과가 나온다!

즉 5의 입장에서는 균형잡힌듯 보이지만 사실 그 이하 노드는 전부 불균형한 상태이다.

• 강의를 따라기전에, main함수 실행결과 오류가 생겨서 잡고 넘어갔다. Rebalance만 하면 자식이 NULL인 이상한 루트노드만 반환되는 현상이 있어서 코드를 하나하나 디버그했더니, Rebalance함수에 이런 문제가 있었다.

BTreeNode* Rebalance(BTreeNode** pRoot)
{
	int hDiff = GetHeightDiff(*pRoot); // Get a Diff of *pRoot

	if (hDiff > 1) // it need to Rotate LL or LR
	{
		if (GetHeightDiff(GetLeftSubTree(*pRoot)) > 0)
			RotateLL(*pRoot); //문제의 부분
		else
			RotateLR(*pRoot); //문제의 부분
	}
	
	if (hDiff < -1) // it need to Rotate RR or RL
	{
		if (GetHeightDiff(GetRightSubTree(*pRoot)) < 0)
			RotateRR(*pRoot); //문제의 부분
		else
			RotateRL(*pRoot); //문제의 부분
	}

	return *pRoot;
}

무엇이 이상할까? Rotate~ 함수들은 회전이후 새로 생긴 루트노드의 주소를 반환한다. 그런데 보면 그 주소를 받는 변수가 없다!

그래서 가장 마지막에 *pRoot는 주소가 갱신되기 이전에 루트노드주소를 반환하는데, 그 루트노드는 이미 회전을 통해 다른 노드의 말단으로 갔으므로 자식이 NULL이다. 따라서 이렇게 반환된 루트노드를 차례차례 꺼내오면 결국 NULL을 자식으로 갖는 이상한 트리 하나를 최종적으로 main에서 반환받게 되는 것이다 따라서

BTreeNode* Rebalance(BTreeNode** pRoot)
{
	int hDiff = GetHeightDiff(*pRoot); // Get a Diff of *pRoot

	if (hDiff > 1) // it need to Rotate LL or LR
	{
		if (GetHeightDiff(GetLeftSubTree(*pRoot)) > 0)
			*pRoot = RotateLL(*pRoot); //수정된 부분
		else
			*pRoot = RotateLR(*pRoot); //수정된 부분
	}
	
	if (hDiff < -1) // it need to Rotate RR or RL
	{
		if (GetHeightDiff(GetRightSubTree(*pRoot)) < 0)
			*pRoot = RotateRR(*pRoot); //수정된 부분
		else
			*pRoot = RotateRL(*pRoot); //수정된 부분
	}

	return *pRoot;
}

처럼 *pRoot가 갱신될 수 있게 해야한다.