📄 chap14.htm
字号:
<a name="07f1_14e4">14.4-1<a name="07f1_14e4"><P>Argue that the root of the red-black tree is always black after RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> executes. <P><a name="07f1_14e5">14.4-2<a name="07f1_14e5"><P>In Exercise 14.3-3, you found the red-black tree that results from successively inserting the keys 41, 38, 31, 12,19, 8 into an initially empty tree. Now show the red-black trees that result from the successive deletion of the keys in the order 8, 12, 19, 31, 38, 41.<P><a name="07f1_14e6">14.4-3<a name="07f1_14e6"><P><a name="07f1_14e1">In which lines of the code for RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>-<FONT FACE="Courier New" SIZE=2>FIXUP</FONT> might we examine or modify the sentinel <I>nil</I>[<I>T</I>]?<P><a name="07f1_14e7">14.4-4<a name="07f1_14e7"><P><a name="07f1_14e2">Simplify the code for <FONT FACE="Courier New" SIZE=2>LEFT</FONT>-<FONT FACE="Courier New" SIZE=2>ROTATE</FONT> by using a sentinel for <FONT FACE="Courier New" SIZE=2>NIL</FONT> and another sentinel to hold the pointer to the root.<P><a name="07f1_14e8">14.4-5<a name="07f1_14e8"><P>In each of the cases of Figure 14.7, give the count of black nodes from the root of the subtree shown to each of the subtrees <img src="../images/alpha12.gif">,<I><img src="../images/beta14.gif">,</I> . . ., <img src="../images/zeta12.gif"><I>,</I> and verify that each count remains the same after the transformation. When a node has a color <I>c</I> or <I>c</I>', use the notation count(<I>c</I>) or count(<I>c</I>') symbolically in your count.<P><a name="07f1_14e9">14.4-6<a name="07f1_14e9"><P>Suppose that a node <I>x</I> is inserted into a red-black tree with RB-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> and then immediately deleted with RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT>. Is the resulting red-black tree the same as the initial red-black tree? Justify your answer.<P><P><P><h1><a name="07f2_14ea">Problems<a name="07f2_14ea"></h1><P><a name="07f2_14eb">14-1 Persistent dynamic sets<a name="07f2_14eb"><P><a name="07f2_14e3"><a name="07f2_14e4"><a name="07f2_14e5">During the course of an algorithm, we sometimes find that we need to maintain past versions of a dynamic set as it is updated. Such a set is called <I><B>persistent.</I></B> One way to implement a persistent set is to copy the entire set whenever it is modified, but this approach can slow down a program and also consume much space. Sometimes, we can do much better.<P>Consider a persistent set <I>S</I> with the operations <FONT FACE="Courier New" SIZE=2>INSERT</FONT>, <FONT FACE="Courier New" SIZE=2>DELETE</FONT>, and <FONT FACE="Courier New" SIZE=2>SEARCH</FONT>, which we implement using binary search trees as shown in Figure 14.8(a). We maintain a separate root for every version of the set. In order to insert the key 5 into the set, we create a new node with key 5. This node becomes the left child of a new node with key 7, since we cannot modify the existing node with key 7. Similarly, the new node with key 7 becomes the left child of a new node with key 8 whose right child is the existing node with key 10. The new node with key 8 becomes, in turn, the right child of a new root <I>r</I>' with key 4 whose left child is the existing node with key 3. We thus copy only part of the tree and share some of the nodes with the original tree, as shown in Figure 14.8(b).<P><I><B>a. </I></B>For a general persistent binary search tree, identify the nodes that need to be changed to insert a key <I>k</I> or delete a node <I>y</I>.<P><a name="07f2_14e6"><I><B>b. </I></B>Write a procedure <FONT FACE="Courier New" SIZE=2>PERSISTENT</FONT>-<FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> that, given a persistent tree <I>T</I> and a key <I>k</I> to insert, returns a new persistent tree <I>T'</I> that is the result of inserting <I>k</I> into <I>T</I>. Assume that each tree node has the fields <I>key</I>, <I>left</I>, and <I>right</I> but no parent field. (See also Exercise 14.3-6.)<P><I><B>c. </I></B>If the height of the persistent binary search tree <I>T</I> is <I>h</I>, what are the time and space requirements of your implementation of <FONT FACE="Courier New" SIZE=2>PERSISTENT</FONT>-<FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT>? (The space requirement is proportional to the number of new nodes allocated.)<P><I><B>d.</I></B> Suppose that we had included the parent field in each node. In this case, <FONT FACE="Courier New" SIZE=2>PERSISTENT</FONT>-<FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> would need to perform additional copying. Prove that P<FONT FACE="Courier New" SIZE=2>ERSISTENT-</FONT>T<FONT FACE="Courier New" SIZE=2>REE-</FONT><FONT FACE="Courier New" SIZE=2>INSERT</FONT> would then require <img src="../images/omega12.gif">(<I>n</I>) time and space, where <I>n</I> is the number of nodes in the tree.<P><I><B>e. </I></B>Show how to use red-black trees to guarantee that the worst-case running time and space is <I>O</I>(lg <I>n</I>) per insertion or deletion.<P><a name="07f2_14ec">14-2 Join operation on red-black trees<a name="07f2_14ec"><P><a name="07f2_14e7"><a name="07f2_14e8"><a name="07f2_14e9">The <I><B>join </I></B>operation takes two dynamic sets <I>S</I><SUB>1</SUB> and <I>S</I><SUB>2</SUB> and an element <I>x</I> such that for any <I>x</I><SUB>1</SUB> <img src="../images/memof12.gif"> <I>S</I><SUB>1</SUB> and <I>x</I><SUB>2 </SUB><img src="../images/memof12.gif"> <I>S</I><SUB>2</SUB>, we have <I>key</I>[<I>x</I><SUB>1</SUB>] <img src="../images/lteq12.gif"> <I>key</I>[<I>x</I>]<I> </I><img src="../images/lteq12.gif"> <I>key</I>[<I>x</I><SUB>2</SUB>]. It returns a set <I>S</I> = <I>S</I><SUB>1</SUB> <img src="../images/wideu.gif"> {<I>x</I>} <img src="../images/wideu.gif"> <I>S</I><SUB>2</SUB>. In this problem, we investigate how to implement the join operation on red-black trees.<P><img src="279_a.gif"><P><h4><a name="07f2_14ed">Figure 14.8 (a) A binary search tree with keys 2, 3, 4, 7, 8, 10. (b) The persistent binary search tree that results from the insertion of key 5. The most recent version of the set consists of the nodes reachable from the root r', and the previous version consists of the nodes reachable from r. Heavily shaded nodes are added when key 5 is inserted.<a name="07f2_14ed"></sub></sup></h4><P><I><B>a.</I></B> Given a red-black tree <I>T</I>, we store its black-height as the field <I>bh</I>[<I>T</I>]. Argue that this field can be maintained by RB-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> and RB-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> without requiring extra storage in the tree and without increasing the asymptotic running times. Show that while descending through <I>T</I>, we can determine the black-height of each node we visit in <I>O</I>(1) time per node visited.<P>We wish to implement the operation RB-<FONT FACE="Courier New" SIZE=2>JOIN</FONT>(<I>T</I><SUB>1</SUB>,<I>x</I>,<I>T</I><SUB>2</SUB>), which destroys <I>T</I><SUB>1</SUB> and <I>T</I><SUB>2</SUB> and returns a red-black tree <I>T</I> = <I>T</I><SUB>1</SUB> <img src="../images/wideu.gif"> {<I>x</I>} <img src="../images/wideu.gif"> <I>T</I><SUB>2</SUB>. Let <I>n</I> be the total number of nodes in <I>T</I><SUB>1</SUB> and <I>T</I><SUB>2</SUB>.<P><I><B>b.</I></B> Assume without loss of generality that <I>bh</I>[<I>T</I><SUB>1</SUB>] <img src="../images/gteq.gif"> <I>bh</I>[<I>T</I><SUB>2</SUB>]. Describe an <I>O</I>(lg <I>n</I>)-time algorithm that finds a black node <I>y</I> in <I>T</I><SUB>1</SUB> with the largest key from among those nodes whose black-height is <I>bh</I>[<I>T</I><SUB>2</SUB>].<P><I><B>c. </I></B>Let <I>T<SUB>y</I></SUB> be the subtree rooted at <I>y</I>. Describe how <I>T<SUB>y</I></SUB> can be replaced by <I>T<SUB>y</I></SUB> <img src="../images/wideu.gif"> {<I>x</I>}<img src="../images/wideu.gif"> <I>T</I><SUB>2</SUB> in <I>O</I>(1) time without destroying the binary-search-tree property.<P><I><B>d. </I></B>What color should we make <I>x</I> so that red-black properties 1, 2, and 4 are maintained? Describe how property 3 can be enforced in <I>O</I>(lg <I>n</I>) time.<P><I><B>e.</I></B> Argue that the running time of RB-<FONT FACE="Courier New" SIZE=2>JOIN</FONT> is <I>O</I>(lg <I>n</I>).<P><P><h1>Chapter notes</h1><P><a name="07f3_14ea"><a name="07f3_14eb"><a name="07f3_14ec"><a name="07f3_14ed"><a name="07f3_14ee">The idea of balancing a search tree is due to <img src="280_a.gif"> and Landis [2], who introduced a class of balanced search trees called "AVL trees" in 1962. Balance is maintained in AVL trees by rotations, but as many as <img src="../images/bound.gif">(lg <I>n</I>) rotations may be required after an insertion to maintain balance in an <I>n</I>-node tree. Another class of search trees, called "2-3 trees," was introduced by J. E. Hopcroft (unpublished) in 1970. Balance is maintained in a 2-3 tree by manipulating the degrees of nodes in the tree. A generalization of 2-3 trees introduced by Bayer and McCreight [18], called B-trees, is the topic of Chapter 19.<P>Red-black trees were invented by Bayer [17] under the name "symmetric binary B-trees." Guibas and Sedgewick [93] studied their properties at length and introduced the red/black color convention.<P><a name="07f3_14ef"><a name="07f3_14f0"><a name="07f3_14f1"><a name="07f3_14f2"><a name="07f3_14f3">Of the many other variations on balanced binary trees, perhaps the most intriguing are the "splay trees" introduced by Sleator and Tarjan [177], which are "self-adjusting." (A good description of splay trees is given by Tarjan [188].) Splay trees maintain balance without any explicit balance condition such as color. Instead, "splay operations" (which involve rotations) are performed within the tree every time an access is made. The amortized cost (see Chapter 18) of each operation on an <I>n</I>-node tree is <I>O</I>(lg <I>n</I>). <P><P><P><P><center>Go to <a href="chap15.htm">Chapter 15</A> Back to <a href="toc.htm">Table of Contents</A></P></center></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -