Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 47
Текст из файла (страница 47)
Argue thatConclude that E[M] = O(lg n/ lg lg n).Problems 11-3: Quadratic probingSuppose that we are given a key k to search for in a hash table with positions 0, 1, ..., m - 1,and suppose that we have a hash function h mapping the key space into the set {0, 1, ..., m 1}.
The search scheme is as follows.1. Compute the value i ← h(k), and set j ← 0.2. Probe in position i for the desired key k. If you find it, or if this position is empty,terminate the search.3. Set j ← (j + 1) mod m and i ← (i + j) mod m, and return to step 2.Assume that m is a power of 2.a. Show that this scheme is an instance of the general "quadratic probing" scheme byexhibiting the appropriate constants c1 and c2 for equation (11.5).b.
Prove that this algorithm examines every table position in the worst case.Problems 11-4: k-universal hashing and authenticationLet ℋ = {h} be a class of hash functions in which each h maps the universe U of keys to {0,1, ..., m - 1}. We say that ℋ is k-universal if, for every fixed sequence of k distinct keysx(1), x(2), ..., x(k) and for any h chosen at random from ℋ, the sequence h(x(1)), h(x(2)), ...,h(x(k)) is equally likely to be any of the mk sequences of length k with elements drawn from{0, 1, ..., m - 1}.a.
Show that if ℋ is 2-universal, then it is universal.b. Let U be the set of n-tuples of values drawn from Zp, and let B = Zp, where p is prime.For any n-tuple a = a0, a1, ..., an-1 of values from Zp and for any b Zp, define thehash function ha,b : U → B on an input n-tuple x = x0, x1, ..., xn-1 from U asand let ℋ = {ha,b}. Argue that ℋ is 2-universal.c. Suppose that Alice and Bob agree secretly on a hash function ha,b from a 2-universalfamily ℋ of hash functions.
Later, Alice sends a message m to Bob over the Internet,where m U . She authenticates this message to Bob by also sending anauthentication tag t = ha,b(m), and Bob checks that the pair (m, t) he receives satisfies t= ha,b(m). Suppose that an adversary intercepts (m, t) en route and tries to fool Bob byreplacing the pair with a different pair (m', t'). Argue that the probability that theadversary succeeds in fooling Bob into accepting (m', t') is at most 1/p, no matter howmuch computing power the adversary has.[1]When nj = mj = 1, we don't really need a hash function for slot j; when we Choose a hashfunction ha,b(k) = ((ak + b) mod p) mod mj for such a slot, we just use a = b = 0.Chapter notesKnuth [185] and Gonnet [126] are excellent references for the analysis of hashing algorithms.Knuth credits H.
P. Luhn (1953) for inventing hash tables, along with the chaining method forresolving collisions. At about the same time, G. M. Amdahl originated the idea of openaddressing.Carter and Wegman introduced the notion of universal classes of hash functions in 1979 [52].Fredman, Komlós, and Szemerédi [96] developed the perfect hashing scheme for static setspresented in Section 11.5. An extension of their method to dynamic sets, handling insertionsand deletions in amortized expected time O(1), has been given by Dietzfelbinger et al. [73].Chapter 12: Binary Search TreesOverviewSearch trees are data structures that support many dynamic-set operations, includingSEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, andDELETE.
Thus, a search tree can be used both as a dictionary and as a priority queue.Basic operations on a binary search tree take time proportional to the height of the tree. For acomplete binary tree with n nodes, such operations run in Θ(lg n) worst-case time. If the treeis a linear chain of n nodes, however, the same operations take Θ(n) worst-case time. We shallsee in Section 12.4 that the expected height of a randomly built binary search tree is O(lg n),so that basic dynamic-set operations on such a tree take Θ(lg n) time on average.In practice, we can't always guarantee that binary search trees are built randomly, but thereare variations of binary search trees whose worst-case performance on basic operations can beguaranteed to be good.
Chapter 13 presents one such variation, red-black trees, which haveheight O(lg n). Chapter 18 introduces B-trees, which are particularly good for maintainingdatabases on random-access, secondary (disk) storage.After presenting the basic properties of binary search trees, the following sections show howto walk a binary search tree to print its values in sorted order, how to search for a value in abinary search tree, how to find the minimum or maximum element, how to find thepredecessor or successor of an element, and how to insert into or delete from a binary searchtree.
The basic mathematical properties of trees appear in Appendix B.12.1 What is a binary search tree?A binary search tree is organized, as the name suggests, in a binary tree, as shown in Figure12.1. Such a tree can be represented by a linked data structure in which each node is an object.In addition to a key field and satellite data, each node contains fields left, right, and p thatpoint to the nodes corresponding to its left child, its right child, and its parent, respectively. Ifa child or the parent is missing, the appropriate field contains the value NIL. The root node isthe only node in the tree whose parent field is NIL.Figure 12.1: Binary search trees. For any node x, the keys in the left subtree of x are at mostkey[x], and the keys in the right subtree of x are at least key[x].
Different binary search treescan represent the same set of values. The worst-case running time for most search-treeoperations is proportional to the height of the tree. (a) A binary search tree on 6 nodes withheight 2. (b) A less efficient binary search tree with height 4 that contains the same keys.The keys in a binary search tree are always stored in such a way as to satisfy the binarysearch-tree property:•Let x be a node in a binary search tree.
If y is a node in the left subtree of x, then key[y]≤ key[x]. If y is a node in the right subtree of x, then key[x] ≤ key[y].Thus, in Figure 12.1(a), the key of the root is 5, the keys 2, 3, and 5 in its left subtree are nolarger than 5, and the keys 7 and 8 in its right subtree are no smaller than 5. The sameproperty holds for every node in the tree.
For example, the key 3 in Figure 12.1(a) is nosmaller than the key 2 in its left subtree and no larger than the key 5 in its right subtree.The binary-search-tree property allows us to print out all the keys in a binary search tree insorted order by a simple recursive algorithm, called an inorder tree walk. This algorithm is sonamed because the key of the root of a subtree is printed between the values in its left subtreeand those in its right subtree. (Similarly, a preorder tree walk prints the root before the valuesin either subtree, and a postorder tree walk prints the root after the values in its subtrees.) Touse the following procedure to print all the elements in a binary search tree T , we callINORDER-TREE-WALK (root[T]).INORDER-TREE-WALK(x)1 if x ≠ NIL2then INORDER-TREE-WALK(left[x])3print key[x]4INORDER-TREE-WALK(right[x])As an example, the inorder tree walk prints the keys in each of the two binary search treesfrom Figure 12.1 in the order 2, 3, 5, 5, 7, 8. The correctness of the algorithm follows byinduction directly from the binary-search-tree property.It takes Θ(n) time to walk an n-node binary search tree, since after the initial call, theprocedure is called recursively exactly twice for each node in the tree—once for its left childand once for its right child.
The following theorem gives a more formal proof that it takeslinear time to perform an inorder tree walk.Theorem 12.1If x is the root of an n-node subtree, then the call INORDER-TREE-WALK(x) takes Θ(n)time.Proof Let T(n) denote the time taken by INORDER-TREE-WALK when it is called on theroot of an n-node subtree.
INORDER-TREE-WALK takes a small, constant amount of timeon an empty subtree (for the test x ≠ NIL), and so T(0) = c for some positive constant c.For n > 0, suppose that INORDER-TREE-WALK is called on a node x whose left subtree hask nodes and whose right subtree has n - k - 1 nodes. The time to perform INORDER-TREEWALK(x) is T(n) = T(k) + T(n - k - 1) + d for some positive constant d that reflects the time toexecute INORDER-TREE-WALK(x), exclusive of the time spent in recursive calls.We use the substitution method to show that T(n) = Θ(n) by proving that T(n) = (c + d)n + c.For n = 0, we have (c + d) · 0 + c = c = T(0). For n > 0, we haveT(n) = T(k) + T(n - k - 1) + d= ((c + d)k + c) + ((c + d)(n - k - 1) + c) + d= (c + d)n + c - (c + d) + c + d= (c + d)n + c,which completes the proof.Exercises 12.1-1For the set of keys {1, 4, 5, 10, 16, 17, 21}, draw binary search trees of height 2, 3, 4, 5, and6.Exercises 12.1-2What is the difference between the binary-search-tree property and the min-heap property (seepage 129)? Can the min-heap property be used to print out the keys of an n-node tree in sortedorder in O(n) time? Explain how or why not.Exercises 12.1-3Give a nonrecursive algorithm that performs an inorder tree walk.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
