Binary sort trees balance the efficiency of insertion and search well, but the efficiency of unbalanced binary sort trees is greatly reduced. The AVL tree introduced today is a solution to this problem.

define

Self-balancing Binary Search Tree (or height-balanced Binary Search Tree) is a Binary ranking Tree in which the Height difference between the left and right subtrees of each node is at most equal to 1. It is a highly balanced binary sort tree. This means that either it is an empty tree, or its left and right subtrees are both balanced binomial trees, and the absolute value of the depth difference between the left and right subtrees is no more than 1. We call the value of the left subtree depth minus the right subtree depth of the nodes in the binary tree Balance Factor (BF), so the Balance Factor of all nodes in the binary tree can only be -1, 0 and 1.

The following figure is not an AVL tree, because the height of the left subtree of node 18 is 2 and the height of the right subtree is 0, and the height difference is greater than 1.

However, it can be transformed into a balanced binary tree after some steps are adjusted, as shown in the following figure:

Realize the principle of

The basic idea of balanced binary tree construction is to check whether the balance of the tree is damaged due to insertion whenever a node is inserted in the process of binary sorting tree construction. If so, find the least unbalanced subtree. On the premise of keeping the characteristics of binary sorting tree, the link relation between nodes in the least unbalanced subtree is adjusted and the corresponding rotation is carried out to make it a new balanced subtree. The least unbalanced subtree refers to the root of the node closest to the inserted node whose absolute value of the balance factor is greater than 1.

The following is an example to understand the construction process of balanced binary tree.

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

The result is very bad for the search, the tree height is up to 8, and most have only one child. So we need to do something to turn it into an AVL tree.

First of all, when elements 3 and 2 are inserted, there is no effect. At this time, the balance factor of 3 is 0, and the balance factor of 1 and 2 is 0. The result is as follows:

Now, to insert 1 into the tree, the result should look like this:

Now the equilibrium factor of 3 is 2, which no longer conforms to the rule of balanced binary tree. In this case, the whole tree is the least unbalanced subtree and we rotate it right:

If 4 is inserted again, the balance will not be affected, and the result is as follows:

At this point, insert element 5, and the subtree with root node 3 becomes the least unbalanced subtree, as shown below:

Now to rotate it to the left:

Now continue to insert element 6, now the right subtree with root 2 is the least unbalanced subtree, the result is as follows:

This time, the left child of 4 needs to be turned to the right child of 2 to satisfy the definition of a binary sort tree, as shown below:

When 7 is inserted again, the situation is somewhat similar, and the result is as follows:

The result of left supination is as follows:

Now, insert 10 again, no adjustment required, and the result is as follows:

Next, insert element 9, and the result is as follows:

From our previous experience, we should be left-handed at this point, but after left-handedness, 9 will become a child to the right of 10, which doesn’t fit the definition of a binary sort tree. Unlike before, 7 and 10 have the opposite sign of the equilibrium factor, which is the reason for this result. In this case, the root node 10 should be first right-handed and then left-handed, as shown below:

Finally, insert element 8 as follows:

In this case, the situation is similar to the above, 6 is the root of the least unbalanced subtree, and the balance factor sign of 9 and 6 is opposite, so 9 is the root of dextral first:

And then 6 to the left:

As you can see, the height of the tree is only 4, a big difference from the previous 8, and the performance is much better.

Deletion of balanced binary trees is similar to insertion and will not be described here. You can figure out for yourself how to delete the element most efficiently, whether you have a leaf, one child, or two children, and you can use recursion.

Next we will introduce another implementation, red black trees.

Java set source code analysis of the basis (four) : binary sort tree

Java collection source code analysis foundation (six) : red black Tree (RB Tree)

This is the end of this article, if you like my article, you can follow my wechat official account: Big Paper Plane

Or scan the qr code below to add directly:

You can also follow me at github: github.com/LtLei/artic…

The path of programming is long and difficult. However, the road ahead is long, I see no end, I will search high and low.