[DS] Binary Search Tree

Min / Max

tree minimum(tree node) 
{ 
  if (node->left == nullptr) return node;
  return minimum(node->left);
}

tree maximum(tree node) 
{ 
  if (node->right == nullptr) return node;
  return maximum(node->right);
}

pred( ) / succ( )

tree succ(tree node) 
{
	if (node != nullptr && node->right != nullptr)
		return minimum(node->right);
	return nullptr;
}

tree pred(tree node) 
{
	if (node != nullptr && node->left != nullptr)
		return maximum(node->left);
	return nullptr;
}

Trim

Case 1: No child

해당 노드를 nullptr 처리함

Case 2: One Child

해당 노드를 지우기 전에 Child를 해당 노드의 부모노드와 link 시킨 후 제거

Case 3: Two Child

predecessor(왼쪽의 Max) or successor(오른쪽의 Min) 중 height가 가장 높은 것을 골라 해당 값을 지우려는 노드에 덮어 씌우고 predecessor 혹은 successor를 제거

tree trim(tree node, int key) 
{
	if (empty(node)) return node;	 // base case
	if (key < node->key) // if node to trim is in left subtree.
		node->left = trim(node->left, key);
	else if (key > node->key) // node to trim is in right subtree.
		node->right = trim(node->right, key);
	// found the key: delete the node now 
	// node with two childeren: replace it with the successor or predecessor
	else if (node->left && node->right) 
	{ 
		if(height(node->left) > height(node->right))
		{
			node->key = pred(node)->key;
			node->left = trim(node->left, node->key);
		}
		else		
		{
			node->key = succ(node)->key;
			node->right = trim(node->right, node->key);
		}	
	}
	else if (node->left || node->right)
	{
		tree temp = node;

		if(node->left)
		{
			node = node->left; 
		}
			 
		else
		{
			node = node->right;
		}
		delete temp;
	}
	else
	{
		node = nullptr;
	}


	return node;
}

search operation

search operation takes time O(h), where h is the height of a BS

BT to BST

1. BT의 모든 노드 값들을 sorted 배열로 읽어 온다 (using set)
2. sorted array를 inorder traveling 하며 배열 값을 순서대로 대입한다.

void get_keys(tree root, set<int> &keys) 
{
	if (root == nullptr) return;
	keys.insert(root->key);
	get_keys(root->left, keys);
	get_keys(root->right, keys);
}

void put_keys(tree root, set<int>::iterator& it)
{
	if(root == nullptr) return;
	put_keys(root->left, it);
	root->key = *it;
	it++;
	put_keys(root->right, it);

}

void BTtoBST(tree root) 
{	
	set<int> keys;
	get_keys(root, keys);

	int setKeySize = keys.size();
	int treeKeySize =  size(root);

	assert(setKeySize == treeKeySize);

	set<int>::iterator it = keys.begin();
	put_keys(root, it);
    
}

LCA : Find the common Ancestor of P and Q

Recursive solution

Time Complexity: O(N)
Space Complexity : O(N) - 호출 스택에 계속 쌓아야 하므로

// recursive solution
tree LCA(tree root, tree p, tree q) 
{  
	if (root == nullptr) return 0;

	if (p->key > root->key && q->key > root->key)
		return LCA(root->right,p,q); 
	else if (p->key < root->key && q->key < root->key)
		LCA(root->left,p,q);
	else
		return root;

	return root;
}

Iteration solution

Time Complexity: O(N)
Space Complexity : O(1) - 주어진 공간에서 작동하기 때문

// iteration solution
int LCAiteration(tree root, tree p, tree q) {  
	DPRINT(cout << ">LCAiteration " << endl;);
	tree node = root;

	while (node != nullptr) 
	{
		if (p->key > node->key && q->key > node->key)
			node = node->right; 
		else if (p->key < node->key && q->key < node->key)
			node = node->left;
		else
			return node->key;
	}
	
	return 0;
}