보완된(균형 잡힌)이진 탐색 트리의 구현 - 12장(2)

보완된(균형 잡힌)이진 탐색 트리의 구현

기존에 구현 했던 이진 탐색 트리에 추가적으로 구현을 한다.

 

리밸런싱 관련된 기능 추가와 BSTInsert 메소드와 BSTRemove 메소드를 수정.

 

먼저 리밸런싱에 필요한 도구들을 정의한다.

1. 왼쪽 서브 트리의 높이와 오른쪽 서브 트리의 높이를 구하여 불균형 여부를 판단하기 위한 함수.

-> int GetHeight(Node<T>* bst)

template <typename T>
int BinarySearchTree<T>::GetHeight(Node<T>* bst)
{
	int leftH; // left 높이
	int rightH; // right 높이

	if (bst == nullptr)
		return 0;

	// nullptr을 반환하므로 int형으로 형변환.
	leftH = GetHeight(bst->GetLeftSubTreeOrNull()); 
	rightH = GetHeight(bst->GetRightSubTreeOrNull()); 

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

반환에서 조금 헷갈릴 수 있는데.

그림을 그려보면 쉽게 이해가 된다.

 

먼저 이 GetHeight함수는 높이라는 값 '하나'만을 반환한다는 것을 인지해야한다.

(즉 1이라는 노드를 넘겼다면 위 그림의 높이는 3이므로 3을 리턴한다)

 

먼저 leftH에 GetHeight함수를 재귀적으로 호출하고 있다. (왼쪽 서브트리를 넘기면서)

1,2,3까지가고 다음 nullptr을 만날 때 if (bst == nullptr)일 때 0을 반환한다.

 

1. leftH는 0을 저장. (3의 노드로 돌아옴 )

2. 바로 이어서 3의 오른쪽 자식 주소를 넘기면서 rightH에 0을 저장. (3의 노드로 돌아옴 )

3. 둘 다 0이니 else인 rightH + 1을 리턴한다. (3 노드를 호출한 2 노드로 돌아감. leftH에는 1이 저장된다.)

4. 2노드에서 다시 rightH의 재귀함수 호출. 2의 오른쪽 자식노드는 0이므로 rightH + 1을 리턴해 rightH도 1이된다.

(leftH도 1 rightH도 1 else부분인 rightH + 1을 해 2를 리턴. 1노드로 돌아간다)

5. 1 노드에서는 leftH가 2가 저장. rightH에 대입하는 GetHeight함수 이어서 호출.

6. 4가 저장된 노드로 가 leftH에 대입하는 GetHeight함수 이어서 호출. 바로 0을 리턴.

7. 바로 이어서 rightH에 대입하는 GetHeight함수 이어서 호출. 바로 0을 리턴.

8. 4가 저장된 노드의 함수는 if문을 비교하고 leftH, rightH 둘다 0이므로 rightH + 1을 리턴.

9. 다시 1이 저장된 노드의 함수부분으로 돌아와 leftH는 2. rightH는 1. leftH가 더 크므로 leftH + 1을 리턴하고 종료.(3)

 

 

2. 균형 인수를 계산해 반환하는 함수

-> int GetHeightDiff(Node<T>* bst)

template <typename T>
int BinarySearchTree<T>::GetHeightDiff(Node<T>* bst)
{
	int lsh; // left sub tree height
	int rsh; // right sub tree height

	if (bst == nullptr)
		return 0;

	lsh = GetHeight(bst->GetLeftSubTreeOrNull());
	rsh = GetHeight(bst->GetRightSubTreeOrNull());
	return lsh - rsh;
}

높이를 구하는 함수 덕에 쉽게 균형 인수를 구할 수 있다.

 

위 그림으로 따진다면,

1이 저장된 노드를 넘겼을때 lsh에는 2가 저장된 노드를 넘겨 높이 2를 구하게 될것이고.

rsh에는 4가 저장된 노드를 넘겨 높이 1를 구하게 된다.

 

 

3. LL회전과 RR회전의 함수를 정의

앞서 이론적으로 설명한 내용을 근거로 구현하면 된다.

먼저 LL회전의 함수

-> Node<T>* RotateLL(Node<T>* bst)

template <typename T>
Node<T>* BinarySearchTree<T>::RotateLL(Node<T>* bst)
{
	// 각각 pNode와 cNode가 필요하다!
	Node<T>* pNode;
	Node<T>* cNode;

	// 적절한 위치 가르키기!
	pNode = bst;
	cNode = pNode->GetLeftSubTreeOrNull();

	pNode->ChangeLeftSubTree(cNode->GetRightSubTreeOrNull()); // cNode의 T3(오른쪽 자식 노드)을 고려!
	cNode->ChangeRightSubTree(pNode); // 회전!

	return cNode; // LL회전으로 인해 변경된 루트 노드의 주소 값 반환 (서브트리 기준으로도 포함)

}

이어서 RotateRR함수.

-> Node<T>* RotateRR(Node<T>* bst)

template <typename T>
Node<T>* BinarySearchTree<T>::RotateRR(Node<T>* bst)
{
	// 각각 pNode와 cNode가 필요하다!
	Node<T>* pNode;
	Node<T>* cNode;

	// 적절한 위치 가르키기!
	pNode = bst;
	cNode = pNode->GetRightSubTreeOrNull();

	pNode->ChangeRightSubTree(cNode->GetLeftSubTreeOrNull()); // cNode의 T3(왼쪽 자식 노드)을 고려!
	cNode->ChangeLeftSubTree(pNode); // 회전!

	return cNode; // LL회전으로 인해 변경된 루트 노드의 주소 값 반환 (서브트리 기준으로도 포함)

}

 

 

4. LR회전과 RL회전의 함수를 정의

 

LR회전과 RL회전을 다시 정리.

1. LR회전 -> 부분 RR회전을 한 후, LL상태로 만든 다음 LL회전.

2. RL회전 -> 부분 LL회전을 한 후, RR상태로 만든 다음 RR회전.

 

그리고 LL회전과 RR회전에서 이미 T3(회전할 때 겹치는 노드)의 고려가 되어있으므로

여기서 T3에 대한 고민을 하지 않아도 된다.

 

먼저 LR회전

-> Node<T>* RotateLR(Node<T>* bst) 

template <typename T>
Node<T>* BinarySearchTree<T>::RotateLR(Node<T>* bst)
{
	// 각각 pNode와 cNode가 필요하다!
	Node<T>* pNode;
	Node<T>* cNode;

	// 적절한 위치 가르키기!
	pNode = bst;
	cNode = pNode->GetLeftSubTreeOrNull();


	pNode->ChangeLeftSubTree(RotateRR(cNode)); // 부분적 RR회전.
	return RotateLL(pNode); // LL회전!

}

 

위 그림을 예로들어 코드를 설명해보면 중요하게 봐야할 코드는

pNode->ChangeLeftSubTree(RotateRR(cNode)); // 부분적 RR회전.

return RotateLL(pNode);

현재 pNode는 5. cNode는 1이다. 먼저 위 그림의 LR상태를 LL상태로 만들기위해 부분적 RR회전을 해야한다.

그러기위해 RotateRR에 cNode를 넘기는것이고. 부분 RR회전을 통해 LL상태가 되어 3이 pNode의 왼쪽자식이 된다.

 

위 그림 처럼 재연결을 하게 된다. 그런다음 LL회전을 진행하기 위해 RotateLL함수를 호출하며 바로 리턴하는 것.

 

그 다음 RL회전

-> Node<T>* RoateRL(Node<T>* bst)

template <typename T>
Node<T>* BinarySearchTree<T>::RotateLR(Node<T>* bst)
{
	// 각각 pNode와 cNode가 필요하다!
	Node<T>* pNode;
	Node<T>* cNode;

	// 적절한 위치 가르키기!
	pNode = bst;
	cNode = pNode->GetRightSubTreeOrNull();


	pNode->ChangeRightSubTree(RotateLL(cNode)); // 부분적 LL회전.
	return RotateRR(pNode); // RR회전!

}

RL회전도 LR회전의 반대.

 

 

5. Rebalance 함수 정의

-> Node<T>* Rebalance(Node<T>* node);

 

루트노드를 기준으로 리밸런싱을 진행한다.

(항상 이진 탐색 트리가 노드가 들어갈때 루트노드부터 비교하며 들어가므로)

template <typename T>
Node<T>* BinarySearchTree<T>::Rebalance(Node<T>* node)
{
	int hDiff = GetHeightDiff(node);

	//균형인수가 +2(양수) 이상이면 LL상태 혹은 LR상태.
	if (hDiff >= 2) // 왼쪽 서브 트리 방향으로 높이가 2 이상 크다면.
	{
		if (GetHeightDiff(node->GetLeftSubTreeOrNull()) > 0) // 양수값이 나온다면 LL상태
			node = RotateLL(node);
		else // 음수가 나온다면 LR상태.
			node = RotateLR(node);
	}
	// 균형인수가 -2(음수) 이하라면 RR상태 혹은 RL상태.
	if (hDiff <= -2) // 오른쪽 서브 트리 방향으로 높이가 2 이상 크다면
	{
		if (GetHeightDiff(node->GetRightSubTreeOrNull()) < 0) // 음수값이 나온다면 RR상태
			node = RotateRR(node);
		else // 양수값이 나온다면 RL상태.
			node = RotateRL(node);
	}
	return node; 
}

 

hDiff변수를 통해 균형인수를 구해온다. 

그리고 양수 +2 이상인지, 음수 -2이하인지를 체크하고 또 내부에서 무슨 상태인지를 밑에 그림처럼 판단한다.

 

 

6. BSTInsert 메소드와 BSTRemove 메소드를 수정

 

먼저 BSTRemove 메소드 부터 확인한다.

Remove는 간단하다. 

template <typename T>
Node<T>* BinarySearchTree<T>::BSTRemove(const T& target)
{
	.....
	m_root = Rebalance(m_root); // 삭제후 리밸런싱!
	return dNode; // 삭제대상의 반환

}

마지막에 삭제를 진행한 뒤. 루트노드를 대상으로 리밸런싱을 진행하면 된다.

(균형인수가 안정된다면 그대로 m_root를 반환할 것이고. 만약 리밸런싱이 진행된다면 회전하고 난 후 새로운 루트노드의 주소를 반환 받아야한다.)

 

그 다음 BSTInsert 메소드.

함수의 원형과 내부 코드가 바뀐다.

-> Node<T>* BSTInsert(Node<T>** root, const T& data)

template <typename T>
Node<T>* BinarySearchTree<T>::BSTInsert(Node<T>** root,const T& data)
{

	if (*root == nullptr) // 노드생성
	{
		*root = new Node<T>(data);
		if (m_root == nullptr) // 처음 생성이라면 루트멤버 저장.
			m_root = *root;
	}
	else if (data < (*root)->GetData())
	{
		BSTInsert(&((*root)->m_left), data);
		*root = Rebalance(*root);
	}
	else if (data > (*root)->GetData())
	{
		BSTInsert(&((*root)->m_right), data);
		*root = Rebalance(*root);
	}
	else
		return nullptr; // 키 중복 허용 금지.
	
	return *root;
}

앞서 구현한 BSTInsert를 대상으로 Remove함수처럼 마지막에 리밸런싱 함수만 호출하고 끝낼 수는 없다.

왜냐하면 삽입 후 노드가 들어갈 자리에 안착하게 되고나서 루트 노드를 대상으로만 균형 인수를 체크하기에

위와 같이 된 트리에서

이런식으로 6 노드가 들어가지만 루트노드는 균형이 깨지지 않았기에 리밸런싱이 되지 않는다.

하지만 그 오른쪽 자식 노드인 4라는 노드는 균형이 깨져있는상태.

 

그렇기에 재귀를 통해서 노드를 삽입할 때, 노드간의 Key값을 비교 하면서 자리를 찾아가고.

재귀의 특성상(자리를 찾아가는 과정 m_left,m_right를 넘기다보면 nullptr을 만남 -> 자리를 찾음)

노드를 생성하고 난 후, 생성된 노드의 부모부터 재귀가 종료되면서 리밸런싱을 진행하는 코드.

 

실행결과. (1 ~ 6까지의 Key값을 넣은 AVL트리의 전위 순회)

int main()
{

	BinarySearchTree<int> avl;
	for (int i = 1; i <= 6; ++i)
		avl.BSTInsert(avl.GetdbRoot(), i);
	
	avl.BSTPrintAllData(avl.GetRoot());

	return 0;
}