[C++ 자/알 Note] 이진탐색트리

이진탐색트리

이진탐색에 최적화된 자료구조는 트리이다

최대 자식을 두 개를 가질 수 있는 트리는 이진트리라고 한다

이러한 이진트리를

N의 왼쪽 서브트리에 있는 모든 노드의 값은 N의 값보다 작고

N의 오른쪽 서브트리에 있는 모든 노드의 값은 N의 값보다 크다는

탐색 속성을 만족시킨 것을 이진탐색트리라고 한다

 

이진탐색트리 시간복잡도

균형이 안 맞는 경우에는

삽입/삭제/탐색에서 최악인 O(N)이 발생할 수 있다

반면, 어느 정도 균형이 맞혀진 경우에는

삽입/삭제/탐색에서 O(logN)이 발생한다

 

전위/중위/후위 순회

부모의 순서가 핵심이다

전위순회는 부모노드 -> 왼쪽 자식 -> 오른쪽 자식

중위순회는 왼쪽 자식 -> 부모노드 -> 오른쪽 자식

후위순회는 왼쪽 자식 -> 오른쪽 자식 -> 부모노드

전위

중위

후위

 

 

이진탐색트리 구현 주의사항

- Max/Min 기능

최대값을 찾는 방법은 계속 오른쪽 자식들을 타고 가면 된다

최소값을 찾는 방법은 계속 왼쪽 자식들을 타고 가면 된다 

 

- Next 기능

Next 함수는 본인 다음 순서로 값이 큰 노드를 의미한다

노드에 오른쪽 자식이 있다면, 오른쪽 자식들 중 Min을 찾으면 된다

노드에 오른쪽 자식이 없는 경우는 나 자신보다 큰 부모를 찾으면 된다

 

- Delete 기능

전반적인 흐름은 Next 값을 가져와서 복사하거나 참조하고

기존 자리는 재귀적으로 삭제함수를 호출시키면 된다

 

- Replace 기능

Replace는 서브트리 교체 작업을 진행한다

 

- Delete with Replace 

child가 없거나 오른쪽만 있는 경우는 해당 오른쪽 노드와 Replace만 진행하면 된다

(child가 없는 경우는 nullptr(해당 오른쪽 노드)와 Replace가 진행되도록 구현) 

child가 왼쪽만 있는 경우는 해당 왼쪽 노드와 Replace만 진행하면 된다

child가 모두 있는 경우는 새로운 노드를 만들어주고 재귀적으로 Delete를 호출하면 된다

 

이진탐색트리 구현

struct Node
{
	Node* parent = nullptr;
	Node* left = nullptr;
	Node* right = nullptr;
	int		key = {};
};

class BinarySearchTree
{
public:
	void	Print() { Print(_root, 10, 0); }
	void	Print(Node* node, int x, int y);
	void	Print_Inorder() { Print_Inorder(_root); }
	void	Print_Inorder(Node* node);

	Node* Search(Node* node, int key);
	Node* Search2(Node* node, int key);

	Node* Min(Node* node);
	Node* Max(Node* node);
	Node* Next(Node* node);

	void	Insert(int key);
	void	Delete(int key);
	void	Delete(Node* node);
	void	Replace(Node* u, Node* v);

private:
	Node* _root = nullptr;
};

 

void BinarySearchTree::Print_Inorder(Node* node)
{
	// 전위 순회 (preorder traverse)
	// 중위 순회 (inorder)
	// 후위 순회 (postorder)
	if (node == nullptr)
		return;

	cout << node->key << endl;
	Print_Inorder(node->left);
	Print_Inorder(node->right);
}

Node* BinarySearchTree::Search(Node* node, int key)
{
	// 재귀함수를 이용한 탐색방법

	if (node == nullptr || key == node->key)
		return node;

	if (key < node->key)
		return Search(node->left, key);
	else
		return Search(node->right, key);
}

Node* BinarySearchTree::Search2(Node* node, int key)
{
	// 반복문을 이용한 탐색방법

	while (node && key != node->key)
	{
		if (key < node->key)
			node = node->left;
		else
			node = node->right;
	}

	return node;
}

Node* BinarySearchTree::Min(Node* node)
{
	while (node->left)
		node = node->left;

	return node;
}

Node* BinarySearchTree::Max(Node* node)
{
	while (node->right)
		node = node->right;

	return node;
}

Node* BinarySearchTree::Next(Node* node)
{
	if (node->right)
		return Min(node->right);

	Node* parent = node->parent;
	while (parent && node == parent->right)
	{
		node = parent;
		parent = parent->parent;
	}

	return parent;
}

void BinarySearchTree::Insert(int key)
{
	Node* newNode = new Node();
	newNode->key = key;

	if (_root == nullptr)// 루트노드를 생성하는 경우
	{
		_root = newNode;
		return;
	}

	Node* node = _root;
	Node* parent = nullptr;

	while (node)// 본인 자리 찾기
	{
		parent = node;
		if (key < node->key)
			node = node->left;
		else
			node = node->right;
	}

	// 노드 구성
	newNode->parent = parent;

	if (key < parent->key)
		parent->left = newNode;
	else
		parent->right = newNode;
}

void BinarySearchTree::Delete(int key)
{
	Node* deleteNode = Search(_root, key);
	Delete(deleteNode);
}

void BinarySearchTree::Delete(Node* node)
{
	if (node == nullptr)
		return;

	if (node->left == nullptr)// child가 없거나 오른쪽만 있는 경우
		Replace(node, node->right);

	else if (node->right == nullptr)// child가 왼쪽만 있는 경우
		Replace(node, node->left);

	else// child가 모두 있는 경우
	{
		// 다음 데이터 찾기
		Node* next = Next(node);
		node->key = next->key;
		Delete(next);
	}
}

void BinarySearchTree::Replace(Node* u, Node* v)// u 서브트리를 v 서브트리로 교체
{
	if (u->parent == nullptr)
		_root = v;
	else if (u == u->parent->left)
		u->parent->left = v;
	else
		u->parent->right = v;

	if (v)
		v->parent = u->parent;

	delete u;// u 서브트리 삭제
}