binary search tree

binary search tree

  • What is a Binary Search Tree?

A binary search tree is first a binary tree. This binary tree has such a feature that all nodes in the left subtree are smaller than the root node, and all nodes in the right subtree are larger than the root node. And the left and right subtrees also satisfy this condition
A binary search tree is also called a binary sorted tree because its inorder traversal is in order.

Implementation of binary search tree - K model

K model only stores k value

Each node of a binary search tree has a value and two pointers, a pointer to the left node and a pointer to the right node.

template<class K>
struct BSTreeNode//The default access permission of sturct is public, because the members of the node are to be accessed
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K key;
	BSTreeNode(const K& k)
		:_left(nullptr),
		_right(nullptr),
		key(k)
	{}
};
  • The following implements a binary search tree

The member variable of the binary search tree has only one pointer to the root node

template<class K>
class BSTree
{
	template BSTreeNode<K> Node;
	Node* root=nullptr;
public:

};

insert

According to the characteristics of the binary search tree, we start searching from the root node:

  1. If the k value is less than the value of the node, go to the left tree to find
  2. If the k value is greater than the value of the node, go to the right tree to find
  3. If equal return false

Sign of the end: the node is empty and can be inserted into it.

Notice:

  1. When the tree is empty, the inserted node is the root node
  2. When it is empty, it cannot be inserted directly, because it is a temporary variable, and the child node must be linked from the position of its parent node.
	bool Insert(const K& k)
	{
		if (root == nullptr)
		{
			root = new Node(k);
			return true;
		}
		Node* cur = root;
		Node* parent = nullptr;
		while (cur)
		{
			if (k > cur->key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (k < cur->key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
				return false;
		}
		cur = new Node(k);
		if (parent->key>k)
			parent->_left = cur;
		else
			parent->_right = cur;
		return true;
	}

From here we can see that the binary search tree is naturally deduplicated - there are no identical elements

  • Recursive writing

In this recursive writing method, if a reference is used, then there is no need to find the parent node. The reference is an alias (isn’t it itself), and we just want to insert itself.

	bool _Insert(Node* &root, const K& k)
	{
		if (root == nullptr)
		{
			root = new Node(k);
			return true;
		}
		if (k > root->key)
			return _Insert(root->_right, k);
		else if (k < root->key)
			return _Insert(root->_left, k);
		else
			return false;
	}
	bool Insert(const K& k)
	{
		return _Insert(root, k);
	}

look up

The search is actually relatively simple, just search according to the nature of the tree

	bool Find(const K& k)
	{
		Node* cur = root;
		while (cur)
		{
			if (k > cur->key)
				cur = cur->_right;
			else if (k < cur->key)
				cur = cur->_left;
			else
				return true;
		}
		return false;
	}
  • Recursive writing
	bool _Find(Node* root, const K& k)
	{
		if (root == nullptr)
			return false;

		if (k > root->key)
			return _Find(root->_right, k);
		else if (k < root->key)
			return _Find(root->_left, k);
		else
			return true;
	}
	bool Find(const K& k)
	{
		return _Find(root, k);
	}

delete

The deletion operation is quite troublesome, and there are many points to pay attention to, because after deletion, it is necessary to ensure that the tree is still a search binary tree.
Here are a few points to note:

  1. Deleted nodes are leaf nodes—there are no left and right subtrees.
  2. The deleted node has only one subtree—the node has only the left subtree or only the right subtree.
  3. The deleted node has both a left subtree and a right subtree.
  • solve

For 1 and 2, we can combine them into one problem, and regard the 1 problem as: both the left and right subtrees are empty.
1, 2 Questions:

  • When the node does not have a left subtree, such as deleting 1, how do we do it? ——The left subtree of 3 can be linked to 2. The left (or right) pointer of the parent node points to the right subtree of the deleted node. The determination of the left and right pointers depends on the positional relationship between the parent node and the child node
				//Left is empty
				if (cur->_left == nullptr)
				{
					if (cur == root)
						root = cur->_right;
					else
					{
						if(father->_left==cur)
							father->_left = cur->_right;
						else
							father->_right = cur->_right;
					}
					delete cur;
				}
  • When the node does not have a right subtree, such as deleting 14, how do we do it? ——The right subtree of 10 can be connected to 13. The left (right) pointer of the parent node points to the left subtree of the deleted node. The determination of the left and right pointers depends on the positional relationship between the parent node and the child node
				//Right is empty
				else if (cur->_right == nullptr)
				{
					if (cur == root)
						root = cur->_left;
					else
					{
						if (father->_left == cur)
							father->_left = cur->_left;
						else
							father->_right = cur->_left;
					}
					delete cur;
				}
  • Extreme case - the node is the root node, at this time we only need to change the pointer of the root node, and then delete the original root node.For example delete 3

For the 3rd question:

We use the exchange method:

For example, to delete 3 here, according to the nature of the binary search tree, the left side is smaller than it, and the right side is larger than it.
Then we have two ways to solve the problem:

  1. Find the node with the largest left subtree (2 nodes in the above figure), and exchange with it. ——According to the nature of the tree, the largest node is at the far right of the left subtree. Can the node be deleted directly then? ——No, because there may be a left subtree to the left of 2, so we want the right pointer of the parent node of this node (1 in this picture) to point to the left subtree of the changed node after swapping.

There is no need to determine the relationship between the parent node and the child node here, because the relationship has already been determined. ——When deleting the root node, you need to re-determine their relationship

As shown below:

2. Find the node (node ​​4) with the smallest right subtree, and exchange with it. ——According to the nature of the tree, the node is at the leftmost of the right subtree. The node cannot be deleted directly after the exchange, because it may have a right subtree, and we need to point the left pointer of its parent node to its right subtree.

As shown below:


Notice:
When the deleted node is the root node, it is different from the above rules. For example, if the node 8 is deleted, we exchange it with the node 10, which is the smallest right subtree. If we follow the above rules, we must point the left pointer of its parent node to its right subtree.
will become like this:

This is not a binary search tree.
Let's think about it, why does this happen? For the above two cases, changing the left point of the node needs to be deleted, but it is completely different for the root node, because its left side does not need to be moved.
Solution: Which pointer of the parent node points to the node value equal to the value of the deleted node, then the pointer points to the right subtree of the deleted node (corresponding to solution 2), and the pointer points to the left subtree of the deleted node (corresponding to solution 1) .

				else
				{
					Node* mincur = cur->_right;
					father = cur;
					while (mincur->_left)
					{
						father = mincur;
						mincur = mincur->_left;
					}
					swap(cur->key, mincur->key);
					if (father == root)
					{
						if (father->_left == mincur)
							father->_left = mincur->_right;
						else
							father->_right = mincur->_right;
					}
					else
						father->_left = mincur->_right;
					delete mincur;
				}

Non-recursive writing

	bool Erase(const K& k)
	{
		if (root == nullptr)
			return false;

		Node* cur = root;
		Node* father = cur;
		while (cur)
		{
			if (k > cur->key)
			{
				father = cur;
				cur = cur->_right;
			}	
			else if (k < cur->key)
			{
				father = cur;
				cur = cur->_left;
			}
			else
			{
				//Left is empty
				if (cur->_left == nullptr)
				{
					if (cur == root)
						root = cur->_right;
					else
					{
						if(father->_left==cur)
							father->_left = cur->_right;
						else
							father->_right = cur->_right;
					}
					delete cur;
				}
				//Right is empty
				else if (cur->_right == nullptr)
				{
					if (cur == root)
						root = cur->_left;
					else
					{
						if (father->_left == cur)
							father->_left = cur->_left;
						else
							father->_right = cur->_left;
					}
					delete cur;
				}
				//are all empty
				else
				{
					Node* mincur = cur->_right;
					father = cur;
					while (mincur->_left)
					{
						father = mincur;
						mincur = mincur->_left;
					}
					swap(cur->key, mincur->key);
					if (father == root)
					{
						if (father->_left == mincur)
							father->_left = mincur->_right;
						else
							father->_right = mincur->_right;
					}
					else
						father->_left = mincur->_right;
					delete mincur;
				}
				return true;
			}

		}
		return false;

	}

recursive writing

For recursive writing:
First, the conditions for processing return
Second, handle the logic of left tree, right tree
Third, handle the current logic

  1. return: return when empty
  2. The k value is larger than the root value, delete the right tree, and the k value is smaller than the root value, delete the left tree
  3. When it is equal, it is the current logic, the left tree is empty, and its right subtree is directly connected, because the reference is passed, and when the right subtree is empty, its left subtree is directly connected. When the left and right subtrees are not empty, it is still the exchange logic. After the exchange, we only need to continue to delete the tree (for the following processing, we only need to delete on the right subtree)
bool _Erase(Node*& root, const K& k)
	{
		if (root == nullptr)
			return false;

		if (k > root->key)
			return _Erase(root->_right, k);
		else if (k < root->key)
			return _Erase(root->_left, k);
		else
		{
			Node* cur = root;
			if (root->_left == nullptr)
			{
				root = root->_right;
				delete cur;
			}
			else if (root->_right == nullptr)
			{
				root = root->_left;
				delete cur;
			}
			else
			{
				cur = cur->_right;
				while (cur->_left)
				{
					cur = cur->_left;
				}
				swap(cur->key, root->key);
				return _Erase(root->_right, k);
			}
			return true;
		}
	}

copy

The copy of the binary search tree is a deep copy, and care should be taken to maintain the characteristics of the tree during the copy process.
The idea is: we copy a tree, and then root points to the root node of the tree and the creation is complete.
_copy, we use copynode as the root node of the tree,
We handle this layer of logic first: give values ​​to nodes, then process the left tree, then process the right tree.

	Node* _copy(Node* _root)
	{
		if (_root == nullptr)
			return nullptr;
		Node* copynode = new Node(_root->key);
		copynode->_left = _copy(_root->_left);
		copynode->_right = _copy(_root->_right);

		return copynode;
	}
	BSTree(const BSTree<K>& Tree)
	{
		root = _copy(Tree.root);
	}

Of course, in the process of copying, we use the method of preorder traversal to copy

	void ProOrder(Node* &root, Node* const& Troot)
	{
		if (Troot == nullptr)
			return;
		root = new Node(Troot->key);
		ProOrder(root->_left, Troot->_left);
		ProOrder(root->_right, Troot->_right);

	}
	BSTree(const BSTree<K>& Tree)
	{
		ProOrder(root, Tree.root);
	}

assignment

direct borrow copy construction

	BSTree<K>& operator=(BSTree<K> t)
	{
	swap(root, t.root);
	return *this;
	}

KV model

A k corresponds to a v, stored together, similar to a dictionary in python
For the kv model, there are relatively few places that need to be changed

  • member adds a value
template<class K,class V>
struct BSTreeNode
{
	BSTreeNode* _left;
	BSTreeNode* _right;
	K key;
	V val;
	BSTreeNode(const K& k,const V& v)
		:_left(nullptr),
		_right(nullptr),
		key(k),
		val(v)
	{}
};
  • When looking up, return the pointer of the node to modify the value
  • Insertion is still similar to the k model
  • Delete does not change, or press K to delete

source code in This blog code link

Performance Analysis of Binary Search Tree

For the time complexity of its search O(h), h is the height of the number, when the binary tree is a single branch tree, the complexity is O(N), then in the worst case it loses its performance.

Tags: C++ Algorithm data structure

Posted by Invincible on Thu, 01 Dec 2022 19:52:09 +0300