1

以前に作成した同様のAVLツリーと比較できるように、挿入、検索、および順序どおりのトラバーサルメソッドのみを実装する赤黒木を作成しようとしています。コーメンのテキスト「アルゴリズムの概要」にあるすべてのアルゴリズムを使用しましたが、何らかの理由で正しく機能しないようです。

たとえば、a、b、cの順に挿入して順番に走査しようとすると、cが失われます。私はテキストのアルゴリズムを約10回調べて、すべてが正しく、間違いを見つけられないことを確認しました。

insertFix()私がメソッドを正しく実行しているかどうか、およびローテーションを誰かに教えてもらえますか？

以下は、ノードをどのように設定したかを示すためのヘッダーファイルです。

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
};

そしてinsertFix()、これが私のメソッドです。これは、通常のバイナリ検索ツリーにある通常の挿入の後に実行されます。

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;
}

以下は私の2つの回転方法です。1つは右回転（RR）で、もう1つは左回転（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;
}

私はこれが見過ごされるべき多くのコードであることを知っています、しかし私は自分が間違っていることを見つけようとしている私の知恵の終わりにいます。回転のどこかでポインタをめちゃくちゃにしているような気がしますが、どこにあるのかわかりません。どんな助けでも本当にありがたいです！

4

1 に答える 1

2

insertFix（）関数のこのセクションでは、次のようにします。

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

変更する必要があります

            RBT::RR(z);

に

            RBT::RR(z->parent->parent);

同じ機能の左回転ケースと同じ：

            RBT::LR(z);

に

            RBT::LR(z->parent->parent);
于 2011-03-28T08:00:47.527 に答える