게임알고리즘 9주차 - Binary Search Tree

지난시간 복습.

탐색

순회 - 전위, 중위, 후위, 깊이우선 탐색, 너비우선 탐색

 

Tree

- 이진트리

- 레벨

- 높이 (height) : 가장 큰 레벨 = max(왼쪽 sub 높이, 오른쪽 sub 높이)

   - 비어있는 트리의 높이는 - 1

- 균형 (balance) : 좌우의 sub tree의 높이의 차.

- 균형트리 : balance factor가 1 이하인 tree.

- 포화이진트리 : balance factor가 0인 tree.

- 완전이진트리 : balance factor가 0이거나 1인 tree.

 

Binary Search Tree

Dynamic Search using Tree

- 정적 검색 (Static Search) : 데이터가 한꺼번에 저장되어 추후에 추가나 삭제가 이루어지지 않는 경우에 이루어지는 검색.

- 동적 검색 (Dynamic Search) : 데이터가 수시로 삭제되는 유동적인 경우 사용되는 검색.

배열 자료구조를 사용하면, 정적 검색의 경우 문제없이 이진검색이나 보간검색 알고리즘을 적용할 수 있지만, 동적검색의 경우는 불가능. 따라서 트리구조를 사용해야 함.

 

Binary Search Tree (이진검색트리)

이진검색트리는 다음 조건을 만족하는 이진트리이다.

- 각 노드마다 하나의 키 값이 할당되어 있다.

- 어떤 노드 N의 왼쪽부분트리(left subtree)에 속한 모든 노드의 키 값은 N의 키 값보다 작거나 같다.

- 어떤 노드 N의 오른쪽부분트리(right subtree)에 속한 모든 노드의 키 값은 N의 키 값보다 크거나 같다.

- N의 왼쪽서브트리와 N의 오른쪽 서브트리도 이진탐색트리이다.

 

Why uses a binary search tree?

In-order traversal(중위순회)을 하면 정렬된 순서로 아이템을 추출할 수 있다.

 

평균 검색시간을 짧게 유지하는 것이 중요하다.

- 동적으로 트리에 아이템이 추가되고 삭제되므로 트리가 항상 균형(balance)을 유지한다는 보장이 없다.

- 외창긔 영운 연걸리스틀를 사용하는 것과 같다 (Skewed tree).

- 랜덤(random)하게 아이템이 트리에 추가되는 경우는 대체로 트리가 균형을 유지한다. -> 평균적인 검색 시간을 기대할 수 있다.

 

Structure of binary search tree

struct Node 
{
	int data;
	Node* left;
	Node* right;
	Node(int d) :
		data(d), left(nullptr), right(nullptr) {}
};

 

Search a Key from binary search tree

Node* BinarySearchTree::search(Node* T, int key) {
	if (T == nullptr) 
	{
		return nullptr;
	}
	else if (T->data == key) 
	{
		return T;
	}
	else if (T->data > key) 
	{
		search(T->left, key);
	}
	else 
	{
		search(T->right, key);
	}
}

 

Insert a node to binary search tree

Node* BinarySearchTree::insertNode(Node* T, int key)
{
	if (T == nullptr) 
	{
		T = new Node(key);
	}
	else if (T->data > key) 
	{
		T->left = insertNode(T->left, key);
	}
	else 
	{
		T->right = insertNode(T->right, key);
	}

	return T;
}

 

Delete a node in binary search tree

Case 1 : 삭제할 노드가 단말노드(Leaf node)인 경우

- 자식이 없어서 간단

- Ex) 노드 K를 삭제하려면 노드 H의 Rchild를 Null로 넣으면 됨

 

Case 2 : 삭제할 노드가 하나의 자식노드를 거느리는 경우

- 왼쪽 자식노드만 있거나 오른쪽 자식노드만 있는 경우

- 삭제할 노드의 부모노드가 삭제노드의 자식노드를 가리키면 됨

- Ex) 노드 F를 삭제하려면 . F의 부모노드(G)가 F의 자식노드(B)를 가리키면 됨

 

Case 3 : 삭제할 노드가 두 개의 자식노드를 거느리는 경우

- 방법 1 : 삭제할 노드의 왼쪽 서브트리의 오른쪽 단말노드의 키 값을 삭제노드의 키 값으로 복사

- 방법 2 : 삭제할 노드의 오른쪽 서브트리의 왼쪽 단말노드의 키 값을 삭제노드의 키 값으로 복사

Node* BinarySearchTree::deleteNode(Node* T, int key)
{
	// there is no data
	if (T == nullptr) 
	{
		return nullptr;
	}
	// move left
	else if (T->data > key) 
	{
		T->left = deleteNode(T->left, key);
		return T;
	}
	// move right
	else if (T->data < key) {
		T->right = deleteNode(T->right, key);
		return T;
	}
	// found data
	else if (T->data == key)
	{
		// Case 1 : The node is leaf node.
		if ((T->left == nullptr) && (T->right == nullptr))
		{
			delete T;

			return nullptr;
		}
		// Case 2 : The node has one children.
		else if (T->left == nullptr)
		{
			Node* Temp = T->right;
			delete T;

			return Temp;
		}
		// Case 2 : The node has one children.
		else if (T->right == nullptr)
		{
			Node* Temp = T->left;
			delete T;

			return Temp;
		}
		// Case 3 : The node has two children.
		else
		{
			Node* rightMin = T->right;

			while (rightMin->left != nullptr)
			{
				rightMin = rightMin->left;
			}

			T->data = rightMin->data;
			deleteNode(rightMin, rightMin->data);

			return T;
		}
	}
}

 

Binary Search Tree 구현 실습

- data : int

- Methods : insertNode, deleteNode, search, etc.

#pragma once
using namespace std;

struct Node 
{
	int data;
	Node* left;
	Node* right;
	Node(int d) :
		data(d), left(nullptr), right(nullptr) {}
};

class BinarySearchTree
{
private:
	Node* node;

public:
	BinarySearchTree() : { }
	~BinarySearchTree() { }

	Node* insertNode(Node* T, int key);
	Node* deleteNode(Node* T, int key);
	Node* search(Node* T, int key);
};

Node* BinarySearchTree::insertNode(Node* T, int key)
{
	if (T == nullptr) 
	{
		T = new Node(key);
	}
	else if (T->data > key) 
	{
		T->left = insertNode(T->left, key);
	}
	else 
	{
		T->right = insertNode(T->right, key);
	}

	return T;
}

Node* BinarySearchTree::deleteNode(Node* T, int key)
{
	// there is no data
	if (T == nullptr) 
	{
		return nullptr;
	}
	// move left
	else if (T->data > key) 
	{
		T->left = deleteNode(T->left, key);
		return T;
	}
	// move right
	else if (T->data < key) {
		T->right = deleteNode(T->right, key);
		return T;
	}
	// found data
	else if (T->data == key)
	{
		// Case 1 : The node is leaf node.
		if ((T->left == nullptr) && (T->right == nullptr))
		{
			delete T;

			return nullptr;
		}
		// Case 2 : The node has one children.
		else if (T->left == nullptr)
		{
			Node* Temp = T->right;
			delete T;

			return Temp;
		}
		// Case 2 : The node has one children.
		else if (T->right == nullptr)
		{
			Node* Temp = T->left;
			delete T;

			return Temp;
		}
		// Case 3 : The node has two children.
		else
		{
			Node* rightMin = T->right;

			while (rightMin->left != nullptr)
			{
				rightMin = rightMin->left;
			}

			T->data = rightMin->data;
			deleteNode(rightMin, rightMin->data);

			return T;
		}
	}
}

Node* BinarySearchTree::search(Node* T, int key) {
	if (T == nullptr) 
	{
		return nullptr;
	}
	else if (T->data == key) 
	{
		return T;
	}
	else if (T->data > key) 
	{
		search(T->left, key);
	}
	else 
	{
		search(T->right, key);
	}
}

 

Binary Search 시간 복잡도

Time complexity of search in binary search tree

Theorem

- 검색하는 아이템 x가 n개의 아이템 중의 하나가 될 확률이 동일하다고 가정하면, 이진검색트리의 평균검색시간은 대략 A(n) = 1.38 logn이 된다.

 

가정

- k번째로 작은 아이템이 뿌리마디에 위치하고 있는 n개의 아이템을 가진 이진검색트리.

 

증명

- 왼쪽 서브트리에 k-1개의 마디가 있고, 오른쪽 서브트리에 n-k개의 마디가 존재한다.

- A(k-1) : 왼쪽 서브트리를 검색하는 평균검색시간

- A(n-k) : 오른쪽 서브트리를 검색하는 평균검색시간

- x가 왼쪽 서브트리에 있을 확률 : (k-1)/n

- x가 오른쪽 서브트리에 있을 확률 : (n-k)/n

- A(n|K) : 크기 n의 입력에 대해 k번째로 작은 아이템이 뿌리 마디에 위치하고 있는 이진검색트리에 대한 평균 검색시간.

 

시간복잡도 계산 간략화 과정 학습.