2008级计算机 内部资料,仅供课堂教学使用 Chapter 10 BINARY TREES P. 429 1. General Binary Trees 3. Buildi Binary Search Tree 2. Binary Search Trees 4. Height Balance: AVL Trees 110.1 General Binary Trees Binary Trees P 430 10.1.1 DEFINITION: A binary tree is either empty, or it consists of a node called the root together with two binary trees called the left subtree and the right subtree of the root 1.2 Traversal of Binary Tree At a given node there are three tasks to do in some order: Visit the node itself (V); traverse its left subtree (L); traverse its right subtree (R). There are six ways to arrange these tasks VLR LVR LRV VRL RVL RL V By standard convention, these are reduced to three by considering only the ways in which the left subtree is traversed before the right V LR: preorder LVR inorder LR V: postorder These three names are chosen according to the step at which the given node is visited With preorder traversal we first visit a node, then traverse its left subtree, and then traverse its right subtree With inorder traversal we first traverse the left subtree then visit the node and then traverse its righ subtree ■With the left subtree. then traverse the right subtr and finally visit Expression Trees P. 435 tree of the quadratic formula P 436 10.1.3 Linked Binary Trees Comparison tree: P. 430 Linked implementation of binary tree: P. 439 Linked Binary Tree Specifications P 437-438 Binary tree class: P. 438 Binary node class: P 438 Constructor: P. 438 Empty: P. 438 10. 2| Binary Search Trees Can we find an implementation for ordered lists in which we can search quickly (as with binary search on a contiguous list) and in which we can make insertions and deletions quickly (as with a linked list)? DEFINITION: A binary search tree is a binary tree that is either empty or in which the data entry of every node has a key and satisfies the conditions The key of the left child of a node(if it exists) is less than the key of its parent node The key of the right child of a node (if it exists) is greater than the key of its parent node The left and right subtrees of the root are again binary search trees We always require: No two entries in a binary search tree may have equal keys We can regard binary search trees as a new AD We may regard binary search trees as a specialization of binary trees We may study binary search trees as a new implementation of the ADT ordered list 10. 2. 1 The Binary Search Tree Class The binary search tree class will be derived from the binary tree class, hence all binary tree methods are inherited P.446 The inherited methods include the constructors, the destructor, clear, empty, size, height, and the traversals reorder,inorder, and postorder A binary search tree also admits specialized methods called insert, remove, and tree search be compared with the usual comparison operators. By casting records to their corresponding keys, the s can The class Record has the behavior outlined in Chapter 7: Each Record is associated with a Key. The keys can comparison operators apply to records as well as to keys 10.2.2 Tree Search P 447 Error code Search tree: tree search( Record &target)const; P 447 This method will often be called with a parameter target that contains only a key value. The method will fill target with the complete data belonging to any corresponding Record in the tree To search for the target, we first compare it with the entry at the root of the tree. If their keys match, then we are finished. Otherwise, we go to the left subtree or right subtree as appropriate and repeat the search in that subtree
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 Chapter 1 0 BINAR Y TREES P.429 ----------------------------------------------------------------------------------------------------------------------------- ---------- 1. General Binary Trees 2. Binary Search Trees 3. Building a Binary Search Tree 4. Height Balance: AVL Trees [10.1] General Binary Trees Binary Trees P. 430 10.1.1 DEFINITIO N: A binary tree is either empty, or it consists of a node called the root together with two binary trees called the left subtree and the right subtree of the root. 10.1.2 Traversal of Binary Trees P. 432 ⚫ At a given node there are three tasks to do in some order: Visit the node itself (V); traverse its left subtree (L); traverse its right subtree (R). There are six ways to arrange these tasks: V L R L V R L R V V R L R V L R L V. By standard convention, these are reduced to three by considering only the ways in which the left subtree is traversed before the right. V L R: preorder L V R: inorder L R V: postorder ⚫ These three names are chosen according to the step at which the given node is visited. ◼ With preorder traversal we first visit a node, then traverse its left subtree, and then traverse its right subtree. ◼ With inorder traversal we first traverse the left subtree, then visit the node, and then traverse its right subtree. ◼ With postorder traversal we first traverse the left subtree, then traverse the right subtree, and finally visit the node. Expression Trees P. 435 Expression tree of the quadratic formula P. 436 10.1.3 Linked Binary Trees Comparison tree: P. 430 Linked implementation of binary tree: P. 439 Linked Binary Tree Specifications P. 437-438 Binary tree class: P. 438 Binary node class: P. 438 Constructor: P. 438 Empty: P. 438 Inorder traversal: P. 439-440 Binary Tree Class Specification P. 441 [10.2] Binary Search Trees Can we find an implementation for ordered lists in which we can search quickly (as with binary search on a contiguous list) and in which we can make insertions and deletions quickly (as with a linked list)? DEFINITION: A binary search tree is a binary tree that is either empty or in which the data entry of every node has a key and satisfies the conditions: ◼ The key of the left child of a node (if it exists) is less than the key of its parent node. ◼ The key of the right child of a node (if it exists) is greater than the key of its parent node. ◼ The left and right subtrees of the root are again binary search trees. We always require: No two entries in a binary search tree may have equal keys. ⚫ We can regard binary search trees as a new ADT. ⚫ We may regard binary search trees as a specialization of binary trees. ⚫ We may study binary search trees as a new implementation of the ADT ordered list. 10.2.1 The Binary Search Tree Class ⚫ The binary search tree class will be derived from the binary tree class; hence all binary tree methods are inherited. P. 446 ⚫ The inherited methods include the constructors, the destructor, clear, empty, size, height, and the traversals preorder, inorder, and postorder. ⚫ A binary search tree also admits specialized methods called insert, remove, and tree_search. ⚫ The class Record has the behavior outlined in Chapter 7: Each Record is associated with a Key. The keys can be compared with the usual comparison operators. By casting records to their corresponding keys, the comparison operators apply to records as well as to keys. 10.2.2 Tree Search P. 447 Error_code Search_tree :: tree_search(Record &target) const; P. 447 ⚫ This method will often be called with a parameter target that contains only a key value. The method will fill target with the complete data belonging to any corresponding Record in the tree. ⚫ To search for the target, we first compare it with the entry at the root of the tree. If their keys match, then we are finished. Otherwise, we go to the left subtree or right subtree as appropriate and repeat the search in that subtree
2008级计算机 数据结构课堂教学笔记 内部资料,仅供课堂教学使用 We program this process by calling an auxiliary recursive function The process terminates when it either finds the target or hits an empty subtree The auxiliary search function returns a pointer to the node that contains the target back to the calling program. Since it is private in the class, this pointer manipulation will not compromise tree encapsulation Binary node*Search tree: search for node( Binary node sub root, const Record &target)const P.448 Recursive auxiliary function: P 448 Nonrecursive version: P.448 Public method for tree search P.449 Binary Search Trees with the Same Keys P.450 Analysis of Tree Search P. 449 Draw the comparison tree for a binary search (on an ordered list). Binary search on the list does exactly the same comparisons as tree search will do if it is applied to the comparison tree. By Section 7.4, binary search performs O(log n) comparisons for a list of length n. This perf e is excellent in comparison to other methods, since log n grows very slowly as n increases The same keys may be built into binary search trees of many different shapes If a binary search tree is nearly completely balanced (bushy), then tree search on a tree with n vertices will also doo(log n) comparisons of keys If the tree degenerates into a long chain, then tree search becomes the same as sequential search, doing O(n) comparisons on n vertices. This is the worst case for tree search o The number of vertices between the root and the target, inclusive, is the number of comparisons that must be done to find the target. The bushier the tree, the smaller the number of comparisons that will usually need to It is often not possible to predict (in advance of building it) what shape of binary search tree will occur In practice, if the keys are built into a binary search tree in random order, then it is extremely unlikely that a binary search tree degenerates badly; tree search usually performs almost as well as binary search. 10.2.3 Insertion into a Binary Search Tree Error code Search tree insert(const Record &new data P.451 Method for Insertion P. 453 The method insert can usually insert a new node into a random binary search tree with n nodes in O(log n) steps. It is possible, but extremely unlikely, that a random tree may degenerate so that insertions require as many as n steps. If the keys are inserted in sorted order into an empty tree, however, this degenerate case will occur 10.2.4 Treesort P.453-455 When a binary search tree is traversed in inorder, the keys will come out in sorted order This is the basis for a sorting method, called treesort: Take the entries to be sorted, use the method insert to build them into a binary search tree, and then use inorder traversal to put them out in order Theorem 10. 1: Treesort makes exactly the same comparisons of keys as does quicksort when the pivot for each sublist is chosen to be the first key in the sublist Corollary 10.2: In the average case, on a randomly ordered list of length n, treesort performs 2n In n +o(n) 39n Ig n+o(n) comparisons of keys First advantage of treesort over quicksort: The nodes need not all be available at the start of the process but are built into the tree one by one as they become available Second advantage: The search tree remains available for later insertions and removals. Drawback: If the keys are already sorted, then treesort will be a disaster-the search tree it builds will reduce never be used if the keys are already sorted, or are nearly so 10.2.5 Removal from a Binary Search Tree P. 455-456 Auxiliary Function to Remove One Node P. 457 Removal Method P. 458 110.3| Building a Binary Search Tree Building a Balanced Binary Search Tree P464 Problem: Start with an ordered list and build its entries into a binary search tree that is nearly balanced (bushy") If the nodes of a complete binary tree are labeled in inorder sequence, starting with 1, then each node is exactly as many levels above the leaves as the highest power of 2 that divides its label
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ We program this process by calling an auxiliary recursive function. ⚫ The process terminates when it either finds the target or hits an empty subtree. ⚫ The auxiliary search function returns a pointer to the node that contains the target back to the calling program. Since it is private in the class, this pointer manipulation will not compromise tree encapsulation. Binary_node *Search_tree :: search_for_node( Binary_node* sub_root, const Record &target) const; P. 448 Recursive auxiliary function: P. 448 Nonrecursive version: P. 448 Public method for tree search: P. 449 Binary Search Trees with the Same Keys P. 450 Analysis of Tree Search P. 449 ⚫ Draw the comparison tree for a binary search (on an ordered list). Binary search on the list does exactly the same comparisons as tree search will do if it is applied to the comparison tree. By Section 7.4, binary search performs O (log n) comparisons for a list of length n. This performance is excellent in comparison to other methods, since log n grows very slowly as n increase s. ⚫ The same keys may be built into binary search trees of many different shapes. ⚫ If a binary search tree is nearly completely balanced (“bushy”), then tree search on a tree with n vertices will also do O (log n) comparisons of keys. ⚫ If the tree degenerates into a long chain, then tree search becomes the same as sequential search, doing Θ(n) comparisons on n vertices. This is the worst case for tree search. ⚫ The number of vertices between the root and the target, inclusive, is the number of comparisons that must be done to find the target. The bushier the tree, the smaller the number of comparisons that will usually need to be done. ⚫ It is often not possible to predict (in advance of building it) what shape of binary search tree will occur. ⚫ In practice, if the keys are built into a binary search tree in random order, then it is extremely unlikely that a binary search tree degenerates badly; tree search usually performs almost as well as binary search. 10.2.3 Insertion into a Binary Search Tree Error_code Search_tree :: insert(const Record &new_data); P. 451 Method for Insertion P. 453 The method insert can usually insert a new node into a random binary search tree with n nodes in O (log n) steps. It is possible, but extremely unlikely, that a random tree may degenerate so that insertions require as many as n steps. If the keys are inserted in sorted order into an empty tree, however, this degenerate case will occur. 10.2.4 Treesort P. 453-455 ⚫ When a binary search tree is traversed in inorder, the keys will come out in sorted order. ⚫ This is the basis for a sorting method, called treesort: Take the entries to be sorted, use the method insert to build them into a binary search tree, and then use inorder traversal to put them out in order. Theorem 10.1: Treesort makes exactly the same comparisons of keys as does quicksort when the pivot for each sublist is chosen to be the first key in the sublist. Corollary 10.2: In the average case, on a randomly ordered list of length n, treesort performs 2n ln n + O (n) ≈ 1.39n lg n + O (n) comparisons of keys. ⚫ First advantage of treesort over quicksort: The nodes need not all be available at the start of the process, but are built into the tree one by one as they become available. ⚫ Second advantage: The search tree remains available for later insertions and removals. ⚫ Drawback: If the keys are already sorted, then treesort will be a disaster—the search tree it builds will reduce to a chain. Treesort should never be used if the keys are already sorted, or are nearly so. 10.2.5 Removal from a Binary Search Tree P. 455-456 Auxiliary Function to Remove One Node P. 457 Removal Method P. 458 [10.3] Building a Binary Search Tree Building a Balanced Binary Search Tree P. 464 Problem: Start with an ordered list and build its entries into a binary search tree that is nearly balanced (“bushy”). If the nodes of a complete binary tree are labeled in inorder sequence, starting with 1, then each node is exactly as many levels above the leaves as the highest power of 2 that divides its label
2008级计算机专业数据结构课堂教学笔记 内部资料,仅供课堂教学使用 P464 To establish future links, we must remember pointers to one node on each level, the last node processed on that Algorithm Developm ent o As each new node is added, it is clearly the last one received in the order, so we can place it in the list last node and set its right pointer to NULL (at least temporarily) The left pointer of the new node is NULL if it is a leaf. Otherwise it is the entry in last node one level lower an the new node o that we can treat the leaves in the same way as other nodes, we consider the leaves to be on level 1, and we set up the initial element of last node, in position 0, to have the pointer value NULL permanently ● This convention that we shall always count levels above the leaves inclusive themselves are on level 1. and so on. 10.3.2P465 While we build up a tree, we need access to the internal structure of the tree in order to create appropriate Therefore, the new function will be implemented as a(public) method for a class of search trees. We will Inks therefore create a new class called a Buildable tree that is derived from the class Search tree and possesses a new method, build tree. The specification for a buildable tree is thus: P 465 Method to build Binary Search Tree P466 10.3.3 Inserting a Node P. 467 10.3. 4 Finishing the Task P 468 P468 Tying Subtrees Together: P 469 10.3.6 Random Search Trees and Optimality Problem: If we assume that the keys have been inserted into a binary search tree in random order, then,on average, how many more comparisons are needed in a search of the resulting tree than would be needed in a completely balanced tre There is a one-to-one correspondence between binary search trees and 2-trees in which left and right are considered different from each other Assume that the n! possible orderings of keys are equally likely in building the binary search tree When there are n nodes in the tree, we denote by s(n)the number of comparisons done in the average successful search and by U(n) the number in the average unsuccessful search Recurrence relation: S(n) =1 +[U(0)+U(1)+.+U(n-D)n Performance of Random Binary Search Trees P 471-472 Relation between internal and external path S(n)=(1+l/n)U(n)-3 Solve, subtracting case I from case n: U U(n-1)+4/(n+1) Evaluate by expanding down to case 0 and the Harmonic Number: Hn=1+1/2+1/3+.+1/n In n THEOREM 10.3: The average number of nodes visited during a search of the average binary search tree with n nodes is approximately 2 In n=(2 In 2)(Ig n)1.39 Ig n, and the number of key comparisons is approximately 4 In n=(4 In 2)(lg n)= 2.77 Ig n COROLLARY 10.4: The average binary search tree requires approximately 2 In 21. 39 times as many comparisons as a completely balanced tree P472 110.4 Height Bala AVL Trees P 473 10.4.1P.473 Definition: An AVl tree is a binary search tree in which the heights of the left and right subtrees of the root differ by at most I and in which the left and right subtrees are again AVL trees. espectively, as the left subtree has height greater than, equal to, or less than that of the right subtree according, With each node of an AVl tree is associated a balance factor that is left higher History The name AVl comes from the discoverers of this method. g M. Adel, son -Vel ski i and e.m. landis The method dates from 1962 Convention in diagrams: In drawing diagrams, we shall show a left-higher node by 1, a node whose balance factor is equal by'-, and a right-higher node by " Examples of AVL trees and other binary trees P 474 C++ Conventions for Avl Trees P 474 We employ an enumerated data type to record balance factors enum Balance factor i left higher, equal height, right higher j AVL nodes are structures derived from binary search tree nodes with balance factors included: P. 475 In a Binary node, left and right have type Binary node *, so the inherited pointer members of an AVL node have this type too, not the more restricted Avl node In the insertion method, we must make sure to insert
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 10.3.1 P.464 To establish future links, we must remember pointers to one node on each level, the last node processed on that level. Algorithm Developm ent ⚫ As each new node is added, it is clearly the last one received in the order, so we can place it in the List last node and set its right pointer to NULL (at least temporarily). ⚫ The left pointer of the new node is NULL if it is a leaf. Otherwise it is the entry in last node one level lower than the new node. ⚫ So that we can treat the leaves in the same way as other nodes, we consider the leaves to be on level 1, and we set up the initial element of last node, in position 0, to have the pointer value NULL permanently. ⚫ This convention means that we shall always count levels above the leaves inclusively, so the leaves themselves are on level 1, and so on. 10.3.2 P.465 While we build up a tree, we need access to the internal structure of the tree in order to create appropriate links. Therefore, the new function will be implemented as a (public) method for a class of search trees. We will therefore create a new class called a Buildable tree that is derived from the class Search tree and possesses a new method, build tree. The specification for a buildable tree is thus: P.465 Method to Build Binary Search Tree P.466 10.3.3 Inserting a Node P.467 10.3.4 Finishing the Task P.468 Finding the root: P.468 Tying Subtrees Together: P.469 10.3.6 Random Search Trees and Optimality Problem: If we assume that the keys have been inserted into a binary search tree in random order, then, on average, how many more comparisons are needed in a search of the resulting tree than would be needed in a completely balanced tree? There is a one-to-one correspondence between binary search trees and 2-trees in which left and right are considered different from each other. ⚫ Assume that the n! possible orderings of keys are equally likely in building the binary search tree. ⚫ When there are n nodes in the tree, we denote by S(n) the number of comparisons done in the average successful search and by U (n) the number in the average unsuccessful search. ⚫ Recurrence relation: S(n) = 1 +[U (0) + U (1) + ··· + U (n − 1)]/ n . Performance of Random Binary Search Trees P.471-472 ⚫ Relation between internal and external path length: S(n) = (1+1/n) U (n) -3 ⚫ Solve, subtracting case n − 1 from case n: U (n) = U (n − 1) + 4/(n+1) ⚫ Evaluate by expanding down to case 0 and using the Harmonic Number: Hn=1+1/2+1/3+…+1/n ≈ ln n THEOREM 10.3: The average number of nodes visited during a search of the average binary search tree with n nodes is approximately 2 ln n = (2 ln 2)(lg n) ≈ 1.39 lg n, and the number of key comparisons is approximately 4 ln n = (4 ln 2)(lg n) ≈ 2.77 lg n. P.472 COROLLA RY 10.4: The average binary search tree requires approximately 2 ln 2 ≈ 1.39 times as many comparisons as a completely balanced tree. P.472 [10.4] Height Balance: AVL Trees P. 473 10.4.1 P. 473 Definition: An AVL tree is a binary search tree in which the heights of the left and right subtrees of the root differ by at most 1 and in which the left and right subtrees are again AVL trees. With each node of an AVL tree is associated a balance factor that is left higher, equal, or right higher according, respectively, as the left subtree has height greater than, equal to, or less than that of the right subtree. History: The name AVL comes from the discoverers of this method, G.M.Adel’son-V el’ski˘ı and E.M.Landis. The method dates from 1962. Convention in diagrams: In drawing diagrams, we shall show a left-higher node by ‘/,’ a node whose balance factor is equal by ‘ −,’ and a right-higher node by ‘\.’ Examples of AVL trees and other binary trees P. 474 C++ Conventions for AVL Trees P. 474 ⚫ We employ an enumerated data type to record balance factors: enum Balance_factor { left_higher, equal_height, right_higher }; ⚫ AVL nodes are structures derived from binary search tree nodes with balance factors included: P. 475 ⚫ In a Binary_node, left and right have type Binary_node *, so the inherited pointer members of an AVL_node have this type too, not the more restricted AVL_node *. In the insertion method, we must make sure to insert
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 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 have
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 ⚫ 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 * 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
2008级计算机 据结构课堂教学笔记 内部资料,仅供课堂教学使用 e Let Fh be such a tree, with left and right subtrees FI and Fr. Then one of Fi and Fr, say FI, has height h-1 and the minimum number of nodes in such a tree, and Fr has height h-2 with the minimum number of nodes These trees, as sparse as possible for AVL trees, are called Fibonacci trees Analysis of Fibonacci Trees P. 488 Pointers and Pitfalls 6 items P515-51c Errata pp. 439, 440,"Post: lines: Change " been been"to"been"(4 occurrences p. 443, E12: Last line of code for method B needs a semicolon " " at end p. 458, line 3: insert comma at end; line 4: insert comma after"returned p. 480, Fig. 10.19, left diagram: The symbol " belongs inside the circle p. 506, Fig. 10.33(a): Both arcs at the bottom of part (a)should be labelled 1(as done in part(c)
2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ Let Fh be such a tree, with left and right subtrees Fl and Fr . Then one of Fl and Fr , say Fl , has height h−1 and the minimum number of nodes in such a tree, and Fr has height h−2 with the minimum number of nodes. ⚫ These trees, as sparse as possible for AVL trees, are called Fibonacci trees. Analysis of Fibonacci Trees P. 488 Pointers and Pitfalls 6 items P.515-516 ------------------------------------------------------------------------------------------------------------------------------- Errata pp. 439, 440, "Post:" lines: Change "been been" to "been" (4 occurrences). p. 443, E12: Last line of code for method B needs a semicolon ";" at end. p. 458, line 3: insert comma at end; line 4: insert comma after "returned". p. 480, Fig. 10.19, left diagram: The symbol "\" belongs inside the circle. p. 506, Fig. 10.33(a): Both arcs at the bottom of part (a) should be labelled 1 (as done in part (c)). ------------------------------------------------------------------------------------------------------------------------
