Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 50
Текст из файла (страница 50)
there exists an integer j, where 0 ≤ j ≤ min(p, q), such that ai = bi for all i = 0, 1, ..., j 1 and aj < bj, or2. p < q and ai = bi for all i = 0, 1, ..., p.For example, if a and b are bit strings, then 10100 < 10110 by rule 1 (letting j = 3) and 10100< 101000 by rule 2. This is similar to the ordering used in English-language dictionaries.The radix tree data structure shown in Figure 12.5 stores the bit strings 1011, 10, 011, 100,and 0.
When searching for a key a = a0a1...ap, we go left at a node of depth i if ai = 0 and rightif ai = 1. Let S be a set of distinct binary strings whose lengths sum to n. Show how to use aradix tree to sort S lexicographically in Θ(n) time. For the example in Figure 12.5, the outputof the sort should be the sequence 0, 011, 10, 100, 1011.Figure 12.5: A radix tree storing the bit strings 1011, 10, 011, 100, and 0. Each node's key canbe determined by traversing the path from the root to that node. There is no need, therefore, tostore the keys in the nodes; the keys are shown here for illustrative purposes only. Nodes areheavily shaded if the keys corresponding to them are not in the tree; such nodes are presentonly to establish a path to other nodes.Problems 12-3: Average node depth in a randomly built binary search treeIn this problem, we prove that the average depth of a node in a randomly built binary searchtree with n nodes is O(lg n).
Although this result is weaker than that of Theorem 12.4, thetechnique we shall use reveals a surprising similarity between the building of a binary searchtree and the running of RANDOMIZED-QUICKSORT from Section 7.3.We define the total path length P(T) of a binary tree T as the sum, over all nodes x in T , ofthe depth of node x, which we denote by d(x, T).a. Argue that the average depth of a node in T isThus, we wish to show that the expected value of P(T) is O(n lg n).b.
Let TL and TR denote the left and right subtrees of tree T, respectively. Argue that if Thas n nodes, thenP(T) = P(TL) + P(TR) + n - 1.c. Let P(n) denote the average total path length of a randomly built binary search treewith n nodes. Show thatd. Show that P(n) can be rewritten ase. Recalling the alternative analysis of the randomized version of quicksort given inProblem 7-2, conclude that P(n) = O(n lg n).At each recursive invocation of quicksort, we choose a random pivot element to partition theset of elements being sorted. Each node of a binary search tree partitions the set of elementsthat fall into the subtree rooted at that node.f.
Describe an implementation of quicksort in which the comparisons to sort a set ofelements are exactly the same as the comparisons to insert the elements into a binarysearch tree. (The order in which comparisons are made may differ, but the samecomparisons must be made.)Problems 12-4: Number of different binary treesLet bn denote the number of different binary trees with n nodes.
In this problem, you will finda formula for bn, as well as an asymptotic estimate.a. Show that b0 = 1 and that, for n ≥ 1,b. Referring to Problem 4-5 for the definition of a generating function, let B(x) be thegenerating functionShow that B(x) = xB(x)2 + 1, and hence one way to express B(x) in closed form isThe Taylor expansion of f(x) around the point x = a is given bywhere f(k)(x) is the kth derivative of f evaluated at x.c. Show that(the nth Catalan number) by using the Taylor expansion ofaround x = 0.
(Ifyou wish, instead of using the Taylor expansion, you may use the generalization of thebinomial expansion (C.4) to nonintegral exponents n, where for any real number n andfor any integer k, we interpret to be n(n - 1) (n - k + 1)/k! if k ≥ 0, and 0 otherwise.)d. Show thatChapter notesKnuth [185] contains a good discussion of simple binary search trees as well as manyvariations.
Binary search trees seem to have been independently discovered by a number ofpeople in the late 1950's. Radix trees are often called tries, which comes from the middleletters in the word retrieval. They are also discussed by Knuth [185].Section 15.5 will show how to construct an optimal binary search tree when searchfrequencies are known prior to constructing the tree. That is, given the frequencies ofsearching for each key and the frequencies of searching for values that fall between keys inthe tree, we construct a binary search tree for which a set of searches that follows thesefrequencies examines the minimum number of nodes.The proof in Section 12.4 that bounds the expected height of a randomly built binary searchtree is due to Aslam [23].
Mart nez and Roura [211] give randomized algorithms for insertioninto and deletion from binary search trees in which the result of either operation is a randombinary search tree. Their definition of a random binary search tree differs slightly from that ofa randomly built binary search tree in this chapter, however.Chapter 13: Red-Black TreesChapter 12 showed that a binary search tree of height h can implement any of the basicdynamic-set operations—such as SEARCH, PREDECESSOR, SUCCESSOR, MINIMUM,MAXIMUM, INSERT, and DELETE—in O(h) time. Thus, the set operations are fast if theheight of the search tree is small; but if its height is large, their performance may be no betterthan with a linked list.
Red-black trees are one of many search-tree schemes that are"balanced" in order to guarantee that basic dynamic-set operations take O(lg n) time in theworst case.13.1 Properties of red-black treesA red-black tree is a binary search tree with one extra bit of storage per node: its color, whichcan be either RED or BLACK. By constraining the way nodes can be colored on any pathfrom the root to a leaf, red-black trees ensure that no such path is more than twice as long asany other, so that the tree is approximately balanced.Each node of the tree now contains the fields color, key, left, right, and p. If a child or theparent of a node does not exist, the corresponding pointer field of the node contains the valueNIL.
We shall regard these NIL's as being pointers to external nodes (leaves) of the binarysearch tree and the normal, key-bearing nodes as being internal nodes of the tree.A binary search tree is a red-black tree if it satisfies the following red-black properties:1.2.3.4.5.Every node is either red or black.The root is black.Every leaf (NIL) is black.If a node is red, then both its children are black.For each node, all paths from the node to descendant leaves contain the same numberof black nodes.Figure 13.1(a) shows an example of a red-black tree.Figure 13.1: A red-black tree with black nodes darkened and red nodes shaded.
Every node ina red-black tree is either red or black, the children of a red node are both black, and everysimple path from a node to a descendant leaf contains the same number of black nodes. (a)Every leaf, shown as a NIL, is black. Each non-NIL node is marked with its black-height;NIL's have black-height 0.
(b) The same red-black tree but with each NIL replaced by thesingle sentinel nil[T], which is always black, and with black-heights omitted. The root's parentis also the sentinel. (c) The same red-black tree but with leaves and the root's parent omittedentirely. We shall use this drawing style in the remainder of this chapter.As a matter of convenience in dealing with boundary conditions in red-black tree code, weuse a single sentinel to represent NIL (see page 206). For a red-black tree T, the sentinel nil[T]is an object with the same fields as an ordinary node in the tree. Its color field is BLACK, andits other fields—p, left, right, and key—can be set to arbitrary values.
As Figure 13.1(b)shows, all pointers to NIL are replaced by pointers to the sentinel nil[T].We use the sentinel so that we can treat a NIL child of a node x as an ordinary node whoseparent is x. Although we instead could add a distinct sentinel node for each NIL in the tree, sothat the parent of each NIL is well defined, that approach would waste space. Instead, we usethe one sentinel nil[T] to represent all the NIL's—all leaves and the root's parent. The valuesof the fields p, left, right, and key of the sentinel are immaterial, although we may set themduring the course of a procedure for our convenience.We generally confine our interest to the internal nodes of a red-black tree, since they hold thekey values. In the remainder of this chapter, we omit the leaves when we draw red-black trees,as shown in Figure 13.1(c).We call the number of black nodes on any path from, but not including, a node x down to aleaf the black-height of the node, denoted bh(x).
By property 5, the notion of black-height iswell defined, since all descending paths from the node have the same number of black nodes.We define the black-height of a red-black tree to be the black-height of its root.The following lemma shows why red-black trees make good search trees.Lemma 13.1A red-black tree with n internal nodes has height at most 2 lg(n + 1).Proof We start by showing that the subtree rooted at any node x contains at least 2bh(x) - 1internal nodes. We prove this claim by induction on the height of x.
If the height of x is 0, thenx must be a leaf (nil[T]), and the subtree rooted at x indeed contains at least 2bh(x) - 1 = 20 - 1 =0 internal nodes. For the inductive step, consider a node x that has positive height and is aninternal node with two children. Each child has a black-height of either bh(x) or bh(x) - 1,depending on whether its color is red or black, respectively. Since the height of a child of x isless than the height of x itself, we can apply the inductive hypothesis to conclude that eachchild has at least 2bh(x)-1 -1 internal nodes. Thus, the subtree rooted at x contains at least (2bh(x)1- 1) + (2bh(x)-1 - 1) + 1 = 2bh(x) - 1 internal nodes, which proves the claim.To complete the proof of the lemma, let h be the height of the tree.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
