탐색(Search) 2

이 글은 윤성우 저 - "윤성우의 열혈 자료구조"를 공부하고 정리하여 작성하였습니다.

1. 균형 잡힌 이진 탐색 트리: AVL 트리의 이해

⚠️ 이진탐색 트리의 문제점과 AVL 트리

• 이진 탐색 트리의 탐색 연산은 O(logn)의 시간 복잡도를 가짐
• 하지만 균형이 맞지 않을수록 O(n)에 가까운 시간 복잡도를 보임.
• 이진 탐색 트리의 단점을 해결한 트리를 ‘균형 잡힌 이진 트리’라 하며 그 종류는 대략 이렇다
  • AVL 트리
  • 2-3 트리
  • 2-3-4 트리
  • Red-Black 트리
  • B 트리

⚖️ 자동으로 균형을 잡는 AVL 트리와 균형 인수(Balance Factor)

• Adelson-Velskii와 Landis에 의해 고안되어 이름도 이들의 이름을 땄음.
• 노드가 추가될 때, 그리고 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 트리
• 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이

🔧 리밸런싱이 필요한 첫 번째 상태와 LL 회전

• ChangeRightSubTree(sNode, pNode)
• 일반화

ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
ChangeRightSubTree(cNode, pNode);

 

🔧 리밸런싱이 필요한 두 번째 상태와 RR 회전

ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
ChangeLeftSubTree(cNode, pNode);

 

🔧 리밸런싱이 필요한 세 번째 상태와 LR 회전

• LR 상태는 RR회전을 통해서 LL 상태가 되게 할 수 있음

🔧 리밸런싱이 필요한 네 번째 상태와 RL 회전

• 자식 노드와 연결된 방향이 LR 상태와 반대인 것 외에는 차이가 없음
• 부분적 LL 회전에 이어서 RR 회전을 진행

 

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

➕ 확장 포인트

• 균형이 깨지는 순간은 삽입과 삭제에서 일어나기 때문에 이 두 과정을 확장해야 함
  • BSTInsert 함수 : 트리에 노드를 추가
  • BSTRemove 함수: 트리에서 노드를 제거

void BSTInsert(BTreeNode ** pRoot, BSTData data)
{
	...
	Rebalance(Root);
}

BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target)
{
	...
	Rebalance(pRoot);
	return dNode;
}

 

🔍 추가적인 도구들 1: 트리가 균형을 이루는지를 확인

• 불균형 여부는 루트 노드를 기준으로 판단

// 트리의 높이를 계산하여 반환
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;
}

int GetHeightDiff(BTreeNode *bst)
{
	int lsh;
	int rsh;
	
	if(bst == NULL)
		return 0;
	
	lsh = GetHeight(GetLeftSubTree(bst));
	rsh = GetHeight(GetRightSubTree(bst));
	return lsh - rsh;
}

 

🔍 추가적인 도구들 2: LL 회전, RR 회전

• LL 회전

BTreeNode * RotateLL(BTreeNode * bst)
{
	BTreeNode * pNode;
	BTreeNode * cNode;
	
	// pNode와 cNode가 LL회전을 위해 적절한 위치를 가리키게 한다.
	pNode = bst;
	cNode = GetLeftSubTree(pNode);
	
	// 실제 LL회전을 담당하는 두 개의 문장
	ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
	ChangeRightSubTree(cNode, pNode);
	
	// LL회전으로 인해서 변경된 루트 노드의 주소 값 반환
	return cNode;
}

• RR 회전

BTreeNode * RotateRR(BTreeNode * bst)
{
	BTreeNode * pNode;
	BTreeNode * cNode;
	
	// pNode와 cNode가 RR회전을 위해 적절한 위치를 가리키게 한다.
	pNode = bst;
	cNode = GetRightSubTree(pNode);
	
	// 실제 RR회전을 담당하는 두 개의 문장
	ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
	ChangeLeftSubTree(cNode, pNode);
	
	// RR회전으로 인해서 변경된 루트 노드의 주소 값 반환
	return cNode;
}

 

🔍 추가적인 도구들 3: LR 회전, RL 회전

• LR 회전 & RL 회전

BTreeNode * RotateLR(BTreeNode * bst)
{
	BTreeNode * pNode;
	BTreeNode * cNode;
	
	// pNode와 cNode가 LR 회전을 위해 적절한 위치를 가리키게 한다.
	pNode = bst;
	cNode = GetLeftSubTree(pNode);
	
	// 실제 LR 회전을 담당하는 두 개의 문장
	ChangeLeftSubTree(pNode, RotateRR(cNode)); // 부분적 RR 회전
	return RotateLL(pNode);  // LL 회전
}

BTreeNode * RotateRL(BTreeNode * bst)
{
	BTreeNode * pNode;
	BTreeNode * cNode;
	
	// pNode와 cNode가 RL 회전을 위해 적절한 위치를 가리키게 한다.
	pNode = bst;
	cNode = GetRightSubTree(pNode);
	
	// 실제 RL 회전을 담당하는 두 개의 문장
	ChangeRightSubTree(pNode, RotateLL(cNode)); // 부분적 LL 회전
	return RotateRR(pNode);  // RR 회전
}

 

🔍 추가적인 도구들 4: Rebalance 함수

BTreeNode * Rebalance(BTreeNode ** pRoot)
{
	int hDiff = GetHeightDiff(*pRoot);  // 균형 인수 계산
	
	// LL or LR 상태
	if(hDiff > 1)
	{
		if(GetHeightDiff(GetLeftSubTree(*pRoot)) > 0) // 왼쪽 서브트리가 왼쪽으로 치우쳐 있다면
			*pRoot = RotateLL(*pRoot);
		else
			*pRoot = RotateLR(*pRoot);
	}
	// RR or RL 상태
	if(hDiff < -1)
	{
		if(GetHeightDiff(GetRightSubTree(*pRoot)) < 0) // 오른쪽 서브트리가 오른쪽으로 치우쳐 있다면
			*pRoot = RotateRR(*pRoot);
		else
			*pRoot = RotateRL(*pRoot);
	}
	
	return *pRoot;
}

 

자료

• 윤성우의 열혈 자료구조 (윤성우 저, 2023.10)