📄 chap14.htm
字号:
<HTML><HEAD><TITLE>Intro to Algorithms: CHAPTER 14: RED-BLACK TREES</TITLE></HEAD><BODY BGCOLOR="#FFFFFF"><a href="chap15.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A><a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A><a href="chap13.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A><h1><a name="07e8_14bf">CHAPTER 14: RED-BLACK TREES<a name="07e8_14bf"></h1><P><a name="07e8_14be">Chapter 13 showed that a binary search tree of height <I>h</I> can implement any of the basic dynamic-set operations--such as <FONT FACE="Courier New" SIZE=2>SEARCH</FONT>, <FONT FACE="Courier New" SIZE=2>PREDECESSOR</FONT>, <FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT>, <FONT FACE="Courier New" SIZE=2>MINIMUM</FONT>, <FONT FACE="Courier New" SIZE=2>MAXIMUM</FONT>, <FONT FACE="Courier New" SIZE=2>INSERT</FONT>, and <FONT FACE="Courier New" SIZE=2>DELETE</FONT>--in <I>O</I>(<I>h</I>) time. Thus, the set operations are fast if the height of the search tree is small; but if its height is large, their performance may be no better than with a linked list. Red-black trees are one of many search-tree schemes that are "balance" in order to guarantee that basic dynamic-set operations take <I>O</I>(lg <I>n</I>) time in the worst case.<P><h1><a name="07ea_14d2">14.1 Properties of red-black trees<a name="07ea_14d2"></h1><P><a name="07ea_14bf"><a name="07ea_14c0"><a name="07ea_14c1"><a name="07ea_14c2"><a name="07ea_14c3">A <I><B>red-black tree</I></B> is a binary search tree with one extra bit of storage per node: its <I><B>color</I></B>, which can be either <FONT FACE="Courier New" SIZE=2>RED</FONT> or <FONT FACE="Courier New" SIZE=2>BLACK</FONT>. By constraining the way nodes can be colored on any path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately <I><B>balanced.</I></B><P>Each node of the tree now contains the fields <I>color, key, left, right</I>, and <I>p.</I> If a child or the parent of a node does not exist, the corresponding pointer field of the node contains the value <FONT FACE="Courier New" SIZE=2>NIL</FONT>. We shall regard these <FONT FACE="Courier New" SIZE=2>NIL'S</FONT> as being pointers to external nodes (leaves) of the binary search tree and the normal, key-bearing nodes as being internal nodes of the tree.<P>A binary search tree is a red-black tree if it satisfies the following <I><B>red-black properties:</I></B><P>1. Every node is either red or black.<P>2. Every leaf (<FONT FACE="Courier New" SIZE=2>NIL</FONT>) is black.<P>3. If a node is red, then both its children are black.<P>4. Every simple path from a node to a descendant leaf contains the same number of black nodes.<P>An example of a red-black tree is shown in Figure 14.1.<P><a name="07ea_14c4"><a name="07ea_14c5"><a name="07ea_14c6"><a name="07ea_14c7">We call the number of black nodes on any path from, but not including, a node <I>x</I> to a leaf the <I><B>black-height</I></B> of the node, denoted bh(<I>x</I>). By property 4, the notion of black-height is well 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.<P><img src="264_a.gif"><P><h4><a name="07ea_14d3">Figure 14.1 A red-black tree with black nodes darkened and red nodes shaded. Every node in a red-black tree is either red or black, every leaf (<FONT FACE="Courier New" SIZE=2>NIL<FONT FACE="Times New Roman" SIZE=2>) is black, the children of a red node are both black, and every simple path from a node to a descendant leaf contains the same number of black nodes. Each non-<FONT FACE="Courier New" SIZE=2>NIL<FONT FACE="Times New Roman" SIZE=2> node is marked with its black-height; <FONT FACE="Courier New" SIZE=2>NIL'S<FONT FACE="Times New Roman" SIZE=2> have black-height 0.<a name="07ea_14d3"></FONT></FONT></FONT></FONT></FONT></FONT></sub></sup></h4><P>The following lemma shows why red-black trees make good search trees.<P><a name="07ea_14d4">Lemma 14.1<a name="07ea_14d4"><P>A red-black tree with <I>n</I> internal nodes has height at most 21g(<I>n</I> + 1).<P><I><B>Proof </I></B>We first show that the subtree rooted at any node <I>x</I> contains at least 2<SUP>bh(<I>x</I>)</SUP> -1 internal nodes. We prove this claim by induction on the height of <I>x</I>. If the height of <I>x</I> is 0, then <I>x</I> must be a leaf (<FONT FACE="Courier New" SIZE=2>NIL</FONT>), and the subtree rooted at <I>x</I> indeed contains at least 2<SUP>bh(<I>x</I>)</SUP>-1 = 2<SUP>0 </SUP>- 1 = 0 internal nodes. For the inductive step, consider a node <I>x</I> that has positive height and is an internal node with two children. Each child has a black-height of either bh(<I>x</I>) or bh(<I>x</I>) - 1, depending on whether its color is red or black, respectively. Since the height of a child of <I>x</I> is less than the height of <I>x</I> itself, we can apply the inductive hypothesis to conclude that each child has at least 2<SUP>bh(<I>x</I>) -1</SUP> -1 internal nodes. Thus, the subtree rooted at <I>x</I> contains at least (2<SUP>bh(<I>x</I>)-1</SUP> -1) + (2<SUP>bh(<I>x</I>)-1</SUP> -1) + 1 = 2<SUP>bh(<I>x</I>)</SUP>- 1 internal nodes, which proves the claim.<P>To complete the proof of the lemma, let <I>h</I> be the height of the tree. According to property 3, at least half the nodes on any simple path from the root to a leaf, not including the root, must be black. Consequently, the black-height of the root must be at least <I>h</I>/2; thus,<P><pre><I>n</I> <img src="../images/gteq.gif"> 2<I><SUP>h/</I>2</SUP> - 1.</sub></sup></pre><P>Moving the 1 to the left-hand side and taking logarithms on both sides yields lg (<I>n</I> + 1) <img src="../images/gteq.gif"> <I>h</I>/2, or <I>h</I> <img src="../images/lteq12.gif"> 21g (<I>n</I> + 1). <P><a name="07ea_14c8"><a name="07ea_14c9"><a name="07ea_14ca"><a name="07ea_14cb"><a name="07ea_14cc"><a name="07ea_14cd"><a name="07ea_14ce"><a name="07ea_14cf"><a name="07ea_14d0"><a name="07ea_14d1">An immediate consequence of this lemma is that the dynamic-set operations <FONT FACE="Courier New" SIZE=2>SEARCH</FONT>, <FONT FACE="Courier New" SIZE=2>MINIMUM</FONT>, <FONT FACE="Courier New" SIZE=2>MAXIMUM</FONT>, <FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT>, and <FONT FACE="Courier New" SIZE=2>PREDECESSOR</FONT> can be implemented in <I>O</I>(lg <I>n</I>) time on red-black trees, since they can be made to run in <I>O</I>(<I>h</I>) time on a search tree of height <I>h</I> (as shown in Chapter 13) and any red-black tree on <I>n</I> nodes is a search tree with height <I>O</I>(lg <I>n</I>). Although the algorithms <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>INSERT</FONT> and <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>DELETE</FONT> from Chapter 13 run in <I>O</I>(lg <I>n</I>) time when given a red-black tree as input, they do not directly support the dynamic-set operations <FONT FACE="Courier New" SIZE=2>INSERT</FONT> and <FONT FACE="Courier New" SIZE=2>DELETE</FONT>, since they do not guarantee that the modified binary search tree will be a red-black tree. We shall see in Sections 14.3 and 14.4, however, that these two operations can indeed be supported in <I>O</I>(lg <I>n</I>) time.<P><h2><a name="07eb_0001">Exercises<a name="07eb_0001"></h2><P><a name="07eb_0002">14.1-1<a name="07eb_0002"><P>Draw the complete binary search tree of height 3 on the keys {1, 2, . . . , 15}. Add the <FONT FACE="Courier New" SIZE=2>NIL</FONT> leaves and color the nodes in three different ways such that the black-heights of the resulting red-black trees are 2, 3, and 4.<P><a name="07eb_0003">14.1-2<a name="07eb_0003"><P>Suppose that the root of a red-black tree is red. If we make it black, does the tree remain a red-black tree?<P><a name="07eb_0004">14.1-3<a name="07eb_0004"><P>Show that the longest simple path from a node <I>x</I> in a red-black tree to a descendant leaf has length at most twice that of the shortest simple path from node <I>x</I> to a descendant leaf.<P><a name="07eb_0005">14.1-4<a name="07eb_0005"><P>What is the largest possible number of internal nodes in a red-black tree with black-height <I>k</I>? What is the smallest possible number?<P><a name="07eb_0006">14.1-5<a name="07eb_0006"><P>Describe a red-black tree on <I>n</I> keys that realizes the largest possible ratio of red internal nodes to black internal nodes. What is this ratio? What tree has the smallest possible ratio, and what is the ratio?<P><P><P>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -