Rot-Schwarz-Baum einfügen, ich glaube ich habe den Rotationen Durcheinander

Ich habe versucht, erstellen Sie eine rot-schwarz-Baum, implementiert nur eine insert, search und in-order-traversal-Methode, so dass ich es vergleichen kann, um eine ähnliche AVL-Baum, den ich vorher gemacht. Ich habe alle algorithmen, die in der Cormen text: Einführung in Algorithmen, aber für einige Grund, warum ich kann nicht scheinen, um es richtig funktioniert.

Wenn ich zum Beispiel einfügen von a, b, c und versuchen, führen Sie eine in-order-traversal, ich bin zu verlieren". c. Ich habe über die algorithmen, die in den text ca 10 mal, um sicherzustellen, dass ich alles richtig und ich kann nicht scheinen zu finden, keine Fehler.

Kann mir jemand sagen, wenn ich mache insertFix() Methode richtig, wie auch die Rotationen.

Unten ist meine header-Datei, um Ihnen eine Idee, wie ich die Knoten:

class RBT
{
private:
    struct node
    {
        int count;                  //counts the number of times the string has been inserted
        std::string  data;          //Storage for String Data
        node         *parent;       //pointer to this node's parent
        node         *LCH;          //pointer to this node's left child
        node         *RCH;          //pointer to this node's right child
        bool         isRed;         //bool value to specify color of node
    };

    node *root;                     //pointer to the tree's root node
    node *nil;                      //nil node used to implement RBT(aka sentinel)
    void traverse(node *t);         //perform an in-order traversal
    int  height(node *p);           //gets height of tree
    int  totalNodes(node *p);       //gets total nodes in tree
    int  totalWords(node *p);       //gets total words in tree
    void insertFix(node *z);        //fixes tree if RBT rules are broken
    void RR(node *z);               //performs Right rotation at z
    void LR(node *z);               //performs Left rotation at z

public:
    int  insert(std::string str);   //tries to add str to tree.  Returns the new count for str
    int  search(std::string str);   //searches for str.  Returns count for str, 0 if not found
    void list();                    //prints in-order traversal of tree  
    void getHeight();               //prints the height of tree
    void getTotal();                //prints the total number of nodes in the tree, as well as total number of words
    void getComparisons();          //prints the number of comparisons used
    RBT();                          //constructor -- just builds an empty tree with a NULL root pointer
    int  numComp;                   //tracks number of comparisons, only counts for search and insert commands
};

Und hier ist mein insertFix() Methode, die lief nach einer normalen einfügen, die man in einem gewöhnlichen binären Suchbaum:

void RBT::insertFix(node *z)
{
    //Private method to fix any rules that might be broken in the RBT.
    //Takes a starting node z, as an input parameter and returns nothing,
    //except for a happy feeling knowing the you are not breaking any RBT laws.
    //Definitions of placeholder nodes used in this method:
    //z  = z
    //y  = left or right uncle of z  

    node *y;

    while (z->parent->isRed)
    {
        if(z->parent == z->parent->parent->LCH)
        {
            y = z->parent->parent->RCH;
            if(y->isRed)
            {
                z->parent->isRed = false;
                y->isRed = false;
                z->parent->parent->isRed = true;
                z = z->parent->parent;
            }
            else
            {
                if( z == z->parent->RCH)
                {
                    z = z->parent;
                    RBT::LR(z);
                }
                z->parent->isRed = false;
                z->parent->parent->isRed = true;
                RBT::RR(z);
            }
        }
        else
        {
            y = z->parent->parent->LCH;
            if(y->isRed)
            {
                z->parent->isRed = false;
                y->isRed = false;
                z->parent->parent->isRed = true;
                z = z->parent->parent;
            }
            else
            {
                if( z == z->parent->LCH)
                {
                    z = z->parent;
                    RBT::RR(z);
                }
                z->parent->isRed = false;
                z->parent->parent->isRed = true;
                RBT::LR(z);
            }
        }
    }
    root->isRed = false;
}

Unten sind meine zwei rotation Methoden, eine ist die Drehrichtung Rechts (RR), und die andere ist eine Links-Drehung (LR):

void RBT::LR(node *x)
{
    //Method to perform a Left Rotation at Node z. Takes a node pointer
    //as a parameter. Returns void.

    node *y; //y is x's right child
    y = x->RCH;
    x->RCH = y->LCH;
    if (y->LCH != nil) {y->LCH->parent = x;}
    y->parent = x->parent;
    if (x->parent == nil) {root = y;}
    else
    {
        if (x == x->parent->LCH) {x->parent->LCH = y;}
                            else {x->parent->RCH = y;}
    }
    y->LCH = x;
    x->parent = y;
}

void RBT::RR(node *x)
{
    //Method to perform a Left Rotation at Node z. Takes a node pointer
    //as a parameter. Returns void.

    node *y; //y is x's left child
    y = x->LCH;
    x->LCH = y->RCH;
    if (y->RCH != nil) {y->RCH->parent = x;}
    y->parent = x->parent;
    if (x->parent == nil) {root = y;}
    else
    {
        if (x == x->parent->RCH) {x->parent->RCH = y;}
                            else {x->parent->LCH = y;}
    }
    y->RCH = x;
    x->parent = y;
}

Ich weiß, das ist eine Menge code vorbei zu schauen, aber ich bin mit meinem Latein am Ende versucht, herauszufinden, was ich falsch mache. Ich habe das Gefühl, ich bin in Unordnung, bis der Zeiger irgendwo in der Rotation, aber ich kann nicht herausfinden, wo. Jede Hilfe wäre wirklich dankbar!