[study note] Following
red-black tree article is collected from
http://www.cs.auckland.ac.nz/~jmor159/PLDS210/red_black.html.
red-black tree is a balanced binary search tree like AVL tree or Splay Tree. At the end of the article, a C++ implemetation of
red-black tree is attached for reference.
A
red-black tree is a binary search tree with one extra attribute for each node: the
colour, which is either red or black. We also need to keep track of the parent of each node, so that a
red-black tree's node structure would be:
struct t_red_black_node {
enum { red, black } colour;
void *item;
struct t_red_black_node *left,
*right,
*parent;
}
For the purpose of this discussion, the NULL nodes which terminate the tree are considered to be the leaves and are coloured black.
Definition of a red-black tree
A
red-black tree is a binary search tree which has the following
red-black properties:
- Every node is either red or black.
- Every leaf (NULL) is black.
- If a node is red, then both its children are black.
- Every simple path from a node to a descendant leaf contains the same number of black nodes.
|
- implies that on any path from the root to a leaf, red nodes must not be adjacent.
However, any number of black nodes may appear in a sequence.
|
 | A basic red-black tree |
 | Basic red-black tree with the sentinel nodes added. Implementations of the red-black tree algorithms will usually include the sentinel nodes as a convenient means of flagging that you have reached a leaf node. They are the NULL black nodes of property 2. |
The number of black nodes on any path from, but not including, a node
x to a leaf is called the
black-height of a node, denoted
bh(x). We can prove the following lemma:
1:#include <iostream>
2:#include <sstream>
3:#include <string>
4:#include <vector>
C++ 5:
6:// SEE UPDATE COMMENTS AT END OF FILE
7:// 2006-01.29 fixed memory leaks
8:
9:// eliminate need to qualify standard library with std::
C++ 10:using namespace std;
11:
12:// ===============================================================
13:// C++ NEEDS SOME DECLARATIONS BEFORE THE MAIN RedBlackTree class.
14:// skip down a little to line this up with the other side
C++ 15:// ===============================================================
16:// requires forward declaration to resolve cycle between NodeVisitor and RedBlackTree
17:template<class T> class RedBlackTree;
18:
19:// use an abstract class for the node visitor. it is templatized to match the templated RedBlackTree declaration
C++ 20:template<class T> class NodeVisitor {
21:public:
22: // need a virtual destructor for the concrete classes
23: virtual ~NodeVisitor() {}
24:
C++ 25: // ise a pure virtual function so a concrete class must implement
26: // the proper signature
27: virtual void visit(const RedBlackTree<T> *node,int depth) = 0;
28:};
29:
C++ 30:// =============================================
31:// >>>>>>>>>>>>>>>>> RED BLACK TREE STARTS HERE
32:// =============================================
33:// in line with the STL conventions, this template uses 'by-value' semantics for the contained
34:// object. This means that the 'T' object will need to have the correct constructor and copy assignment
C++ 35:// semantics or it won't work. primitive types are OK but object instances would have to be
36:// put together correctly.
37:template<class T> class RedBlackTree {
38:
39:private:
C++ 40: /*
41: Red/Black tree implementation based on
42: Algorithms in C++, Sedgewick
43: Introduction To Algorithms Cormen, Thomas H. / Leiserson, Charl es E . / Rivest, Ronald L . The MIT Press 07/1990
44: NOTE : LOOK AT END OF FILE TO SEE DIFFERENCES IN TRAVERSAL IDIOMS
C++ 45: */
46:
47: // yes, i could use an enum but since i want to print the values, using an enum is more
48: // trouble than it is worth.
49: static const int red = 0;
C++ 50: static const int black = 1;
51:
52: // use a common instance variable naming convention 'm_'. others use a single leading '_'
53: int m_color;
54: T m_val;
C++ 55: RedBlackTree *m_left;
56: RedBlackTree *m_right;
57:
58: RedBlackTree(RedBlackTree *b) {
59: m_val = b->m_val;
C++ 60: m_left = b->m_left;
61: m_right = b->m_right;
62: m_color = red;
63: }
64:
C++ 65: void copy(RedBlackTree *x) {
66: m_val = x->m_val;
67: m_left = x->m_left;
68: m_right = x->m_right;
69: m_color = x->m_color;
C++ 70:
71: // UPDATE 2006-01-28
72: // node pointed to by 'x' is no longer needed, delete it.
73: // first make sure the delete won't descend into other nodes
74: x->m_left = 0;
C++ 75: x->m_right = 0;
76: delete x;
77: }
78:
79: RedBlackTree *RBinsertLeft(T k,int sw) {
C++ 80: RedBlackTree *l;
81: RedBlackTree *b;
82:
83: l = m_left;
84: if (l == 0) {
C++ 85: m_left = b = new RedBlackTree(k);
86: }
87: else {
88: b = l->RBinsert(k,sw);
89: }
C++ 90: return b;
91: }
92:
93: RedBlackTree *RBinsertRight(T k,int sw) {
94: RedBlackTree *r;
C++ 95: RedBlackTree *b;
96:
97: r = m_right;
98: if (r == 0) {
99: m_right = b = new RedBlackTree(k);
C++ 100: }
101: else {
102: b = r->RBinsert(k,sw);
103: }
104: return b;
C++ 105: }
106:
107: RedBlackTree *rotLeft()
108: {
109: RedBlackTree *x;
C++ 110: RedBlackTree *me;
111:
112: if (m_right == 0) return 0;
113: // make the changes in a copy of current node __self
114: // on return, the caller will copy in 'me' to current node
C++ 115: me = new RedBlackTree(this);
116: x = me->m_right;
117: me->m_right = x->m_left;
118: x->m_left = me;
119: return x;
C++ 120: }
121:
122: RedBlackTree *rotRight()
123: {
124: RedBlackTree *x;
C++ 125: RedBlackTree *me;
126:
127: if (m_left == 0) return 0;
128:
129: // make the changes in a copy of current node __self
C++ 130: // on return, the caller will copy in 'me' to current node
131: me = new RedBlackTree(this);
132: x = me->m_left;
133: me->m_left = x->m_right;
134: x->m_right = me;
C++ 135: return x;
136: }
137:
138: RedBlackTree *RBinsert(T k,int sw) {
139: RedBlackTree *b = 0;
C++ 140: RedBlackTree *x;
141: RedBlackTree *l;
142: RedBlackTree *ll;
143: RedBlackTree *r;
144: RedBlackTree *rr;
C++ 145:
146: // if current node is a 4 node, split it by flipping its colors
147: // if both children of this node are red, change this one to red
148: // and the children to black
149: l = m_left;
C++ 150: r = m_right;
151: if ((l != 0)&&(l->m_color==red)&&(r != 0)&&(r->m_color==red)) {
152: m_color = red;
153: l->m_color = black;
154: r->m_color = black;
C++ 155: }
156:
157: // go left or right depending on key relationship
158: if (k < m_val) {
159: // recursively insert
C++ 160: b = RBinsertLeft(k,0);
161:
162: // on the way back up check if a rotation is needed
163: // if search path has two red links with same orientation
164: // do a single rotation and flip the color bits
C++ 165: l = m_left;
166: if ((m_color == red)&&(l != 0)&&(l->m_color == red)&&(sw == 1)) {
167: x = rotRight();
168: if (x != 0) {
169: // copy returned node to 'this'
C++ 170: copy(x);
171: }
172: }
173:
174: // flip the color bits
C++ 175: l = m_left;
176: if (l != 0) {
177: ll = l->m_left;
178: if (ll != 0) {
179: if ((l->m_color == red)&&(ll->m_color == red)) {
C++ 180: x = rotRight();
181: if (x != 0) {
182: copy(x);
183: }
184: m_color = black;
C++ 185: r = m_right;
186: if (r != 0) {
187: r->m_color = red;
188: }
189: }
C++ 190: }
191: }
192: }
193: else {
194: b = RBinsertRight(k,1);
C++ 195:
196: // on the way back up check if a rotation is needed
197: // if search path has two red links with same orientation
198: // do a single rotation and flip the color bits
199: r = m_right;
C++ 200: if ((m_color == red)&&(r != 0)&&(r->m_color == red)&&(sw == 0)) {
201: x = rotLeft();
202: if (x != 0) {
203: // copy returned node to 'this'
204: copy(x);
C++ 205: }
206: }
207:
208: // flip the color bits
209: r = m_right;
C++ 210: if (r != 0) {
211: rr = r->m_right;
212: if (rr != 0) {
213: if ((r->m_color == red)&&(rr->m_color == red)) {
214: x = rotLeft();
C++ 215: if (x != 0) {
216: // copy returned node to 'this'
217: copy(x);
218: }
219: m_color = black;
C++ 220: l = m_left;
221: if (l != 0) {
222: l->m_color = red;
223: }
224: }
C++ 225: }
226: }
227: }
228:
229: return b;
C++ 230: }
231:
232:// ==================================================
233:// PUBLIC METHODS
234:// ==================================================
C++ 235:public:
236: // construct with an initial value
237: RedBlackTree(T x) {
238: m_val = x;
239: m_left = 0;
C++ 240: m_right = 0;
241: m_color = red;
242: }
243:
244: ~RedBlackTree() {
C++ 245:
246: if (m_left != 0) {
247: delete m_left;
248: }
249: if (m_right != 0) {
C++ 250: delete m_right;
251: }
252: }
253:
254: // return a string representation
C++ 255: string str() const {
256: stringstream s(stringstream::out);
257: // m_val (type T) must have the proper ostream insertion operator
258: // or this implementation won't work
259: s << "[" << m_val << "," << m_color << "]";
C++ 260: return s.str();
261: }
262:
263: // 'const' means this method doesn't change the object state
264: T val() const {
C++ 265: return m_val;
266: }
267:
268: // 'const' means this method doesn't change the object state
269: int color() const {
C++ 270: return m_color;
271: }
272:
273: // 'const' means this method doesn't change the object state
274: // and it returns a pointer to a const node that the caller
C++ 275: // cannot change, only inspect
276: const RedBlackTree *find(const T &key) const {
277: const RedBlackTree *result = 0;
278: if (key == m_val) {
279: result = this;
C++ 280: }
281: else if (key < m_val) {
282: if (m_left != 0) {
283: result = m_left->find(key);
284: }
C++ 285: }
286: else {
287: if (m_right != 0) {
288: result = m_right->find(key);
289: }
C++ 290: }
291: return result;
292: }
293:
294: // 'const' means this method doesn't change the object state
C++ 295: // and the visitor is not allowed to change the object state.
296: // that may not be what is desired but is used here to
297: // illustrate something you can do in C++ that you can't do
298: // in the other languages and that illustrates the bias towards
299: // extensive static type checking
C++ 300: void inorder(NodeVisitor<T> *visitor,int depth) const {
301: if (m_left != 0) {
302: m_left->inorder(visitor,depth+1);
303: }
304: visitor->visit(this,depth);
C++ 305: if (m_right != 0) {
306: m_right->inorder(visitor,depth+1);
307: }
308: }
309:
C++ 310: RedBlackTree *insert(T k) {
311: RedBlackTree *b;
312: b = RBinsert(k,0);
313: m_color = black;
314: return b;
C++ 315: }
316:};
317:
318:// define a concrete class for the node visitor
319:class IntNodeVisitor : public NodeVisitor<int> {
C++ 320:public:
321: virtual ~IntNodeVisitor() {}
322:
323: // the node is 'const' so the visitor can't change it, only look at it
324: virtual void visit(const RedBlackTree<int> *node,int depth) {
C++ 325: if (node->val() != 0) {
326: cout << "(" << node->val() << ":" << node->color() << ":" << depth << "), ";
327: }
328: }
329:};
C++ 330:
331:// ==================================
332:// test program
333:// ==================================
334:int main(int argc,char *argv[]) {
C++ 335: int nodelist[] = {11,4,8,14,17,6,9,7,16,15,13,5,19,18,12,10,3,20,1};
336: NodeVisitor<int> *v;
337:
338: // insert all the data into the tree
339: RedBlackTree<int> *root = new RedBlackTree<int>(2);
C++ 340:
341: // need to do an ugly calculation to figure out length of the nodelist array
342: // if i used a collection object instead of an array, then I couldn't have
343: // done static initialization. so its a tradeoff
344: for(int i=0;i<(sizeof(nodelist)/sizeof(nodelist[0]));i++) {
C++ 345: root->insert(nodelist[i]);
346: }
347:
348: // anonymous class implementing the NodeVisitor interface
349: v = new IntNodeVisitor;
C++ 350:
351: // print the header
352: cout << "C++ = ";
353: // visit all the nodes in order
354: root->inorder(v,0);
C++ 355: // print a newline
356: cout << endl;
357:
358: // find the specified element and print its value
359: const RedBlackTree<int> *x = root->find(16);
C++ 360: cout << x->str() << endl;
361:
362: // no garbage collection, need to explicitly delete
363: delete root; // will recursively delete all the nodes
364: delete v;
C++ 365:}
366:
367:
368:// ===================================================================
369:// UPDATE 2006-01-29
C++ 370:// there are memory leaks that need to be fixed.
371:// 1. the algorithm leaks nodes after a rotate
372:// two possible fixes :
373:// find where the leaks occur and do the needed deletes
374:// in this case the 'copy' method handles
C++ 375:// deleting unused nodes
376:// use an appropriate smart pointer to handle deleteing
377:// 2. the tree is not properly disposed of when the program completes
378:// In the STL tradition a delete of the tree should
379:// delete all tree resources but not the contained data. the application
C++ 380:// should handle deleting the contained data elements, if needed, prior
381:// to deleting the tree. In this case a recursive delete of the
382:// nodes works gets rid of the tree resources
383://
384:// these issue show that one of the big difficulties in C++ is to
C++ 385:// handle disposing of data after you are done with it. that is indeed a
386:// source of many C++ program errors of the type that are related more to
387:// dealing with the complexity of the language rather than the solving
388:// the problem. In this code the leaks are probably fixed but there is always
389:// a lingering doubt "Did I get all the leaks?"
C++ 390:// Thats a problem with C++, its hard to be certain.
391://
392:// a modern approach is to use smart pointers to simulate garbage
393:// collection. the Boost library referenced counted smart pointers
394:// will be included in the next standard revision of the C++ library
C++ 395:// so they are used here to handle all the cases.
396:// ===================================================================
397:
398:
