Guys, I am Zhang Shuxin, today to share with you is the common three binary tree: complete binary tree, balanced binary tree, binary search tree, as for the title of 3 minutes of understanding is my gibberish, can so fast to see your ability to understand ha ha.

Complete binary tree

A complete binary tree is a special binary tree that meets the following requirements:

  1. All leaf nodes appear in layer K or K-1, and the maximum number of nodes must be reached from layer 1 to layer K-1.

  2. The KTH layer may not be full, but all nodes of the KTH layer must be concentrated on the far left. It is important not to be confused with “full binary trees”. A complete binary tree does not require all trees to have left and right subtrees, but it does require:

  3. No node can have a left subtree without a right subtree

  4. The leaf nodes appear in the last or penultimate layer and cannot go any higher

Here’s a picture of a “complete binary tree” versus a “full binary tree” :

When we implement a complete binary tree with an array, leaf nodes can be added to the array from top to bottom and left to right, and then knowing the location of a node, we can easily calculate the location of its parent node and child node.

Take the complete binary tree in the figure above as an example. The node labeled 2 is also at position 2 in the array. Its parent node is (k/2 = 1), and its children are (2k=4) and (2k+1=5), as well as other nodes.

Complete binary tree usage scenarios:

According to the previous study, we know that the characteristics of a complete binary tree are: “the position of leaf nodes is relatively regular”. So you can use it when you sort or look up data, like heap sort, which we’ll talk about later.

Binary search tree

In fact, the binary tree is mainly proposed to improve the search efficiency. For example, when the commonly used HashMap is dealing with serious hash conflicts, the search efficiency is reduced due to the excessively long zipper, so the red-black tree is introduced.

As we know, binary search can shorten the search time, but it requires that the search data must be in order. Every search, operation to maintain an ordered data set, so there is the concept of binary search tree.

Binary search tree (also called binary sort tree), it is a binary tree with the following properties:

  1. If the left subtree is not empty, the value of all nodes in the left subtree is less than the value of its root node.

  2. If the right subtree is not empty, the value of all nodes in the right subtree is greater than or equal to the value of its root node.

  3. The left and right subtrees are also binary sort trees respectively.

As shown below:

In other words, in a binary search tree, the left subtree is smaller than the node, and the right subtree is larger than the node, recursively defined.

According to the characteristic of binary sort tree, we can know that the middle order traversal of binary sort tree must be from small to large.

For example, the middle-order traversal results in:

1, 3, 4, 6, 7, 8, 10, 13, 14

Performance of binary sorting trees

In the best case, the search efficiency of binary sorting tree is O(logn), and its access performance is similar to split search.

But the worst case is O(n), where the inserted elements are ordered and the resulting binary sort tree is a linked list, in which case all the elements need to be traversed (see figure b below).

If we can ensure that the binary sort tree does not have the extreme case mentioned above (the inserted elements are ordered, resulting in a linked list), we can guarantee high efficiency.

But this is not easy to control when inserting ordered elements, and by the definition of a binary sort tree, we can’t tell if the current tree needs to be adjusted.

So that’s where the balanced binary tree comes in.

Balanced binary trees

The idea behind balanced binary trees is to make sure that the tree doesn’t tilt too much, that the two sides balance as much as possible. Thus it is defined as follows:

  1. A balanced binary tree is either an empty tree

  2. Or make sure the difference between the height of the left and right subtrees is no more than 1

  3. The subtree must also be a balanced binary tree

In other words, the height of the two left subtrees of the tree does not differ much.

So let’s go to the extreme case of the binary sort tree, and now use it to construct a balanced binary tree.

Take 12 as the root node, when 24 is added as its right subtree, the height difference between the left and right subtrees of the root node is 1, which is still balanced. Then add another element 28:

At this time, the root node 12 felt unbalanced, I had no children on the left and two children on the right, exceeding the maximum 1 I said before, no, please adjust it for me!

So we need to adjust the current tree structure to rotate it.

Since the last node is added to the right subtree of the right subtree, we need to find a way to add material to the left subtree of the right subtree, so we need to rotate counterclockwise to make 24 the root node, and 12 right to make 24 the left subtree, which looks like this:

At this point, the balance is restored, and the right subtree of 37 to 28 is still balanced:

If you add another 30, it needs to be at the left of 37:

At this point, we can see that the tree is unbalanced again. The tree with the root of 24 is obviously too heavy on the right and too thin on the left. To maintain balance, 24 has to give way to 28.

It’s a little ugly, but it keeps the balance.

Similarly, the balanced binary tree needs to rotate when adding and deleting to keep the whole tree balanced. After such a complicated internal work, when we use it, the time complexity of insertion and search is O(logn), which is quite good.

conclusion

After reading this article, I believe you have a deeper understanding of “complete binary tree, binary search tree and balanced binary tree” these three binary trees, with this foundation, then go to see B+ B- red black tree, it is relatively easy, if there is a chance later I will write two such.

Recommended reading

Guys, I’m off duty…

Summary of my half-year working experience in Android development

Java Foundation 5: A comprehensive understanding of automatic unpacking and common risks