This is probably the most difficult and most "useless" data structure in the entire "data structure" textbook (now there is also some algorithm content). Say it is useless, it is precisely because it is too useful - exactly the same interface interface with ordinary binary search trees, most of the case is high than ordinary binary search tree efficiency (a lot). Therefore, in general, people are always for all - reuse after writing, and will not write again. So, although you have finished the balance binary tree, it is likely that you will never write one. You now pull your individual, let him write one, I am afraid that there is not much, joking the word, and do not really.
Before I started writing, I was worried that I could write this part. After all, I was on the day of the Switch ... case, and it was just half - there was no left-handed handovered, and there was no deletion insertion. Later, I became confident - I didn't know clearly because I didn't say it. I said my dreams. I didn't find the inventor of the AVL tree (GM Adelson-Velskii and Ym Landis. An Algorithm for the Organization of Information. Soviet Math. Dokl., 3: 1259--1262, 1962.) I don't know what I wrote below. Is it reflected in the original meaning of inventors, but at least, I think the current textbook is intended to distort the inventors.
basic concepts
Ø Balance
The following citation from Algorithms and Data Structures (Niklaus Wirth, Prentice-Hall, Englewood Cliffs, NJ, 1986 ISBN: 0-13-022005-1 PP. 215 - 226)
One Such Definition of Balance Has Been Postulate by Adelson-Velskii and Landis [4-1]. The balance criterion is the folload:
A Tree is balanced if and only ing for every node the heights of its two subtrees diffrity by at Most 1.
Trees satisfying this condition are often called AVL-trees (after their inventors). We shall simply call them balanced trees because this balance criterion appears a most suitable one. (Note that all perfectly balanced trees are also AVL-balanced.)
The Definition IS Not Only Simple, But It Also Leads To a Manageable Rebalance Procedure and an average search path length detene identically balanced Tree.
Science and technology is more good, my translation level is relatively poor, I don't show ugly, I just want everyone to pay attention to the final line of the line, the balance should be easy to operate, and it is never seen in the book. Switch ... case.
Ø Rotate
Balance is rotated. Participating in rotation is 3 nodes (one of which may be external node null), rotation is to transfer these 3 nodes. Note that when left-handed, P-> Right must not be empty, and P-> Left is not empty, which is obvious. p
pp
Left rotation
t
t
(p)
(NULL)
(NULL)
It can be seen that Left-6 is indeed rotating to "left" or very image. The right rotation is the image of the left-handed image, no longer explained. The table below is a pointer transformation of left-handed and right-handed nodes. (Brackets indicate NULL conditions)
Left-handed right-handed T-> Parent = P-> Parent P-> Parent = T t-> Parent = P-> Parent P-> Parent = T (t-> left-> parent = P) P-> Right = T -> Left (t-> right-> parent = p) P-> Left = t-> Right T-> LEFT = PP = T t-> Right = PP = T
Ø Balance factor (BF - Balance Factor)
The balance of the AVL tree relies on whether equilibrium is required, depending on whether there is an imbalance in the tree. In order to avoid each judgment balance, the height of the left and right subtroes is obtained, and the balance factor is introduced. It is probably 1962, AV & L did not give a definition in person, and the definition of balance factors in the times. I saw 4 books, the two is BF = left high - the right high, the two is bf = right high - left high. The most interesting thing is a left left drop in the two Chinese (Yan Weimin and Yin Kun), one right reduction; two foreign people write it. Although there is nothing in principle, it is better for China's students - when you are, no matter which mission you are. I take care of my habits, the following BF = left high - the right high, the habits are different, please pay attention.
In this way, whether it is necessary to equilibrate the conditions very clear - | bf |> 1. If it is built from the empty tree, the balance is always balanced, then the imbalance occurs only in the inserted deletion operation, and the unbalanced flag is a node that appears BF == 2 or BF == -2.
Insert and delete
Insert and delete the AVL tree, actually insert and delete the ordinary binary search tree, and then balance. It is certain that the maximum number of balances required to insert and delete (the root cause will be given below), but this does not indicate that the insertion and deletion of balanced ideas have a big difference. Existing textbooks, only from the surface, there is a different number of faders, but not fundamentally recognize the essence of insertion and deleting symmetry, and getting messy (Switch ... case), it is still serious. Mislept readers - think that it is unpredictable to delete operation.
The AVL tree reflects a balanced beauty. Two rotations are mirrors, insertion deletion is the operation of mirroring, there is no reason to have a big difference. In fact, balance can be unified:
1. While (Current! = NULL) Modify the balance factor of the Current.
Ø When inserted into the node, current-> bf = (current-> DATA> * P)? 1: -1; Ø Current-> bf - = (Current-> DATA> * P)? 1: -1;
Ø CURRENT points to the parent node of the insertion node or actually deletes the node, which is the result of the insertion and deletion of the ordinary binary search tree. * p The initial value is a DATA that is inserted or actually deleted. Because the delete operation may be deleted not Data.
2. Determine if equilibration needs
IF (current-> bf == -2) l_balance (c_root); Else if (current-> bf == 2) r_balance (c_root);
3. Do you want to continue to modify the balance factor of the parent node
Ø When the node is inserted, if (! Current-> bf) Break; this, the height of the subtree of the root is the same as the height of the subtree of the root.
Ø Delete the node if (current-> bf) Break; then, the height of the subtree of the root is the same as the height of the subtree of the root.
Ø The reason why the ability to delete the operation is much more, that is, because equilibrification does not increase the height of the subtree, it may reduce the height of the subtree, and it is possible to increase the insertion operation of the tree, once a balance can be offset. The increase is increased; in the delete operation that is likely to reduce the tree, the balance can bring the imbalance of ancestor nodes.
4. The current node moves to the parent node, turn 1
P = & (current-> data); current = current-> parent;
The complete insertion deletion function is as follows:
Bool Insert (Const T & DATA)
{
IF (! bstree
While (Current)
{
Current-> BF = (Current-> DATA> * P)? 1: -1;
IF (Current-> BF == -2) l_balance (c_root);
Else if (Current-> bf == 2) r_balance (c_root);
IF (! Current-> BF) Break;
P = & (current-> data); current = current-> parent;
}
Return True;
}
Bool Remove (Const T & DATA)
{
IF (! bstree
// Add protECETED: T r_r_data in Class BStree, modified to Data of the actual deleted node in BSTREE
While (Current)
{
Current-> bf - = (Current-> DATA> * P)? 1: -1;
IF (Current-> BF == -2) l_balance (c_root);
Else if (Current-> bf == 2) r_balance (c_root);
IF (Current-> BF) Break;
P = & (current-> data); current = current-> parent;}
Return True;
}
You can see, how much they are.
