Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 48
Текст из файла (страница 48)
(Hint: There is an easysolution that uses a stack as an auxiliary data structure and a more complicated but elegantsolution that uses no stack but assumes that two pointers can be tested for equality.)Exercises 12.1-4Give recursive algorithms that perform preorder and postorder tree walks in Θ(n) time on atree of n nodes.Exercises 12.1-5Argue that since sorting n elements takes Ω(n lg n) time in the worst case in the comparisonmodel, any comparison-based algorithm for constructing a binary search tree from anarbitrary list of n elements takes Ω(n lg n) time in the worst case.12.2 Querying a binary search treeA common operation performed on a binary search tree is searching for a key stored in thetree.
Besides the SEARCH operation, binary search trees can support such queries asMINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR. In this section, we shallexamine these operations and show that each can be supported in time O(h) on a binary searchtree of height h.SearchingWe use the following procedure to search for a node with a given key in a binary search tree.Given a pointer to the root of the tree and a key k, TREE-SEARCH returns a pointer to a nodewith key k if one exists; otherwise, it returns NIL.TREE-SEARCH (x, k)1 if x= NIL or k = key[x]2then return x3 if k < key[x]4then return TREE-SEARCH(left[x], k)5else return TREE-SEARCH(right[x], k)The procedure begins its search at the root and traces a path downward in the tree, as shownin Figure 12.2.
For each node x it encounters, it compares the key k with key[x]. If the twokeys are equal, the search terminates. If k is smaller than key[x], the search continues in theleft subtree of x, since the binary-search-tree property implies that k could not be stored in theright subtree. Symmetrically, if k is larger than key[x], the search continues in the rightsubtree. The nodes encountered during the recursion form a path downward from the root ofthe tree, and thus the running time of TREE-SEARCH is O(h), where h is the height of thetree.Figure 12.2: Queries on a binary search tree.
To search for the key 13 in the tree, we followthe path 15 → 6 → 7 → 13 from the root. The minimum key in the tree is 2, which can befound by following left pointers from the root. The maximum key 20 is found by followingright pointers from the root. The successor of the node with key 15 is the node with key 17,since it is the minimum key in the right subtree of 15.
The node with key 13 has no rightsubtree, and thus its successor is its lowest ancestor whose left child is also an ancestor. In thiscase, the node with key 15 is its successor.The same procedure can be written iteratively by "unrolling" the recursion into a while loop.On most computers, this version is more efficient.ITERATIVE-TREE-SEARCH(x, k)1 while x ≠ NIL and k ≠ key[x]2do if k < key[x]3then x ← left[x]4else x ← right[x]5 return xMinimum and maximumAn element in a binary search tree whose key is a minimum can always be found by followingleft child pointers from the root until a NIL is encountered, as shown in Figure 12.2. Thefollowing procedure returns a pointer to the minimum element in the subtree rooted at a givennode x.TREE-MINIMUM (x)1 while left[x] ≠ NIL2do x ← left[x]3 return xThe binary-search-tree property guarantees that TREE-MINIMUM is correct.
If a node x hasno left subtree, then since every key in the right subtree of x is at least as large as key[x], theminimum key in the subtree rooted at x is key[x]. If node x has a left subtree, then since nokey in the right subtree is smaller than key[x] and every key in the left subtree is not largerthan key[x], the minimum key in the subtree rooted at x can be found in the subtree rooted atleft[x].The pseudocode for TREE-MAXIMUM is symmetric.TREE-MAXIMUM(x)1 while right[x] ≠ NIL2do x ← right[x]3 return xBoth of these procedures run in O(h) time on a tree of height h since, as in TREE-SEARCH,the sequence of nodes encountered forms a path downward from the root.Successor and predecessorGiven a node in a binary search tree, it is sometimes important to be able to find its successorin the sorted order determined by an inorder tree walk. If all keys are distinct, the successor ofa node x is the node with the smallest key greater than key[x].
The structure of a binary searchtree allows us to determine the successor of a node without ever comparing keys. Thefollowing procedure returns the successor of a node x in a binary search tree if it exists, andNIL if x has the largest key in the tree.TREE-SUCCESSOR(x)1 if right[x] ≠ NIL2then return TREE-MINIMUM (right[x])3 y ← p[x]4 while y ≠ NIL and x = right[y]5do x ← y6y ← p[y]7 return yThe code for TREE-SUCCESSOR is broken into two cases. If the right subtree of node x isnonempty, then the successor of x is just the leftmost node in the right subtree, which is foundin line 2 by calling TREE-MINIMUM(right[x]). For example, the successor of the node withkey 15 in Figure 12.2 is the node with key 17.On the other hand, as Exercise 12.2-6 asks you to show, if the right subtree of node x is emptyand x has a successor y, then y is the lowest ancestor of x whose left child is also an ancestorof x.
In Figure 12.2, the successor of the node with key 13 is the node with key 15. To find y,we simply go up the tree from x until we encounter a node that is the left child of its parent;this is accomplished by lines 3–7 of TREE-SUCCESSOR.The running time of TREE-SUCCESSOR on a tree of height h is O(h), since we either followa path up the tree or follow a path down the tree. The procedure TREE-PREDECESSOR,which is symmetric to TREE-SUCCESSOR, also runs in time O(h).Even if keys are not distinct, we define the successor and predecessor of any node x as thenode returned by calls made to TREE-SUCCESSOR(x) and TREE-PREDECESSOR(x),respectively.In summary, we have proved the following theorem.Theorem 12.2The dynamic-set operations SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, andPREDECESSOR can be made to run in O(h) time on a binary search tree of height h.Exercises 12.2-1Suppose that we have numbers between 1 and 1000 in a binary search tree and want to searchfor the number 363.
Which of the following sequences could not be the sequence of nodesexamined?a.b.c.d.e.2, 252, 401, 398, 330, 344, 397, 363.924, 220, 911, 244, 898, 258, 362, 363.925, 202, 911, 240, 912, 245, 363.2, 399, 387, 219, 266, 382, 381, 278, 363.935, 278, 347, 621, 299, 392, 358, 363.Exercises 12.2-2Write recursive versions of the TREE-MINIMUM and TREE-MAXIMUM procedures.Exercises 12.2-3Write the TREE-PREDECESSOR procedure.Exercises 12.2-4Professor Bunyan thinks he has discovered a remarkable property of binary search trees.Suppose that the search for key k in a binary search tree ends up in a leaf. Consider three sets:A, the keys to the left of the search path; B, the keys on the search path; and C, the keys to theright of the search path.
Professor Bunyan claims that any three keys a A, b B, and c Cmust satisfy a ≤ b ≤ c. Give a smallest possible counterexample to the professor's claim.Exercises 12.2-5Show that if a node in a binary search tree has two children, then its successor has no leftchild and its predecessor has no right child.Exercises 12.2-6Consider a binary search tree T whose keys are distinct. Show that if the right subtree of anode x in T is empty and x has a successor y, then y is the lowest ancestor of x whose left childis also an ancestor of x. (Recall that every node is its own ancestor.)Exercises 12.2-7An inorder tree walk of an n-node binary search tree can be implemented by finding theminimum element in the tree with TREE-MINIMUM and then making n-1 calls to TREESUCCESSOR.
Prove that this algorithm runs in Θ(n) time.Exercises 12.2-8Prove that no matter what node we start at in a height-h binary search tree, k successive callsto TREE-SUCCESSOR take O(k + h) time.Exercises 12.2-9Let T be a binary search tree whose keys are distinct, let x be a leaf node, and let y be itsparent. Show that key[y] is either the smallest key in T larger than key[x] or the largest key inT smaller than key[x].12.3 Insertion and deletionThe operations of insertion and deletion cause the dynamic set represented by a binary searchtree to change.
The data structure must be modified to reflect this change, but in such a waythat the binary-search-tree property continues to hold. As we shall see, modifying the tree toinsert a new element is relatively straight-forward, but handling deletion is somewhat moreintricate.InsertionTo insert a new value v into a binary search tree T , we use the procedure TREE-INSERT.The procedure is passed a node z for which key[z] = v, left[z] = NIL, and right[z] = NIL. Itmodifies T and some of the fields of z in such a way that z is inserted into an appropriateposition in the tree.TREE-INSERT(T, z)1 y ← NIL2 x ← root[T]3 while x ≠ NIL4do y ← x5if key[z] < key[x]678910111213then x ← left[x]else x ← right[x]p[z] ← yif y = NILthen root[T] ← zelse if key[z] < key[y]then left[y] ← zelse right[y] ← z⊹ Tree T was emptyFigure 12.3 shows how TREE-INSERT works.
Just like the procedures TREE-SEARCH andITERATIVE-TREE-SEARCH, TREE-INSERT begins at the root of the tree and traces a pathdownward. The pointer x traces the path, and the pointer y is maintained as the parent of x.After initialization, the while loop in lines 3–7 causes these two pointers to move down thetree, going left or right depending on the comparison of key[z] with key[x], until x is set toNIL. This NIL occupies the position where we wish to place the input item z. Lines 8–13 setthe pointers that cause z to be inserted.Figure 12.3: Inserting an item with key 13 into a binary search tree. Lightly shaded nodesindicate the path from the root down to the position where the item is inserted. The dashedline indicates the link in the tree that is added to insert the item.Like the other primitive operations on search trees, the procedure TREE-INSERT runs inO(h) time on a tree of height h.DeletionThe procedure for deleting a given node z from a binary search tree takes as an argument apointer to z.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
