The time required to query/add/delete a search tree is proportional to the height h of the tree, but not proportional to the capacity n of the tree. If we can keep the tree short and thick, that is, keep H around O(lg n), then it will save time to complete the above work. A search tree that can always keep a good figure and will not grow crooked because of additions and deletions is called a balanced search tree.

Rotation-a small operation that does not destroy the characteristics of small left and large right.

There are many kinds of balanced trees, among which several trees are kept balanced by plastic surgery:

X and y in the figure are nodes; A, b and c are a whole string of subtrees. Imagine: if x is y's left child; Now you want to change X to parent, how should you change the rest of the tree? Y must be right-handed, so as to maintain the characteristics of BST-small left and big right. As for the other parts under X and Y, the whole string of subtrees can be treated together: the original left subtree of X (a) is still the left subtree of X after adjustment; Y's original right subtree (C) is still the right subtree of Y after adjustment; And the original right subtree (B) of X, after adjustment, naturally there is only one place to put it: it becomes the left subtree of Y, and these rules don't need to be remembered, because if you want to keep the characteristics of BST after adjustment, this is the only answer. Draw two values of x and y on the number axis and three strings of values in three subtrees of A, B and C to see more clearly:

- x - y -

B.C.

This action is called turning to the right or clockwise. The original parent (y) is called pivot, and the original child (x) is called rotator.

On the other hand, if the original tree looks like the right picture and wants to change it to the left picture, it is called turning left or counterclockwise. The original parent (x) is called pivot, and the original child (y) is called rotator. The subtree of a binary balanced tree has roots, the right subtree is X, the root of the left subtree is RootL, and the two subtrees of the left subtree are LLeftChild and LRightChild respectively. After right rotation, the Root of this subtree is RootL, the left subtree is LLeftChild, the Root of the right subtree is root, and the two subtrees of root are LRightChild (left) and X (right) respectively.

How many nodes are there in the old parent-child tree? How many nodes are there in the subtree on the right? How many nodes are there in the left and right subtrees of the new parent node after rotation? It is found that the right-hand effect will move the center of gravity of the tree to the right; The left-handed effect is to move the center of gravity of the tree to the left. If your tree has experienced many vicissitudes such as insertion/removal, the longer it grows, the more curved it becomes. If you rotate it at the right time, won't it be short, fat and beautiful again? Therefore, the left hand and the right hand are the basic operations used by several balance trees; It's just that the balance tree is different and the timing/conditions of operation are different.

A tree with symmetrical left and right child nodes is a balanced tree, otherwise it is an unbalanced tree.

An unbalanced tree will affect the efficiency of querying, inserting and deleting data in the tree. For example, when a binary tree is extremely unbalanced, that is, all nodes are on the same side of the root and the tree has no branches, it becomes a linked list. The arrangement of data is one-dimensional rather than two-dimensional. In this case, the search speed drops to O(N) instead of O(logN) of the balanced binary tree.

In order to search for a tree in a faster time O(logN), it is necessary to ensure that the tree is always balanced (or at least most of it is balanced). That is to say, for each node in the tree, the number of descendants on the left and the number of descendants on the right should be roughly equal.