Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 54
Текст из файла (страница 54)
The new sibling w of x isnow a black node with a red right child, and thus we have transformed case 3 into case 4.Case 4: x's sibling w is black, and w's right child is redCase 4 (lines 17–21 and Figure 13.7(d)) occurs when node x's sibling w is black and w's rightchild is red. By making some color changes and performing a left rotation on p[x], we canremove the extra black on x, making it singly black, without violating any of the red-blackproperties.
Setting x to be the root causes the while loop to terminate when it tests the loopcondition.AnalysisWhat is the running time of RB-DELETE? Since the height of a red-black tree of n nodes isO(lg n), the total cost of the procedure without the call to RB-DELETE-FIXUP takes O(lg n)time. Within RB-DELETE-FIXUP, cases 1, 3, and 4 each terminate after performing aconstant number of color changes and at most three rotations. Case 2 is the only case in whichthe while loop can be repeated, and then the pointer x moves up the tree at most O(lg n) timesand no rotations are performed. Thus, the procedure RB-DELETE-FIXUP takes O(lg n) timeand performs at most three rotations, and the overall time for RB-DELETE is therefore alsoO(lg n).Exercises 13.4-1Argue that after executing RB-DELETE-FIXUP, the root of the tree must be black.Exercises 13.4-2Argue that if in RB-DELETE both x and p[y] are red, then property 4 is restored by the callRB-DELETE-FIXUP(T, x).Exercises 13.4-3In Exercise 13.3-2, you found the red-black tree that results from successively inserting thekeys 41, 38, 31, 12, 19, 8 into an initially empty tree.
Now show the red-black trees that resultfrom the successive deletion of the keys in the order 8, 12, 19, 31, 38, 41.Exercises 13.4-4In which lines of the code for RB-DELETE-FIXUP might we examine or modify the sentinelnil[T]?Exercises 13.4-5In each of the cases of Figure 13.7, give the count of black nodes from the root of the subtreeshown to each of the subtrees α, β, ..., ζ, and verify that each count remains the same after thetransformation. When a node has a color attribute c or c′, use the notation count(c) orcount(c′) symbolically in your count.Exercises 13.4-6Professors Skelton and Baron are concerned that at the start of case 1 of RB-DELETEFIXUP, the node p[x] might not be black.
If the professors are correct, then lines 5–6 arewrong. Show that p[x] must be black at the start of case 1, so that the professors have nothingto worry about.Exercises 13.4-7Suppose that a node x is inserted into a red-black tree with RB-INSERT and then immediatelydeleted with RB-DELETE. Is the resulting red-black tree the same as the initial red-blacktree? Justify your answer.Problems 13-1: Persistent dynamic setsDuring the course of an algorithm, we sometimes find that we need to maintain past versionsof a dynamic set as it is updated. Such a set is called persistent. One way to implement apersistent set is to copy the entire set whenever it is modified, but this approach can slowdown a program and also consume much space.
Sometimes, we can do much better.Consider a persistent set S with the operations INSERT, DELETE, and SEARCH, which weimplement using binary search trees as shown in Figure 13.8(a). We maintain a separate rootfor every version of the set. In order to insert the key 5 into the set, we create a new node withkey 5. This node becomes the left child of a new node with key 7, since we cannot modify theexisting node with key 7. Similarly, the new node with key 7 becomes the left child of a newnode with key 8 whose right child is the existing node with key 10. The new node with key 8becomes, in turn, the right child of a new root r′ with key 4 whose left child is the existingnode with key 3. We thus copy only part of the tree and share some of the nodes with theoriginal tree, as shown in Figure 13.8(b).Figure 13.8: (a) A binary search tree with keys 2, 3, 4, 7, 8, 10.
(b) The persistent binarysearch tree that results from the insertion of key 5. The most recent version of the set consistsof the nodes reachable from the root r′, and the previous version consists of the nodesreachable from r. Heavily shaded nodes are added when key 5 is inserted.Assume that each tree node has the fields key, left, and right but no parent field. (See alsoExercise 13.3-6.)a. For a general persistent binary search tree, identify the nodes that need to be changedto insert a key k or delete a node y.b. Write a procedure PERSISTENT-TREE-INSERT that, given a persistent tree T and akey k to insert, returns a new persistent tree T′ that is the result of inserting k into T.c. If the height of the persistent binary search tree T is h, what are the time and spacerequirements of your implementation of PERSISTENT-TREE-INSERT? (The spacerequirement is proportional to the number of new nodes allocated.)d.
Suppose that we had included the parent field in each node. In this case,PERSISTENT-TREE-INSERT would need to perform additional copying. Prove thatPERSISTENT-TREE-INSERT would then require Ω(n) time and space, where n is thenumber of nodes in the tree.e. Show how to use red-black trees to guarantee that the worst-case running time andspace are O(lg n) per insertion or deletion.Problems 13-2: Join operation on red-black treesThe join operation takes two dynamic sets S1 and S2 and an element x such that for any x1S1 and x2 S2, we have key[x1] ≤ key[x] ≤ key[x2].
It returns a set S = S1 {x} S2. In thisproblem, we investigate how to implement the join operation on red-black trees.a. Given a red-black tree T, we store its black-height as the field bh[T]. Argue that thisfield can be maintained by RB-INSERT and RB-DELETE without requiring extrastorage in the nodes of the tree and without increasing the asymptotic running times.Show that while descending through T, we can determine the black-height of eachnode we visit in O(1) time per node visited.We wish to implement the operation RB-JOIN(T1, x, T2), which destroys T1 and T2 and returnsa red-black tree T = T1 {x} T2.
Let n be the total number of nodes in T1 and T2.b. Assume that bh[T1] ≥ bh[T2]. Describe an O(lg n)-time algorithm that finds a blacknode y in T1 with the largest key from among those nodes whose black-height isbh[T2].c. Let Ty be the subtree rooted at y. Describe how Ty {x} T2 can replace Ty in O(1)time without destroying the binary-search-tree property.d. What color should we make x so that red-black properties 1, 3, and 5 are maintained?Describe how properties 2 and 4 can be enforced in O(lg n) time.e. Argue that no generality is lost by making the assumption in part (b).
Describe thesymmetric situation that arises when bh[T1] = bh[T2].f. Argue that the running time of RB-JOIN is O(lg n).Problems 13-3: AVL treesAn AVL tree is a binary search tree that is height balanced: for each node x, the heights of theleft and right subtrees of x differ by at most 1. To implement an AVL tree, we maintain anextra field in each node: h[x] is the height of node x. As for any other binary search tree T, weassume that root[T] points to the root node.a. Prove that an AVL tree with n nodes has height O(lg n).
(Hint: Prove that in an AVLtree of height h, there are at least Fh nodes, where Fh is the hth Fibonacci number.)b. To insert into an AVL tree, a node is first placed in the appropriate place in binarysearch tree order. After this insertion, the tree may no longer be height balanced.Specifically, the heights of the left and right children of some node may differ by 2.Describe a procedure BALANCE(x), which takes a subtree rooted at x whose left andright children are height balanced and have heights that differ by at most 2, i.e.,|h[right[x]] - h[left[x]]| ≤ 2, and alters the subtree rooted at x to be height balanced.(Hint: Use rotations.)c.
Using part (b), describe a recursive procedure AVL-INSERT(x, z), which takes a nodex within an AVL tree and a newly created node z (whose key has already been filledin), and adds z to the subtree rooted at x, maintaining the property that x is the root ofan AVL tree. As in TREE-INSERT from Section 12.3, assume that key[z] has alreadybeen filled in and that left[z] = NIL and right[z] = NIL; also assume that h[z] = 0.Thus, to insert the node z into the AVL tree T, we call AVL-INSERT(root[T], z).d. Give an example of an n-node AVL tree in which an AVL-INSERT operation causesΩ(lg n) rotations to be performed.Problems 13-4: TreapsIf we insert a set of n items into a binary search tree, the resulting tree may be horriblyunbalanced, leading to long search times.
As we saw in Section 12.4, however, randomly builtbinary search trees tend to be balanced. Therefore, a strategy that, on average, builds abalanced tree for a fixed set of items is to randomly permute the items and then insert them inthat order into the tree.What if we do not have all the items at once? If we receive the items one at a time, can westill randomly build a binary search tree out of them?We will examine a data structure that answers this question in the affirmative. A treap is abinary search tree with a modified way of ordering the nodes. Figure 13.9 shows an example.As usual, each node x in the tree has a key value key[x].
In addition, we assign priority[x],which is a random number chosen independently for each node. We assume that all prioritiesare distinct and also that all keys are distinct. The nodes of the treap are ordered so that thekeys obey the binary-search-tree property and the priorities obey the min-heap order property:•••If v is a left child of u, then key[v] < key[u].If v is a right child of u, then key[v] > key[u].If v is a child of u, then priority[v] > priority[u].Figure 13.9: A treap.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
