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 insert2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 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