📄 s_rbt.htm
字号:
<html>
<head>
<title>Red-Black Trees</title>
</head>
<body bgcolor="#ffffff">
<p align=right>
<a href="s_man.htm" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_man.htm" target="_top"><img src="c_man.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/c_man.gif" width=74 height=19 border=0></a>
</p>
<h1>Red-Black Trees</h1>
Binary search trees work best when they are balanced or the path
length from root to any leaf is within some bounds. The red-black
tree algorithm is a method for balancing trees. The name
derives from the fact that each node is colored <i>red</i> or <i>black</i>, and
the color of the node is instrumental in determining the balance
of the tree. During insert and delete operations, nodes may be
rotated to maintain tree balance. Both average and worst-case
search time is <b><i>O</i></b>(lg <i>n</i>). For details, consult
<a href="javascript:if(confirm('http://www.amazon.com/exec/obidos/ISBN=0262031418/none01A/ \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://www.amazon.com/exec/obidos/ISBN=0262031418/none01A/'" tppabs="http://www.amazon.com/exec/obidos/ISBN=0262031418/none01A/" target="_top">Cormen [1990]</a>.
<h2>Theory</h2>
A red-black tree is a balanced binary search tree with the
following properties:
<ol>
<li>Every node is colored red or black.
<li>Every leaf is a <b>NIL</b> node, and is colored black.
<li>If a node is red, then both its children are black.
<li>Every simple path from a node to a descendant leaf contains
the same number of black nodes.
</ol>
The number of black nodes on a path from root to leaf is known as
the black-height of a tree. These properties guarantee that any
path from the root to a leaf is no more than twice as long as any
other. To see why this is true, consider a tree with a black
height of two. The shortest distance from root to leaf is two,
where both nodes are black. The longest distance from root to
leaf is four, where the nodes are colored (root to leaf): red,
black, red, black. It is not possible to insert more black nodes
as this would violate property 4, the black-height requirement.
Since red nodes must have black children (property 3), having two
red nodes in a row is not allowed. The largest path we can
construct consists of an alternation of red-black nodes, or twice
the length of a path containing only black nodes. All operations
on the tree must maintain the properties listed above. In
particular, operations which insert or delete items from the tree
must abide by these rules.
<h2>Insertion</h2>
To insert a node, we search the tree for an insertion point, and
add the node to the tree.
A new node replaces an existing <b>NIL</b> node at the bottom of the tree,
and has two <b>NIL</b> nodes as children. In the implementation, a <b>NIL</b>
node is simply a pointer to a common <i>sentinel</i> node that is colored black.
After insertion, the new node
is colored red. Then the parent of the node is examined to
determine if the red-black tree properties have been violated.
If necessary, we recolor the node and do rotations to balance the
tree.
<p>
By inserting a red node
with two <b>NIL</b> children, we have preserved black-height
property (property 4). However, property 3 may be violated.
This property states that both children of a red node must be
black. Although both children of the new node are black (they're
<b>NIL</b>), consider the case where the parent of the new node is red.
Inserting a red node under a red parent would violate this
property. There are two cases to consider:
<ul>
<li> <i>Red parent, red uncle</i>:
Figure 3-6 illustrates a red-red
violation. Node <b>X</b> is the newly inserted node, with both parent
and uncle colored red. A simple recoloring removes the red-red
violation. After recoloring, the grandparent (node <b>B</b>) must be
checked for validity, as its parent may be red. Note that this
has the effect of propagating a red node up the tree. On
completion, the root of the tree is marked black. If it was
originally red, then this has the effect of increasing the black-height
of the tree.
<p>
<li> <i>Red parent, black uncle</i>:
Figure 3-7 illustrates a red-red
violation, where the uncle is colored black. Here the nodes may
be rotated, with the subtrees adjusted as shown. At this point
the algorithm may terminate as there are no red-red conflicts and
the top of the subtree (node <b>A</b>) is colored black. Note that if
node <b>X</b> was originally a right child, a left rotation would be
done first, making the node a left child.
</ul>
Each adjustment made while inserting a node causes us to travel
up the tree one step. At most 1 rotation (2 if the node is a
right child) will be done, as the algorithm terminates in this
case. The technique for deletion is similar.
<p>
<center>
<h3><a name="Fig3-6">
<img src="s_fig36.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_fig36.gif" vspace=5 width=403 height=602><br>
Figure 3-6: Insertion - Red Parent, Red Uncle</a>
</h3>
</center>
<p>
<p>
<center>
<h3><a name="Fig3-7">
<img src="s_fig37.gif" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_fig37.gif" vspace=5 width=499 height=632><br>
Figure 3-7: Insertion - Red Parent, Black Uncle</a>
</h3>
</center>
<p>
<h2>Implementation</h2>
An
<a href="javascript:if(confirm('http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_rbt.txt \n\nThis file was not retrieved by Teleport Pro, because it is linked too far away from its Starting Address. If you increase the in-domain depth setting for the Starting Address, this file will be queued for retrieval. \n\nDo you want to open it from the server?'))window.location='http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_rbt.txt'" tppabs="http://www.ee.uwa.edu.au/~plsd210/ds/niemann/s_rbt.txt">ANSI-C implementation</a>
for red-black trees is included.
<b>Typedef T</b> and comparison operators <b>compLT</b>
and <b>compEQ</b> should be altered to reflect the data stored in the
tree. Each <b>Node</b> consists of <b>left</b>, <b>right</b>, and <b>parent</b> pointers
designating each child and the parent. The node color is stored
in <b>color</b>, and is either <b>RED</b> or <b>BLACK</b>. The data is stored in the
<b>data</b> field. All leaf nodes of the tree are <b>sentinel</b> nodes, to
simplify coding. The tree is based at <b>root</b>, and initially is a
<b>sentinel</b> node.
<p>
Function <b>insertNode</b> allocates a new node and inserts it in the tree.
Subsequently, it calls <b>insertFixup</b> to ensure that the red-black
tree properties are maintained. Function
<b>deleteNode</b> deletes a node from
the tree. To maintain red-black tree properties, <b>deleteFixup</b> is
called. Function <b>findNode</b> searches the tree for a particular value.
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -