2008级计算机 内部资料,仅供课堂教 only genuine AVL nodes The benefit of implementing AVL nodes with a derived structure is the reuse of all of our functions for processing nodes of binary trees and search trees. Methods for Balance Factors P. 475 o We often invoke these methods through pointers to nodes, such as left->get balance( ) But left could the compiler) point to any Binary node, not just to an AVL node, and these methods are declared only AVL node A C++ compiler must reject a call such as left->get balance( ) since left might point to a Binary node that is not an avl node Dummy Methods and Virtual Methods P 475-476 To enable calls such as left->get balance(), we include dummy versions of get balance()and set balance() in the underlying Binary node structure. These do nothing: P. 476 The correct choice between the AVL version and the dummy version of the method can only be made at run time, when the type of the object *left is known We therefore declare the binary node versions of set balance and get balance as virtual methods, selected at run time: P 476 Class Declaration for AVl Trees P 476 e We must override the earlier insertion and deletion functions for binary search trees with versions that maintain the balanced structure of av trees e All other binary search tree methods can be inherited without any changes P.476 The inherited data member of this class is the pointer root, which has type Binary node< Record > and thus can store the address of either an ordinary binary tree node or an AVL tree node We must ensure that the overridden insert method only creates nodes of type AVL node; doing so will guarantee that all nodes reached via the root pointer of an AVl tree are AVL nodes 10.4.2 Insertions into an Avl tree P. 477 Public insertion method Recursive Function Specifications P 479 Rotations of an avl tree P 481 Double Rotation P 481-483 3 Removal of a Node P 484-485 1. Reduce the problem to the case when the node x to be removed has at most one child 2. Delete x. We use a bool variable shorter to show if the height of a subtree has been shortened 3. While shorter is true do the following steps for each node p on the path from the parent of x to the root of the tree. When shorter becomes false, the algorithm terminates 4. Case 1: Node p has balance factor equal. The balance factor of p is changed according as its left or right subtree has been shortened. and shorter becomes false 5. Case 2: The balance factor of p is not equal, and the taller subtree was shortened. Change the balance factor of p to equal, and leave shorter as true. 6. Case 3: The balance factor of p is not equal, and the shorter subtree was shortened. Apply a rotation as follows to restore balance. Let q be the root of the taller subtree of p 7. Case 3a: The balance factor of q is equal. A single rotation restores balance, and shorter becomes false 8. Case 3b: The balance factor of q is the same as that of p. Apply a single rotation, set the balance factors of p and q to equal, and leave shorter as true 9. Case 3c: The balance factors of p and q are opposite. Apply a double rotation(first around q, then around p ), set the balance factor of the new root to equal and the other balance factors as appropriate, and leave shorter as Sample cases, deletion from an AVL tree P. 486 Example of deletion from an AVL tree P 487 10.4.4 Analysis of AVL Trees P 485 The number of recursive calls to insert a new node can be as large as the height of the tree At most one(single or double) rotation will be done per insertion A rotation improves the balance of the tree, so later insertions are less likely to require rotations It is very difficult to find the height of the average AVL tree, but the worst case is much easier. The worst-case behavior of AVl trees is essentially no worse than the behavior of random search trees Empirical evidence suggests that the average behavior of AVl trees is much better than that of random trees almost as good as that which could be obtained from a perfectly balanced tree P.485 o To find the maximum height of an avl tree with n nodes. we instead find the minimum number of nodes that an avl tree of height h can have2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 only genuine AVL nodes. ⚫ The benefit of implementing AVL nodes with a derived structure is the reuse of all of our functions for processing nodes of binary trees and search trees. Methods for Balance Factors P. 475 ⚫ We often invoke these methods through pointers to nodes, such as left->get_balance( ). But left could (for the compiler) point to any Binary_node, not just to an AVL_node, and these methods are declared only for AVL_node. ⚫ A C++ compiler must reject a call such as left->get_balance( ), since left might point to a Binary_node that is not an AVL_node. Dummy Methods and Virtual Methods P. 475-476 ⚫ To enable calls such as left->get_balance( ), we include dummy versions of get _balance( ) and set_ balance( ) in the underlying Binary_node structure. These do nothing: P. 476 ⚫ The correct choice between the AVL version and the dummy version of the method can only be made at run time, when the type of the object *left is known. ⚫ We therefore declare the Binary_node versions of set_balance and get_balance as virtual methods, selected at run time: P. 476 Class Declaration for AVL Trees P. 476 ⚫ We must override the earlier insertion and deletion functions for binary search trees with versions that maintain the balanced structure of AVL trees. ⚫ All other binary search tree methods can be inherited without any changes. P. 476 ⚫ The inherited data member of this class is the pointer root, which has type Binary_node<Record > * and thus can store the address of either an ordinary binary tree node or an AVL tree node. ⚫ We must ensure that the overridden insert method only creates nodes of type AVL_node; doing so will guarantee that all nodes reached via the root pointer of an AVL tree are AVL nodes. 10.4.2 Insertions into an AVL tree P. 477 Public Insertion Method P. 478 Recursive Function Specifications P. 479 Rotations of an AVL Tree P. 481 Double Rotation P. 481-483 10.4.3 Removal of a Node P. 484-485 1. Reduce the problem to the case when the node x to be removed has at most one child. 2. Delete x . We use a bool variable shorter to show if the height of a subtree has been shortened. 3. While shorter is true do the following steps for each node p on the path from the parent of x to the root of the tree. When shorter becomes false, the algorithm terminates. 4. Case 1: Node p has balance factor equal. The balance factor of p is changed according as its left or right subtree has been shortened, and shorter becomes false. 5. Case 2: The balance factor of p is not equal, and the taller subtree was shortened. Change the balance factor of p to equal, and leave shorter as true. 6. Case 3: The balance factor of p is not equal, and the shorter subtree was shortened. Apply a rotation as follows to restore balance. Let q be the root of the taller subtree of p . 7. Case 3a: The balance factor of q is equal. A single rotation restores balance, and shorter becomes false. 8. Case 3b: The balance factor of q is the same as that of p . Apply a single rotation, set the balance factors of p and q to equal, and leave shorter as true. 9. Case 3c: The balance factors of p and q are opposite. Apply a double rotation (first around q , then around p ), set the balance factor of the new root to equal and the other balance factors as appropriate, and leave shorter as true. Sample cases, deletion from an AVL tree P. 486 Example of deletion from an AVL tree P. 487 10.4.4 Analysis of AVL Trees P. 485 ⚫ The number of recursive calls to insert a new node can be as large as the height of the tree. ⚫ At most one (single or double) rotation will be done per insertion. ⚫ A rotation improves the balance of the tree, so later insertions are less likely to require rotations. ⚫ It is very difficult to find the height of the average AVL tree, but the worst case is much easier. The worst-case behavior of AVL trees is essentially no worse than the behavior of random search trees. ⚫ Empirical evidence suggests that the average behavior of AVL trees is much better than that of random trees, almost as good as that which could be obtained from a perfectly balanced tree. Worst-Case AVL Trees P. 485 ⚫ To find the maximum height of an AVL tree with n nodes, we instead find the minimum number of nodes that an AVL tree of height h can have