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<Record >*Search tree<Record >: search for node( Binary node<Record > 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<Record > 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 label2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 ⚫ 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<Record > *Search_tree<Record > :: search_for_node( Binary_node<Record >* 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<Record > :: 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