[자료구조] 이진 탐색 트리

KANTAM·2021년 9월 7일

이진트리 자료구조 트리

Data Structure

목록 보기

6/8

이진 탐색 트리

각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지니 노드들로 이루어져 있다.
중복된 노드가 없어야 한다.
왼쪽 서브트리, 오른쪽 서브트리 또한 이진 탐색 트리이다.

중위순회

이진 탐색 트리를 순회할 때는 중위순회 방식을 쓴다. 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 순서.
중위순회를 하면 이진 탐색 트리 내에 있는 모든 값들을 정렬된 순서대로 탐색한다.

중위순회 : 10 -> 20 -> 25 -> 26 -> 30 -> 40 -> 50

Search

이진 탐색 트리는 부모노드가 왼쪽 자식노드보다 크고, 오른쪽 자식노드보다 작으므로 효율적인 탐색이 가능하다.

여기서 25를 찾는다고 하자. 루트 20과 비교하여면크므로 왼쪽 서브트리는 비교할 필요가 없다. 그리고 오른쪽 서브트리의 루트인 30과 비교하면 작으므로 왼쪽 서브트리와 비교한다. 25와 비교하면 같으므로 값이 25인 노드를 찾을 수있다.
이렇게 비교하면서 서브트리를 반씩 날리며 연산할 수 있다.
이진 탐색 트리의 탐색 연산의 시간복잡도는 O(h)이며 h는 트리의 높이이다.

코드

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);
}

// while문
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;
}

Insert

이진 탐색 트리에 노드를 삽입 시, 루트 노드부터 값을 비교하여 제자리를 찾아간다.

22노드를 넣어보면 25의 왼쪽노드로 들어가게 된다.

코드

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;
}

Replace

u노드와 v노드를 서로 교체하고 v를 삭제

코드

void BinarySearchTree::Replace(Node* u, Node* v)
{
	// u가 루트
	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;
}

노드바로 다음의 큰 값을 반환한다.

코드

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;
}

Delete

노드를 삭제 할 때는 자식 노드가 없거나, 하나만 있거나, 양쪽 모두 있을 때로 나뉜다.

코드

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

	// 자식 노드가 없거나 하나만 있는 경우
	if (node->left == nullptr)
		Replace(node, node->right);
	else if (node->right == nullptr)
		Replace(node, node->left);
	// 양쪽 자식 노드가 모두 있을 때
	else
	{
		// 다음 데이터 찾기
		Node* next = Next(node);
		node->key = next->key;
		Delete(next);
	}
}