열혈 자료구조 - 12.2 균형 잡힌 이진 트리 : AVL 트리의 구현

AVL 트리의 구현

- 두 서브 트리의 높이 차(균형 인수를 구하는 함수)

int GetHeightDiff(BTreeNode * bst)
{
	int lsh;    // 좌측 트리의 높이
	int rsh;    // 우측 트리의 높이

	if(bst == NULL) {
		return 0;
	} 
    
	lsh = GetHeight(GetLeftSubTree(bst));
	rsh = GetHeight(GetRightSubTree(bst));

	return lsh - rsh;
}

- 서브트리의 높이를 구하는 함수

int GetHeight(BTreeNode * bst) 
{
	int leftH;		// left height
	int rightH;		// right height

	if(bst == NULL) {
		return 0;
	}
    
	// 왼쪽 서브 트리 높이를 재귀적으로 계산
	leftH = GetHeight(GetLeftSubTree(bst));

	// 오른쪽 서브 트리 높이를 재귀적으로 계산
	rightH = GetHeight(GetRightSubTree(bst));

	// 큰 값의 높이를 반환한다.
	if(leftH > rightH) { return leftH + 1; }
	else               { return rightH + 1; }
}

- LL 회전

BTreeNode * RotateLL(BTreeNode * bst)
{
	BTreeNode * pNode;
	BTreeNode * cNode;

	pNode = bst;
	cNode = GetLeftSubTree(pNode);

	// 회전하는 부분
	ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
	ChangeRightSubTree(cNode, pNode);
    
	return cNode;
}

- RR 회전

BTreeNode * RotateRR(BTreeNode * bst)
{
	BTreeNode * pNode;
	BTreeNode * cNode;

	pNode = bst;
	cNode = GetRightSubTree(pNode);

	// 회전하는 부분
	ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
	ChangeLeftSubTree(cNode, pNode);
	return cNode;
}

- LR 회전

// LR 회전
BTreeNode * RotateLR(BTreeNode * bst)
{
	BTreeNode * pNode;
	BTreeNode * cNode;

	pNode = bst;
	cNode = GetLeftSubTree(pNode);
	
    	// RR 회전을 하고 다시 LL 회전한 결과를 반환
	ChangeLeftSubTree(pNode, RotateRR(cNode));   // 부분적 RR 회전
	return RotateLL(pNode);     // LL 회전
}

- RL 회전

BTreeNode * RotateRL(BTreeNode * bst)
{
	BTreeNode * pNode;
	BTreeNode * cNode;

	pNode = bst;
	cNode = GetRightSubTree(pNode);

	ChangeRightSubTree(pNode, RotateLL(cNode));   // 부분적 LL 회전
	return RotateRR(pNode);     // RR 회전
}

- 재조정 함수

    -> 각 상태에 맞게 적절한 회전 함수를 호출

BTreeNode * Rebalance(BTreeNode * pRoot)
{
	int hDiff = GetHeightDiff(pRoot);

	if(hDiff > 1)     // 왼쪽 서브 트리 방향으로 높이가 2 이상 크다면(LL, LR)
	{
		if(GetHeightDiff(GetLeftSubTree(*pRoot)) > 0)	// 좌측 서브트리를 봤을 때
			*pRoot = RotateLL(*pRoot);				// 0보다 크면 LL 상태
		else
			*pRoot = RotateLR(*pRoot);				// 0보다 작으면 LR 상태
	}
	
	if(hDiff < -1)     // 오른쪽 서브 트리 방향으로 2 이상 크다면(RR, RL)
	{
		if(GetHeightDiff(GetRightSubTree(*pRoot)) < 0)		// 우측 서브트리를 봤을 떄
			*pRoot = RotateRR(*pRoot);				// 0보다 작으면 RR 상태
		else
			*pRoot = RotateRL(*pRoot);				// 0보다 크면 RL 상태
	}
	
	return *pRoot;
}

- 기존 이진 탐색 트리의 Insert와 Delete부분에 조정하는 함수를 추가

void BSTInsert(BTreeNode * pRoot, BSTData data)
{
	if (pRoot == NULL)
	{
		pRoot = MakeBTreeNode();
		SetData(pRoot, data);
	}
	else if (data < GetData(pRoot))
	{
		BSTInsert(pRoot->left), data);
		pRoot = Rebalance(pRoot);
	}
	else if (data > GetData(pRoot))
	{
		BSTInsert(pRoot->right), data);
		pRoot = Rebalance(pRoot);
	}
	else
	{
		return NULL; // 키의 중복을 허용하지 않는다.
	}
	return pRoot;
} // 노드를 추가하면서 조정해야 올바른 결과가 나옴

BTreeNode * BSTRemove(BTreeNode * pRoot, BSTData target)
{
	// 삭제 연산 진행
    
    pRoot = Rebalance(pRoot);
	return dNode;
}