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

What this article shares with you is about the relationship between balanced binary tree and binary sort tree. The editor thinks it is very practical, so I share it with you to learn. I hope you can get something after reading this article. Let's take a look at it with the editor.

There is no direct relationship between balanced binary tree and binary sort tree, but the search efficiency of binary sort tree is related to the shape of binary tree, so when we want the shape of binary sort tree to be uniform, such binary tree is called balanced binary tree.

1. Binary sort tree

Binary sort tree (Binary Sort Tree), also known as binary search tree (Binary Search Tree), also known as binary search tree.

Binary sort tree definition:

A binary sort tree is either an empty tree or a binary tree with the following properties:

If the left subtree is not empty, the value of all nodes on the left subtree is less than the value of its root node; if the right subtree is not empty, the value of all nodes on the right subtree is greater than the value of its root node; the left and right subtrees are also binary sort trees.

As shown in the figure below is a binary sort tree:

A sequence sorted by keywords can be obtained by traversing the binary sort tree in the middle order. for example, an ordered sequence can be obtained by traversing the above picture in the middle order: 10meme42, 45, 5, 5, 58, 63, 67, 67, 70, 83, 90, 98

Search and Analysis of binary sort Tree

In terms of the average time performance of the search, the search on the binary sort tree is similar to the half search, but in terms of maintaining the ordering of the table, the binary sort tree is more efficient because it does not need to move the node. you only need to modify the pointer to complete the insertion and deletion of the binary sort tree.

Binary sort tree lookup in the worst case, the search time required depends on the depth of the tree:

When the binary sort tree is close to the full binary tree, its depth is log2n, so the search time in the worst case is O (log2n), which is the same order of magnitude as the half search. When the binary tree forms a single branch tree as shown in the following figure, its depth is n, and in the worst case, the search time is O (n), which belongs to the same number as the sequential search.

Therefore, in order to ensure the high search speed of the binary sort tree, we hope that the binary tree is close to the full binary tree, or the depth of the left and right subtrees of each node of the binary tree is as deep as 2. Balanced binary tree

Through the above analysis, we know that the search efficiency of the binary sort tree is related to the shape of the binary tree, we hope that the shape of the binary sort tree is uniform, such a binary tree is called a balanced binary tree.

Balanced binary tree definition

Balanced binary tree (Balanced Binary Tree), which is an empty tree, or has the following properties: the absolute value of the depth difference between its left and right subtrees is not more than 1; its left and right subtrees are also balanced binary trees.

The depth of the left subtree of the binary tree node minus the depth of its right subtree is called the balance factor BF, then the balance factor of all nodes on the balanced binary tree can only be-1, 0 and 1, such as the balanced binary tree on the left and the unbalanced binary tree on the right.

Because the difference between the depth of the left subtree and the right subtree of any node on the balanced binary tree will not exceed 1, it can be proved that its depth is of the same order of magnitude as the depth of the complete binary tree with n nodes ⌊ log2n ⌋ + 1. Therefore, its average number of searches is of the same order of magnitude as ⌊ log2n ⌋ + 1.

To construct a balanced binary tree, Georgii M. Adelson-Velskii and Evgenii M. Landis proposed a method of dynamically maintaining a binary balanced tree. The basic idea is: when constructing a binary sorting tree, whenever inserting a node, first check whether the balance of the tree is destroyed by inserting nodes. If so, find out the minimum unbalanced subtree, under the premise of maintaining the sort tree. The connection relationship between the nodes in the minimum unbalanced subtree is adjusted to achieve a new balance, so the balanced binary tree is referred to as the AVL tree. The minimum balanced subtree refers to the subtree of the root node which is closest to the inserted node and the absolute value of the balance factor is greater than 1.

There are generally four cases of adjusting the minimum unbalanced subtree: unidirectional right rotation (LL type): insert the left subtree of the left subtree with the left subtree as the axis and rotate to the right once, as shown in the following figure. 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.

Pay attention to the LL type, which rotates around the middle node. Why the left child of BL here cannot regard B-BL-I as the LL type, it is because node An is the subtree where the absolute value of the balance factor of the nearest node is greater than 1, and the absolute value of the balance factor of the other nodes is not more than 1; similarly, when I is the right child of BL, B-BL-I cannot be regarded as LR type.

two。 Unidirectional left rotation (RR type): insert the right subtree of the right subtree, with the right subtree as the axis, and make a single rotation to the left

Pay attention to the RR type, which rotates around the middle node. Here I is the left and right subtree does not affect the RR type, the principle is the same as above.

3. Two-way rotation first left then right (LR type): insert the right subtree whose position is the left subtree, to rotate twice, first to the left, then to the right.

The insertion node is the left child: pay attention to why B-C-I can not be defined as the RR type as a subtree, the principle is the same as the explanation in the RR type, for the LR type, the R end or L near the insertion node end is used as the rotation axis (such as the following figure is equivalent to first rotating the subtree with B as the root, and then rotating the subtree with An as the root).

The insertion node is the right child:

4. Two-way rotation first right then left (RL type): insert the left subtree whose position is the right subtree and make two adjustments, first right and then left; the treatment is similar to that of LR.

The insertion node is the left child:

The insertion node is the right child:

Through the above, we can find that the balance factor has a great relationship with the type, and it is necessary to use the node closest to the insertion node and the absolute value of the balance factor > 1 as the subtree of the root node to determine which type.

Practice

As shown in the following figure, node 2 is first inserted into an LL type, and then balanced after the overall right-handed processing.

After inserting 8 and 6 in turn, the absolute value of the balance factor of node 5 is more than 1, which becomes RR type, so the subtree 8-6 is rotated to the right (RR type) with 5 as the root node, and then the whole tree with 5 as the root node is rotated to the left.

After continuing to insert node 9, the balance factor of node 4 is more than 1, which becomes RR type, so with 4 as the root node, the whole left-handed node will be turned.

Undefined

The above is the relationship between the balanced binary tree and the binary sort tree. The editor believes that there are some knowledge points that we may see or use in our daily work. I hope you can learn more from this article. For more details, please follow the industry information channel.

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.