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

Editor to share with you how to achieve balanced binary tree Java, I believe that most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to understand it!

1 Overview of balanced binary tree

In order to avoid the binary search tree degenerating into a linked list in extreme cases and affecting the search efficiency, we introduce a balanced binary tree, that is, to make the structure of the tree look "uniform" as much as possible, and the number of nodes and levels of the left and right subtrees as much as possible. If you want to learn to balance the binary tree and master it, you must first master the binary sort tree. If you do not quite understand the binary search tree, including why the binary sort tree may be reduced to a linked list, you can take a look at this article: data structure-the principle of binary sort tree and the complete implementation of Java code.

Balanced binary tree, also known as AVL tree, means that the value of all nodes in the left subtree is smaller than that of the root node, while the value of all nodes in the right subtree is larger than that of the root node, and the maximum height difference between the left subtree and the right subtree is 1. Therefore, the balanced binary tree satisfies the properties of all binary sort (search) trees and is developed on the basis of binary sort trees. As for AVL, it is named after two Russian scientists who invented the balanced binary tree: G. M. Adelson-Velsky and E. M. Landis.

In general, balanced binary trees have the following properties:

It must be a binary sort tree.

It is an empty tree or the absolute value of the height difference between its left and right subtrees is not more than 1, and the left and right subtrees are a balanced binary tree, recursively defined.

Balance factor BF (Balance Factor): we call the balance factor the value of the depth of the left subtree minus the depth of the right subtree of the nodes on the binary tree, then the balance factors of all nodes on the balanced binary tree can only be-1, 0 and 1. As long as the absolute value of the balance factor of a node on a binary tree is greater than 1, the binary tree is unbalanced.

In the above figure, figure 1 is a balanced binary tree. Figure 2 is 59 larger than 58, but it is the left subtree of 58, which does not meet the definition of binary sort tree, and figure 2 is not a balanced binary tree. The reason why figure 3 is not a balanced binary tree is that the left subtree height of node 58 is 3, while the right subtree is empty, and the difference between the two is greater than the absolute value 1, so it is not balanced either. After proper adjustment, figure 4 meets the definition, so it is a balanced binary tree.

Minimum unbalanced subtree: the node that is closest to the insertion or deletion node and the absolute value of the balance factor is greater than 1 is the root subtree, which is called the minimum unbalanced subtree. In the following figure, when node 37 is newly inserted, the node whose absolute value of the nearest balance factor is more than 1 is 58 (that is, its left subtree height 3 minus the right subtree height 1), so the subtree below 58 is the minimum unbalanced subtree.

2 the realization principle of balanced binary tree

The core of the implementation principle of balanced binary tree is that after inserting and deleting nodes, only the balance of those nodes on the path from the insertion point to the root node may be changed, because only the subtrees of these nodes may change. Therefore, we need to follow this path up to the root and update the balance information to try to find the minimum imbalance tree. On the premise of keeping the characteristics of the binary sorting tree, the relationship between the root node and the child node in the minimum unbalanced subtree is adjusted and the corresponding rotation is carried out to make it a new balanced subtree.

Let's take a look at the rebalancing of inserts first, because later we will find that the rebalancing operations of inserts and deletes are basically the same.

We call the node that needs to balance (the absolute value of the balance factor is greater than 1) x. Since any node has at most two sons, a height imbalance requires the height difference of two subtrees at point x. This imbalance can only occur in the following four situations:

Insert an element into the left subtree of the left child node of node X, referred to as LL

Insert an element into the right subtree of the left child node of node X, referred to as LR

Insert an element into the left subtree of the right child node of node X, referred to as RL

Insert an element into the right subtree of the right child node of node X, referred to as RR

Among them, the first case and the fourth case are symmetrical, which is called the "outside" situation, which can be solved by single rotation, while the second case and the third case are symmetrical, which is called the "inner side" situation. Double rotation is needed to solve the problem.

Case study: elements in the logarithm array {3pr 2je 1je 4je 5je 6je 7pr 16jr 15jr 14jr 13jr 12pr 11pr 10pr 8je 9} sequentially insert and build a balanced binary tree. Take this case as an example to explain the general solutions to the above four problems and the concepts of single rotation and double rotation.

2.1 single rotation

First of all, when the first two elements "3, 2" are added, the balanced binary tree can be constructed normally. When the third number is "1", it is found that the balance factor of the root node "3" becomes 2, and the whole tree becomes the minimum unbalanced subtree. Therefore, the structure needs to be adjusted.

The situation in the above figure meets the condition 1--LL, so a single rotation is used to rebalance. At this point, we need to turn right (clockwise). The purpose of rotation is actually to reduce the depth and maintain balance.

After node 3 is rotated to the right, node 2 becomes the root node, and node 3 becomes the right subtree of 2. At this time, the depth of tree node 1 is reduced by one level, and the whole tree returns to balance. The operation in which the balance can be repaired by a single rotation is called single rotation.

The node X whose absolute value of the balance factor BF is greater than 1 is called the imbalance point. It is very important to find the imbalance point when repairing a damaged AVL tree. Finding the imbalance point is the process of tracing back to the root node from the position of the newly inserted or deleted node.

Then we add node 4, and the balance factor is not out of range. When adding node 5, the BF value of node 3 is-2, which means it is going to rotate again.

The situation in the image above meets the condition 4--RR and requires a single rotation to rebalance. At this point, we need to turn left (counterclockwise).

After turning to the left, as on the right of the picture above, the depth of the tree is reduced by one level, and the whole tree is balanced again. Further, when we add node 6, we find that the BF value of root node 2 becomes-2, so we turn the root node to the left.

The result of left-handed rotation makes node 2 become the left child of node 4, and node 3, which is originally between 2 and 4, is the left subtree of 4. Because it needs to satisfy the characteristics of binary sorting tree after rotation, it becomes the right subtree of node 2. Because every key of the subtree is between 2 and 4, this transformation is true.

Now let's try to summarize the general solution when situations 1 and 4 occur.

First, cases 1 and 4 can extract a general model:

In the model, if the left subtree 1 is going to be unbalanced, then the depth of the left subtree 1 must be 2 layers deeper than that of the right subtree 1; if the right subtree is going to be unbalanced 4, then the depth of the left subtree 1 must be 2 layers lighter than that of the right subtree 1.

For cases 1 and 4 above, we use right-handed and left-handed, respectively, to reduce or increase the depth of the two subtrees:

As shown in the figure above, after case 1, K2 becomes the root node, K1 becomes the right child node of K2, and the right subtree 2 of K2 becomes the left subtree of K1; after the left rotation of case 4, K2 becomes the root node, K1 becomes the left child node of K2, and the left subtree 2 of K2 becomes the right subtree of K1. The tree has reached equilibrium again, which is the general solution of case 1 and case 4, and we can find that they are symmetrical.

Node 7 is added below, which causes the BF of node 5 to become-2, and conforms to case 4, which requires left-handed. According to the general solution above, use the following left-handed method to make the tree become a balanced binary tree again:

2.2 double rotation

The above single rotation is not useful for cases 2 and 3, because the tree structure is too deep at this time, and a single rotation does not reduce its depth. You need to use double rotation at this point.

When the node is added at 16:00, the structure does not change, and then by adding node 15, the BF of node 7 becomes-2. This fits case 3: insert an element, called RL for short, into the left subtree of the right child node of node X. As shown below:

At this time, simple left-handed can not solve the problem: node 15 becomes the right child of 16, which is not in line with the characteristics of binary sort tree, at this time can not be simple left-handed. As shown below:

For this case, we first build a broader model for key nodes 7, 16, and 15:

7-k1, 16-k2, 15-k3, and node 7 can also have left subtrees, node 16 can have right subtrees, and node 15 can have left and right subtrees.

If the BF of K1 above is-2, one of the subtrees of left subtree 2 or right subtree 2 is two layers deeper than left subtree 1, or they are both empty subtrees, but we don't know what the situation is, but it doesn't matter, here we ask for a general solution to this problem!

At this time, in order to balance the height, we can't take K1 as the root node, but left-handed-- using K2 as the root node will not solve the problem (as has been proved above). The only choice is to take K3 as the new root node. and first make K2 the right subtree of K3, and then K1 turns left into the left subtree of K3, and the left subtree 2 becomes the right subtree of K1, and the right subtree 2 becomes the left subtree of K2. This is completely true, and this is the general solution of case 3. Finally, the results of right-left double rotation are as follows:

We can see that no matter what happens (one of the subtrees of left subtree 2 or right subtree 2 is two layers deeper than that of left subtree 1, or they are both empty subtrees), after the left-right double rotation is transformed into the shape of the upper right image, the depth of left subtree 2 or right subtree 2 will be reduced by one layer, while the depth of left subtree 1 will be increased by one layer, this tree is always a balanced binary tree.

In fact, the process model of right-left double rotation and separate rotation is as follows:

Going back to the case, left subtree 2, right subtree 2, left subtree 1, and right subtree 1 are all empty trees. after using right-left double rotation, the tree structure is shown in the following figure, and the tree can be rebalanced:

Then insert 14, the situation is similar to just now, the BF of node 6 is-2, which is in line with the case of RL (the element is inserted in the left subtree 7 of the right child node 15 of node 6). The left is shown below, and the right-left double rotation continues, and the whole tree returns to balance, as shown on the right of the following figure:

Continue to insert 13, and the BF of root node 4 becomes-2, which matches case 4. In this case, a single left-handed rotation can be used to solve the problem:

After you continue to insert 12, go back up to node 14:00 and find that the BF of node 14 is 2. In this case, you need to restore balance by right-handed rotation.

After continuing to insert 11, go back up to node 15:00 and find that the BF of node 15 is 2. In this case, you need to restore balance by right-handed rotation.

After you continue to insert 10, go back up to node 12:00 and find that the BF of node 12 is 2. In this case, you need to restore balance by right-handed rotation.

After inserting 8, there is no minimum unbalanced tree going up to the root node, so there is no need to rotate. Finally, after inserting 9, we find that case 2 occurs, when we have the experience of symmetry in case 1 and case 4, and naturally we also know that a right-to-left double-spin symmetry operation-- left-right double rotation-- is needed to rebalance.

Let's first take a look at the left-right double spin model:

It and the right-left double spin model operate symmetrically, taking K3 as the new root node, and first making K2 turn into the left subtree of K3, and then K1 turning right into the right subtree of K3, and the left subtree 2 becomes the right subtree of K2, and the right subtree 2 becomes the left subtree of K1, which is completely true, which is the general solution of case 2.

After the left-right double spin, the balanced binary tree is reformed:

In fact, the process model of left-right double rotation and separate rotation is as follows:

After the nodes are added, a balanced binary tree is finally formed:

2.3 Summary

There are only four cases of imbalances in inserting nodes:

Insert an element into the left subtree of the left child node of node X, referred to as LL

Insert an element into the right subtree of the left child node of node X, referred to as LR

Insert an element into the left subtree of the right child node of node X, referred to as RL

Insert an element into the right subtree of the right child node of node X, referred to as RR

Among them, 1 uses single right-handed rotation and 4 uses single left-handed rotation to solve the problem. 2 and 3 are more complex, 2 need to use left-right double rotation, 3 need to use right-left double rotation.

1 and 4, 2 and 3 are symmetrical cases, and now taken together, the so-called rotation does not seem to be so complex, and we have found a general solution to these problems, which is equally applicable to the deletion of nodes. No longer need to consider a variety of special cases, very convenient, let's take a look at the specific code implementation!

3 Construction of balanced binary tree 3.1 class architecture

First of all, the node object still needs a data field and two reference domains, and there is an additional field of node height compared with the binary sort tree, which facilitates the calculation of the balance factor and provides a way to return the node height. You also need a reference to the comparator, because you need to sort the elements, so you naturally need to compare the size of the elements. if a comparator is passed externally, compare it with a user-specified comparator, otherwise, the data type E must be a subclass of the Comparable interface, otherwise an error will be reported because it cannot be compared.

In addition, you need to provide a method of traversing the middle order, which will display the results of the binary sort tree sequentially.

Public class AvlTree {/ * externally saves the reference to the root node * / private BinaryTreeNode root; / * * Custom comparator * / private Comparator

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.