이진 탐색 트리

이진 탐색 트리

이진 탐색

• 정렬되어 있는 배열에 한해서 특정한 값을 찾아내는 알고리즘이다.

• 정렬되어 있는 배열의 중간 지점의 값(mid)과
  찾고있는 값(key)을 비교하여 mid > key 일 경우 key가 배열에 존재한다는 가정 하에 key는 mid의 좌측 배열에 존재할 것이고 mid < key일 경우 key는 mid의 우측 배열에 존재할 것이다.

• 따라서 mid를 key가 있다고 추정되는 배열의 중간 값으로 바꾸어 주고 mid == key일 때 까지 위 과정을 반복한다.

• 이진 탐색을 사용하면 비교가 한번 진행될 때 마다 비교군이 절반씩 감소하므로 O(logN)의 시간복잡도를 가지게 된다.

// 삽입
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;
}

// 이진 탐색
Node* BinarySearchTree::Search(Node* node, int key)
{
	while (key != node->key||node != nullptr )
	{
		if (key < node->key)
			node = node->left;
		else
			node = node->right;
	}
	return node;
}


// 삭제
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)
		Replace(node,node->right);
	else if(node->right==nullptr)
		Replace(node, node->left);
	else
	{
		Node* next = Next(node);
		node->key = next->key;
		Delete(next);
	}
}

// u 서브트리를 v 서브트리로 교체
// 그 후 u를 delete
void BinarySearchTree::Replace(Node* u, Node* 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;
}