Shulou(Shulou.com)06/01 Report--

The editor of this article introduces in detail "what are the operations of the C++ binary search tree". The contents are detailed, the steps are clear, and the details are handled properly. I hope that this article "what is the operation of the C++ binary search tree" can help you solve your doubts. Let's follow the editor's train of thought to slowly deepen, together to learn new knowledge.

The concept of binary search Tree and the concept of Operation binary search Tree

A binary search tree is also called a binary sorting tree. if its left subtree is not empty, the value of all nodes on the left subtree is less than that of the root node; if its right subtree is not empty, the value of all nodes on the right subtree is greater than that of the root node, and its left and right subtrees do not have a binary search tree respectively. It can also be an empty tree.

Int a [] = {5,3,4,1,7,8,2,6,0,9}

Operation search of binary search Tree

Iteration:

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;}

Recursion:

Node* _ FindR (Node* root, const K& key) {if (root = = nullptr) return nullptr; if (root- > _ key)

< key) return _FindR(root->

_ right, key); else if (root- > _ key > key) return _ FindR (root- > _ left, key); else return root;} insert

If the tree is empty, insert it directly

The tree is not empty. Find the insertion position and insert the new node according to the nature of the binary search tree.

Iteration:

Bool Insert (const K & key) {if (_ root = = nullptr) {_ root = new Node (key); return true;} / / find the location to insert Node* parent = nullptr; Node* cur = _ root 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); if (parent- > _ key

< cur->

_ key) {parent- > _ right = cur;} else {parent- > _ left = cur;} return true;}

Recursion:

Bool _ InsertR (Node*& root, const K & key) {if (root = = nullptr) {root = new Node (key); return true;} else {if (root- > _ key)

< key) { return _InsertR(root->

_ left, key);} else if (root- > _ key > key) {return _ InsertR (root- > _ left, key) } else {return false;} Delete

First, find out whether the element is in the binary search tree, and if it does not exist, return it. Otherwise, the node to be deleted may be divided into the following four situations:

The node to be deleted is childless

The only node to delete is the left child node.

The only node to delete is the right child node.

The only nodes to be deleted are left and right nodes

In practice, 1 and 2 or 3 can be merged, so the real deletion process is as follows:

Delete the node and point the parent node of the deleted node to the left child node of the deleted node

Delete the node and point the parent node of the deleted node to the right child node of the deleted node

Alternative method. Find the first node under the middle order in its right subtree (the key is the smallest), fill it into the deleted node with its value, and then deal with the deletion problem of the node.

Iteration:

Bool Erase (const K & key) {Node* parent = nullptr; Node* cur = _ root; while (cur) {if (cur- > _ key)

< key) { parent = cur; cur = cur->

_ right;} else if (cur- > _ key > key) {parent = cur; cur = cur- > _ left } else {/ / delete if (cur- > _ left = = nullptr) { If (cur = = _ root) {_ 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 (cur = = _ root) { _ root = cur- > _ left } else {if (cur = = parent- > _ left) {parent- > _ left = cur- > _ left } else {parent- > _ right = cur- > _ left } else {/ / find Go to the smallest node of the right tree instead of deleting Node* minRightParent = cur Node* minRight = cur- > _ right; while (minRight- > _ left) {minRightParent = minRight MinRight = minRight- > _ left;} cur- > _ key = minRight- > _ key If (minRight = = minRightParent- > _ left) minRightParent- > _ left = minRight- > _ right; else minRightParent- > _ right = minRight- > _ right Delete minRight;} return true;}} return false;}

Recursion:

Bool _ EraseR (Node*& root, const K& key) {if (root = = nullptr) return false; if (root- > _ key)

< key) { return _EraseR(root->

_ right, key);} else if (root- > _ key > key) {return _ EraseR (root- > _ left, key);} else {/ / Delete Node* del = root If (root- > _ left = = nullptr) {root = root- > _ right;} else if (root- > _ right = = nullptr) {root = root- > _ left } else {/ / alternative method to delete Node* minRight = root- > _ right While (minRight- > _ left) {minRight = minRight- > _ left;} root- > _ key = minRight- > _ key / / convert to recursively delete the smallest node return _ EraseR (root- > _ right, minRight- > _ key) in the right subtree;} delete del; return true;}} Application of binary search Tree

1.K model: in K model, only key is used as the key, key is only needed in the structure, and the key is the value to be searched. For example: give a word word to determine whether the word is spelled correctly. The specific methods are as follows: 1. A binary search tree is constructed by using each word in the word set as key. two。 Retrieve the existence of the word in the binary search tree. If it exists, it will be spelled correctly, and if it does not exist, it will be misspelled.

2.KV model: each key key has a corresponding value Value, that is, the key-value pair. This way is very common in real life: for example, an English-Chinese dictionary is the corresponding relationship between English and Chinese, and the corresponding Chinese can be found quickly through English, and the corresponding Chinese words form a key-value pair; another example is to count the number of words, after the statistics are successful, the number of times a given word appears can be quickly found, and the word and the number of times it appears constitute a key-value pair.

For example: to implement a simple English-Chinese dictionary dict, you can find the corresponding Chinese through English, the specific implementation is as follows: 1. To construct a binary search tree for key-value pairs, note: binary search trees need to be compared, and key-value pairs are compared only when comparing Key. two。 When querying English words, you only need to give English words and you can quickly find the corresponding Key.

Namespace KEY_VALUE {template struct BSTreeNode {BSTreeNode* _ left; BSTreeNode* _ right; K _ key; V _ value BSTreeNode (const K & key, const V & value): _ left (nullptr), _ right (nullptr), _ key (key), _ value (value) {}}; template class BSTree {typedef BSTreeNode Node Public: v & operator [] (const K & key) {pair ret = Insert (key, V ()); return ret.first- > _ value } pair Insert (const K & key, const V & value) {if (_ root = = nullptr) {_ root = new Node (key, value); return make_pair (_ root, true) } / / find the location to insert Node* parent = nullptr; Node* cur = _ root; while (cur) {if (cur- > _ key)

< key) { parent = cur; cur = cur->

_ right;} else if (cur- > _ key > key) {parent = cur; cur = cur- > _ left } else {return make_pair (cur, false) }} cur = new Node (key, value); if (parent- > _ key

< cur->

_ key) {parent- > _ right = cur;} else {parent- > _ left = cur } return make_pair (cur, true);} 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 } bool Erase (const K & key) {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 {/ / delete if (cur- > _ left = = nullptr) {if (cur = = _ root) {_ root = cur- > _ right } else {if (cur = = parent- > _ left) {parent- > _ left = cur- > _ left } else {parent- > _ right = cur- > _ right }} delete cur } else if (cur- > _ right = = nullptr) {if (cur = = _ root) {_ root = cur- > _ left } else {if (cur = = parent- > _ left) {parent- > _ left = cur- > _ left } else {parent- > _ right = cur- > _ right }} delete cur } else {/ / find the smallest node of the right tree instead of deleting Node* minRightParent = cur Node* minRight = cur- > _ left; while (minRight- > _ left) {minRightParent = minRight MinRight = minRight- > _ left;} cur- > _ key = minRight- > _ key If (minRight = minRightParent- > _ left) minRightParent- > _ left = minRight- > right Else minRightParent- > _ right = minRight- > _ right; delete minRight } return true;}} return false } void InOrder () {_ InOrder (_ root); cout _ left); cout _ key > str) {if (str = = "Q") {break } else {auto ret = dict.Find (str); if (ret = = nullptr) {cout

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.