The relationship between balanced binary trees and binary sorted trees

There is no direct relationship between balanced binary trees and binary sorting trees, but the search efficiency of binary sorting trees is related to the shape of the binary tree. So when we want the shape of the binary sorting tree to be uniform, like this Binary trees are called balanced binary trees.

##1. Binary sorting tree

Binary Sort Tree, also known as

Binary Search Tree (Binary Search Tree), also known as Binary Search Tree.

• Binary sorting tree definition:

A binary sorting tree is either an empty tree, or has the following properties Binary tree:

If the left subtree is not empty, then the values ​​of all nodes on the left subtree are less than the value of its root node;
1. If the right subtree is not empty, then The values ​​of all nodes on the right subtree are greater than the value of its root node;
2. The left and right subtrees are also binary sorted trees respectively.

As shown in the figure below, it is a binary sorting tree:

Perform in-order traversal on the binary sorting tree to get a sorted by keyword Sequence, for example, an in-order traversal of the above figure can obtain an ordered sequence: 10, 42, 45, 55, 58, 63, 67, 70, 83, 90, 98

• Search analysis of binary sorting tree

In terms of the average time performance of the search, the search on the binary sorting tree is similar to the half search, but in terms of maintaining the orderliness of the table In terms of efficiency, the binary sorted tree is more efficient because it does not need to move nodes, but only needs to modify the pointer to complete the insertion and deletion operations of the binary sorted tree.

Binary sorted tree search In the worst case, the search time required depends on the

depth of the tree:

1. When the binary sorting tree is close to full binary tree, its depth is $\#\#lo{}_{\mathrm{}}n$, so the worst-case search time is O($lo{}_{\mathrm{}}n$When the binary tree forms a single-branch tree as shown in the figure below, its depth is n, and the search time in the worst case is O(n), which is of the same order of magnitude as the sequential search.
2. SoIn order to ensure a high search speed for binary sorting tree search, we hope that the binary tree is close to a full binary tree, or that the left and right subtree depths of each node of the binary tree are as equal as possible
   
   2. Balanced Binary Tree
Through the above analysis, it can be seen that the search efficiency of the binary sorting tree is related to the shape of the binary tree. We hope that the shape of the binary sorting tree is Uniform, such a binary tree is called a balanced binary tree.

• Definition of balanced binary tree
  Balanced Binary Tree (Balanced Binary Tree), it is an empty tree, or has the following properties:

1. The absolute value of the depth difference between its left and right subtrees does not exceed 1;
2. Its left and right subtrees are also balanced binary trees respectively.

The depth of the left subtree of a binary tree node minus the depth of its right subtree is called balance factor BF. Then it is only possible to balance the balance factors of all nodes on the binary tree. They are -1, 0 and 1. The one on the left in the figure below is a balanced binary tree, and the one on the right is an unbalanced binary tree.

Because the difference between the depths of the left and right subtrees of any node on a balanced binary tree will not exceed 1, it can be proved that its depth is the same as the depth of a complete binary tree with n nodes$\lfloor lo{g}_{2}n\rfloor$ 1 is of the same order of magnitude. Therefore, its average number of searches is also $\#\#\lfloor log{}_{\mathrm{n}}\rfloor \#\#\backslash lfloor\; log\_2n\; \backslash rfloor$AVL tree. The minimum balanced subtree refers to the subtree which is the node closest to the inserted node and whose absolute value of the balance factor is greater than 1 as the root node.

• There are generally four situations for adjusting the minimum unbalanced subtree:

1. One-way right rotation (LL type): The insertion position is the left subtree of the left subtree, and the left subtree is used as the axis to perform a single right rotation, as shown in the figure below. The number next to the node is the balance factor of the node, and the I node is the currently inserted node (if the I node is in the middle, it means that the I node can be either a left child or a right child.

Note LL Type, rotate with the middle node as the axis. Why here I is the left child of BL cannot use B-BL-I as the LL type, because the A node is the closest balance to the I node For subtrees with factor absolute value > 1, the absolute values ​​of balance factors of other nodes do not exceed 1; similarly, when I is the right child of BL, B-BL-I cannot be regarded as LR type .
2.
One-way left rotation (RR type): Insert the right subtree whose position is the right subtree, and the right subtree is the axis, and perform a single Rotate to the left

Pay attention to the RR type and rotate with the middle node as the axis. Here I is the left and right subtrees and does not affect the actual RR type. The principle is the same as above.

3.
Bidirectional rotation first left and then right (LR type): insert the right subtree whose position is the left subtree, and perform two rotations, first to the left and then to the right.

Insert the node as the left child: pay attention to why

cannot use B-C-I as a subtree to define it as RL type. The principle is the same as the explanation in RR type. For LR type, the R end or L is close to the inserted node. The end is used as the axis of rotation (as shown in the figure below, it is equivalent to first rotating the subtree with B as the root to become an LL shape, and then rotating the subtree with A as the root).
Insert the node to the right Child:

4.
Two-way rotation first right and then left (RL type): Insert the left subtree whose position is the right subtree, make two adjustments, first rotate right and then rotate left; The processing situation is similar to LR.

Insert the node as the left child:

Insert the node as the right child:

After the above We can find that the balance factor has a great relationship with the type.

It is necessary to use the node closest to the inserted node and the absolute value of the balance factor > 1 as the subtree of the root node to determine which type it is .

• Exercise

As shown in the figure below, first insert node 2 to become an LL type, and then balance it after the overall right-hand processing.

After inserting 8 and 6 in sequence, the absolute value of the balance factor of node 5 is >1, becoming an RL type, so first take 5 as the root node and right-rotate its subtree 8-6 (becoming RR type), and then rotate the entire tree with 5 as the root node left-rotated.

After continuing to insert node 9, the balance factor of node 4 is > 1, becoming the RR type, so 4 is the root node , turn the whole thing to the left.

The above is the detailed content of The relationship between balanced binary trees and binary sorted trees. For more information, please follow other related articles on the PHP Chinese website!