​

primers

Tree structure is a very important data structure, many students have no idea what a tree can do after learning the tree. What are the application scenarios of trees?

So I’m going to talk about search trees, which are widely used in databases, such as B-tree or B-+ tree data structures for efficient sorting and retrieval.

Binary search trees, red-black trees, AVL trees, as well as B-trees and B-+ trees are all frequently asked about in the interview process!

It all starts with Binary Search trees.

Basic properties of binary search tree:

  • If its left subtree is not empty, then all nodes in the left subtree are less than the root node

  • If its right subtree is not empty, then all nodes in the right subtree are greater than the root node

  • Its left and right subtrees are binary search trees respectively

The following image shows a binary search tree that satisfies the three basic properties described above.

The illustration

So what are the benefits of this data structure? We can try to use it to find data first, let’s say we want to find 15 in this binary search tree.

Step1

Firstly, search down from the position of the root node, and find that the data at the root node is 16, 15<16, then it can be inferred that 15 should be in the left subtree of the current node, so we search in the left subtree.

Step2

At this time, it comes to the left subtree and compares it with the root node of the left subtree. If 15>10 is found, 15 should be in the right subtree of the current node, so it should look for it in the right subtree.

Step3

At this point, the data of the current root node is 14. If 15>14 is found, the right subtree of the current node should be searched.

Step4

Once again, we go to the right subtree, and we find that the root node is exactly 15, and we finally find the data we want.

thinking

Simply recall the above process, it is not difficult to find that in the process of searching for data, we do not need to traverse every node in the whole search tree, we only need to compare the value of each search with that of the current node:

  • If it is less than the value of the current node, go to the left subtree and ignore the right subtree completely

  • If the value is greater than the value of the current node, go to the right subtree and ignore the left subtree completely

  • If it is equal to the value of the current node, data is found

It is not difficult to see that this is actually a binary process. Assuming that there are N nodes in the binary search tree and the number of nodes in the left and right subtrees of each node is approximately the same, it can be inferred that the search efficiency of the binary search tree is O(logN).

See here may be many students will think, since the search efficiency of binary search tree has been approximately **O(logN)**, is a very good efficiency, why there is almost no binary search tree shadow in practical application? Because binary search trees are not stable, why not? Let’s look at the following case.

Special case

The figure is also a binary search tree. If you want to see if this binary search tree also has data 15, what is the search efficiency?

Step1

First, search down from the position of the root node, and find that the data at the root node is 10, 15>10. Then it can be inferred that 15 should be in the right subtree of the current node, so we search in the right subtree.

Step2

If the root node is 11, 15>11, go to the right subtree of the current node again.

Step3

Go to the root node of the new tree and find that the current node 13 is still less than 15. Go to the right subtree of the current node again.

Step4

Finally, the latest subtree is found and the current root node value is 15.

Analysis of the

Analysis the search process, it is easy to find a binary search tree in this case (commonly referred to as single branches of the tree), search efficiency decreased, assuming that binary search tree or a total of N nodes, but one of the taller trees formed above the single branches of the tree, and the single number is greater than the other branches of the tree node is a tree or another is the tree node number is negligible, So when we’re looking for data, once the data we’re looking for is on a single tree, the efficiency might go down to O(N). Therefore, it is this instability in efficiency that makes binary search trees generally only exist in teaching materials as an explanation, and rarely used in practical scenarios.

summary

  1. In general, the search efficiency of binary search tree is order logN.
  2. In the case of single branch tree, the search efficiency of binary search tree is reduced to O(N).

The latter

For search tree, we generally used for search, so only introduce binary search tree search process, insert and delete process is similar to it, interested students can start their own push! Next time I’ll show you an AVL tree!

I am uneducated, if there is any mistake, but also hope you forgive me, not stingy advice!

Those who like this article, welcome to pay attention to the public accountLei Zi’s world of programming, practice more martial arts secrets.​

One key three even is the contemporary virtue of the Chinese nation!