Detailed description of binary search tree

Catalog

1. Binary search tree

1.1 The concept of binary search tree

1.2 Binary search tree operation

 1.2.1 Binary tree search

 1.2.2  The insertion of a binary tree

 1.2.3   The deletion of binary trees

summary

---

1. Binary search tree

1.1 The concept of binary search tree

Binary search tree is also called Binary sort tree , It could be a Empty tree , It may also be a binary tree that satisfies the following characteristics ：

• If its left subtree is not empty , Then the value on all nodes of the left subtree is less than the value on the root node
• If its right subtree is not empty , Then the value on all nodes of the right subtree is greater than the value on the root node
• Its left and right subtrees also meet the above characteristics

This is a standard binary search tree

1.2 Binary search tree operation

 1.2.1 Binary tree search

    Implementation steps ：

• Start from the root node and find , If the current value is larger than the target value , Then search on the right subtree
• If the current value is smaller than the target value , Then search on the left subtree
• If the current value is equal to the target value , Then return to true
• If the empty node is still not found , Then return to false

Let's see how the code is implemented ：

1. Non recursive writing

	bool Find(const K& val)
	{
        // from root Start looking for 
		Node* cur = root;
        // If so cur It's empty , If it is still not found, it returns false
		while (cur)
		{
            // If it is smaller than the current value, search in the left subtree 
			if (cur->val > val)
			{
				cur = cur->left;
			}
            // If it is larger than the current value, search in the right subtree 
			else if (cur->val < val)
			{
				cur = cur->right;
			}
            // If it is equal, it will return to true
			else
			{
				return true;
			}
		}
		return false;
	}

2. Recursive writing

Because parameters cannot be passed directly within a class , So it encapsulates a layer of functions

bool FindR(const K&val)
{
     return _FindR(root,val);
}
bool _FindR(Node*& root, const K& val)
{       
        // If root If it is empty, it means that , Returns an empty 
		if (!root)
		{
			return false;
		}
        // If it is less than the template value , Then search in the left subtree 
		if (root->val < val)
		{
			return _FindR(root->right, val);
		}
        // If it is greater than the template value , Then search in the right subtree 
		else if (root->val > val)
		{
			return _FindR(root->left, val);
		}
        // If it is equal to the target value , Then return to true
		else
		{
			return true;
		}
}

1.2.2  The insertion of a binary tree

Implementation steps ：

• If the tree is empty , Then assign the inserted node directly to root
• If the tree is not empty , Then find the insertion position according to the nature of the binary search tree

  If we need to insert 9 This node , So what are our steps ？

1. Start from the root node and find , If the current value is less than 9 Be big , Then search on the right subtree
2. If the current value is less than 9 smaller , Then search on the left subtree
3. If the current value is equal to 9, Then return to false（ The current setting does not allow inserting the same element ）
4. If you reach the empty node , Then this is the position to insert

How is our code implemented ？

1. Non recursive writing

bool insert(const K& val)
	{
		// If it's an empty tree 
		if (!root)
		{
			root = new Node(val);
			return true;
		}
		// If it's not an empty tree 
		else
		{ 
            // You need to create a parent node to link the inserted node 
			Node* parent = nullptr;
			Node* cur = root;
			while (cur)
			{
				if (cur->val < val)
				{
					parent = cur;
					cur = cur->right;
				}
				else if (cur->val > val)
				{
					parent = cur;
					cur = cur->left;
				}
				else
				{
					return false;
				}
			}
           //cur Went to the empty node , That is where we want to insert 
			Node* newnode = new Node(val);
            // You also need to determine whether you are inserting a left subtree or a right subtree 
			if (parent->val < val)
			{
				parent->right = newnode;
			}
			else
			{
				parent->left = newnode;
			}
			return true;
		}
	}

2. Recursive writing

bool InsertR(const K& val)
{
	return _InsertR(root, val);
}

bool _InsertR(Node*& root, const K& val)
{
		// If it is empty , Is the insertion position 
		if (!root)
		{
			root = new Node(val);
			return true;
		}
        // If the current value is less than the target value , Then find the position in the left subtree 
		if (root->val < val)
		{
			return _InsertR(root->right, val);
		}
        // If the current value is greater than the target value , Then find the position in the right subtree 
		else if (root->val > val)
		{
			return _InsertR(root->left, val);
		}
        // If the current value is equal to the target value , return false
		else
		{
			return false;
		}
}

Different from ordinary non recursive writing , There is no need to decide whether to insert the left subtree or the right subtree

  If we insert it recursively 9 This value , We will find that 9 The last place to insert is 10 The left side of this node , Again because root Of 10 Of Alias of the left node , So we just need to put root Value assignment of 9 This node can

1.2.3   The deletion of binary trees

Implementation steps ：

1. First, find out whether the element is in the binary search tree , If it doesn't exist , Then return to false,
2. Otherwise, the nodes to be deleted may be divided into the following four situations ：

• The node to be deleted has no children
• Only the left child node is to be deleted
• Only the right child node is to be deleted
• The node to be deleted has left 、 Right child node
   

We can find that when there are no child nodes, this situation can also be summarized in the case of only left nodes or right nodes

Then the code implementation is as follows ：

1. Non recursive writing

bool erase(const K& val)
	{
		Node* cur = root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->val < val)
			{
				parent = cur;
				cur = cur->right;
			}
			else if (cur->val > val)
			{
				parent = cur;
				cur = cur->left;
			}
			// If the target value is found 
			else
			{
                // Record the deleted nodes 
				Node* del = cur;
				if (!cur->left)
				{
					if (!parent)
					{
						cur = cur->right;
					}
					else
					{
						if (parent->left == cur)
						{
							parent->left = cur->right;
						}
						else
						{
							parent->right = cur->right;
						}
					}
					delete del;
				}
				else if (!cur->right)
				{
					if (!parent)
					{
						cur = cur->left;
					}
					else
					{
						if (parent->left == cur)
						{
							parent->left = cur->left;
						}
						else
						{
							parent->right = cur->left;
						}
					}
					delete del;
				}
				// Left and right subtrees are not empty 
				else
				{
					Node* minparent = cur;
					Node* minright = cur->right;
					// Find the minimum value of the right subtree 
					while (minright->left)
					{
						minparent = minright;
						minright = minright->left;
					}
					// Exchange the size of the minimum value and the target value 
					swap(cur->val, minright->val);
				    
					if (minparent->left == minright)
					{
						minparent->left = minright->right;
					}
					else
					{
						minparent->right = minright->right;
					}
					// Delete the replaced node 
					delete minright;
				}
				return true;
			}
		}
		return false;
	}

2. Recursive writing

bool EraseR(const K& val)
{
		return _EraseR(root, val);
}
bool _EraseR(Node*& root, const K& val)
{
		// If it is empty , Then the target value does not exist , return false
		if (!root)
		{
			return false
		}

		if (root->val < val)
		{
			return _EraseR(root->right, val);
		}
		else if (root->val > val)
		{
			return _EraseR(root->left, val);
		}
		// Find the target node 
		else
		{
			// If the left subtree is empty 
			if (!root->left)
			{
				root = root->right;
			}
			else if (!root->right)
			{
				root = root->left;
			}
			else
			{
				Node* minright = root->right;
				while (minright->left)
				{
					minright = minright->left;
				}
				swap(root->val, minright->val);

				return _EraseR(root->right, minright->val);
			}
		}
}

summary

The difference between recursive and non recursive writing ：

1. Recursive writing does not need to judge whether the target value is the left subtree or the right subtree of its parent value in the delete and insert operations
2. The outstanding thing about recursive writing is the small amount of code
3. If the binary search tree is not uniform , Recursive writing may cause stack overflow

   ---