The concept, implementation and analysis of binary search tree (BST)

Catalog

Binary search tree

Concept

BST Insertion of trees

 BST Tree search

BST The deletion of ( important )

application

Performance analysis

---

Binary search tree

Concept

Binary search tree is also called binary sort tree , It could be an empty tree , Or a binary tree with the following properties :

• If its left subtree is not empty , Then the values of all nodes on the left subtree are smaller than the values of the root nodes
• If its right subtree is not empty , Then the value of all nodes on the right subtree is greater than the value of the root node
• Its left and right subtrees are also binary search trees

int ar[]={5,3,2,4,8,9,1};

BST Insertion of trees

• If the tree is empty, it will be inserted directly ;
• If it's not empty , Then insert according to the rules of binary search tree .

bool Insert(const K& key, const V& value)
	{
		if (_root == nullptr)
		{
			_root = new Node(key, value);
			return true;
		}
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}

		cur = new Node(key, value);
		if (cur->_key > parent->_key)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		return true;

	}

 BST Tree search

If the root node _root->_key== You're looking for key  Return the found node

If the root node _root->_key> You're looking for key  Look on its left sub tree

If the root node _root->_key< You're looking for key  Look on its right subtree

If the root node does not exist , Return null pointer

	Node* Find(const K& key)
	{
		Node* cur = _root;
		while (cur)
		{
			if (cur->_key < key)
			{
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				cur = cur->_left;

			}
			else
			{
				return cur;
			}
		}
		return nullptr;
	}

BST The deletion of ( important )

First of all, according to the key Find nodes , No return found false;

There are three cases of deletion

1. The left subtree of the node to be deleted is empty

• The root node to delete , Let the root be equal to the right child node
• The left child node that is an ordinary node and its parent node to be deleted is parent->_left = cur->_right
• The right child node that is an ordinary node and its parent node to be deleted is parent->_right= cur->_right

2. The right subtree of the node to be deleted is empty

• The root node to delete , Let the root be equal to the left child node
• The left child node that is an ordinary node and its parent node to be deleted is parent->_left = cur->_left; 
• The left child node that is an ordinary node and its parent node to be deleted is parent->_right = cur->_left;

3. The left and right child nodes of the deleted node are not empty :

  We use the substitution method here

Find the largest node of the left subtree ( The most right ) Or the smallest node of the right subtree

The code is as follows :

	bool Erase(const K& key)
	{
		//1. Looking for nodes 
		Node* cur = _root;
		Node* parent = nullptr;
		while (cur)
		{
			if (cur->_key < key)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				if (cur->_left == nullptr)
				{
					if (parent == nullptr)// The root node to delete 
					{
						_root = cur->_right;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_right;
						}
						else
						{
							parent->_right = cur->_right;
						}
					}
					delete cur;
				}
				else if (cur->_right == nullptr)
				{
					if (parent == nullptr)
					{
						_root = cur->_left;
					}
					else
					{
						if (cur == parent->_left)
						{
							parent->_left = cur->_left;

						}
						else
						{
							parent->_right = cur->_left;
						}
					}
					delete cur;
				}
				else
				{
					//  The substitution method deletes    The largest node of the left tree ( The rightmost node )  Or the smallest node of the right tree ( Leftmost node )
					Node* Parent = cur;  //  Be careful not to initialize null 
					Node* minNode = cur->_right;
					while (minNode->_left)
					{
						Parent = minNode;
						minNode = minNode->_left;
					}
					swap(cur->_key, minNode->_key);
					//  Convert to delete minNode


					//  because minNode As an empty node , You can delete 
					if (Parent->_right == minNode)
						Parent->_right = minNode->_right;
					else
						Parent->_left = minNode->_right;
					delete minNode;
				}
				return true;
			}
		}
        return false;
	}

application

according to BST We can realize the characteristics of trees

  1. K Model ：K The model has only key As a key , You only need to store Key that will do , The key is the value to be searched .

such as ： Give a word word, Judge whether the word is spelled correctly , The specific way is as follows ：

Take each word in the word set as key, Build a binary search tree

  Retrieve whether the word exists in the binary search tree , If it exists, it is spelled correctly , If it does not exist, it is misspelled .

2. KV Model ： Every key key, All have corresponding values Value, namely <Key, Value> The key/value pair . This way in real life Very common in life ： For example, an English Chinese dictionary is the corresponding relationship between English and Chinese , Through English, you can quickly find the corresponding Chinese   writing , Britain Chinese words and their corresponding Chinese <word, chinese> It forms a key value pair ; Another example is counting the number of words , After successful Statistics , Given Words can quickly find the number of times they appear , Words and their occurrences are <word, count> It forms a key value pair .

such as ： Realize a simple English Chinese Dictionary dict, You can find the corresponding Chinese... In English , The specific implementation is as follows ：

< word , Chinese meaning > Construct a binary search tree for key value pairs , Be careful ： Binary search trees need to compare , When comparing key value pairs, only

Key When querying English words , Just give the English words , You can quickly find the corresponding key.   

Performance analysis

Insert and delete operations must first find , Search efficiency represents the performance of each operation in binary search tree .

Yes, yes. n A binary search tree of nodes , If the probability of finding each element is equal , Then the average search length of the binary search tree is the number of nodes in the binary search tree A function of depth , That is, the deeper the node , The more times you compare .

But for the same key set , If the order of key insertion is different , It is possible to get binary search trees with different structures

Therefore, the best efficiency of binary search tree is like a complete binary tree, and its average number of comparisons is :

The worst is equivalent to a single branch tree , The average number of comparisons is :