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: