리벤런싱에 필요한 도구들의 정의: 균형을 이루고 있는가?

“이거 리벨런싱이 필요한 불균형 상태야?”

물론 불균형의 여부는 ‘루트 노드’를 기준으로 판단한다. 따라서 위의 질문에 답을 하기 위해서는다음 질문에 답을 할 수 있어야 한다.

“왼쪽 서브 트리의 높이는 어떻게 되나요? 그리고 오른쪽 서브 트리의 높이는요?”

int GetHeight(BTreeNode *bst)
{
	int leftH;
	int rightH;
	
	if (bst == NULL)
		return 0;
	
	leftH = GetHeight(GetLeftSubTree(bst));
	rightH = GetHeight(GetRightSubTree(bst));
	
	if(leftH > rightH)
		return leftH + 1;
	else
		return rightH + 1;
}