tree - 奇妙な順序を出力する赤黒の木

Question

私のクラスでは、既存のツリーを読み込んで挿入を実行する赤黒ツリープログラムを作成するように依頼されました。ツリーを正しく読み取ることができました。最初のいくつかの挿入は正しく再構築されますが、約2回目または3回目の入力の後、ツリーの順序が教授と一致しません。私は自分のコードを何千回も調べて、疑似コードや C++ の実装と比較しました。私は単にエラーを見つけることができません。

ここで得られる助けをいただければ幸いです。私は誰かに宿題をするように頼んでいるわけではありません。テストケースの入力、教授の出力、および私自身の出力を含めました。また、すべてのコードを含めました。

テストケース入力ファイル

最初の行は、既存のツリーの要素数です。赤の場合は 0、黒の場合は 1。ツリーの後には、挿入する要素の数を示す整数 (この場合は 7) があります。

教授のアウトプット

私の出力

メイクファイル

run: main.o RBnode.o RBnode.h RBTree.o RBTree.h
    g++ -g3 -ggdb -O0 main.o RBnode.o RBTree.o -o RBtree

main.o: main.cpp
    g++ -c main.cpp

clean:
    rm -f RBtree *.o core core.*

tidy: clean
    rm -f *.*~ *~

RBTree.cpp

#include <fstream>
#include<iostream>
#include<cstdio>
#include"RBTree.h"
#include<cstdlib>

// Set up tree
RBtree::RBtree(){


        nil = new RBnode();
        root = nil;

}

RBtree::~RBtree(){

}

// Writes pre-order tree starting at root node to file FD
void RBtree::RBwrite(RBnode* tempRoot, FILE * fd){

        if(tempRoot != nil){

    fprintf(fd,"%d %d\n", tempRoot->colorData, tempRoot->data);

    RBwrite(tempRoot->lchild,fd);
        RBwrite(tempRoot->rchild,fd);

        }

}


// Returns root node of tree
RBnode* RBtree::getRoot(){

        return root;
}

// Insertion for a new node
RBnode* RBtree::RBinsert(int data){

        RBnode* x;
        RBnode* y;

        RBnode* z = new RBnode();
        z->data = data;


        y = this->nil;
        x = this->root;

        while(x != nil)
        {
                y = x;
                if(z->data < x->data)
                        x = x->lchild;
                else
                        x = x->rchild;
        }

        z->parent = y;
        if(y == nil)
            {    root = z;}
                //Empty Tree
        else if(z->data < y->data)
           {     y->lchild = z;}
        else
               { y->rchild = z;}
        z->lchild = nil;
        z->rchild = nil;
        z->changeColor(0);

 return z;

}





// Insertion of existing value from an existing tree
RBnode* RBtree::RBinsert(int color, int data){

        RBnode* z = new RBnode();
        z->changeColor(color);
        z->changeData(data);

        RBnode* x = root;
        RBnode* y = nil;
    while(x != nil)
    {
        y = x;
        if(z->data < x->data)
            x = x->lchild;
        else
            x = x->rchild;
    }
    z->parent = y;
    if(y == nil)
        root = z; //empty as Fword
    else if(z->data < y->data)
       { y->lchild = z;}
    else
       { y->rchild = z;}
    z->lchild = nil;
    z->rchild = nil;

return z;
}


// Fixup function. Based off algorithm from CLRS 
void RBtree::RBinstertFixup(RBnode* z){

        RBnode* y;

while(z->parent->colorData == 0 && z->parent != nil) {

        if(z->parent == z->parent->parent->lchild)
        {
                y = z->parent->parent->rchild;
                if(y->colorData == 0)
                {
                        z->parent->changeColor(1);
                        y->changeColor(1);
                        z->parent->parent->changeColor(0);
                        z = z->parent->parent;
                }
                else
                {
                        if(z == z->parent->rchild)
                        {
                                z = z->parent;
                                Lrotate(z);
                        }
                z->parent->changeColor(1);
                z->parent->parent->changeColor(0);
                Rrotate(z->parent->parent);
                }
        }
        else
        {
                y = z->parent->parent->lchild;
                if(y->colorData == 0)
                {
                        z->parent->changeColor(1);
                        y->changeColor(1);
                        z->parent->parent->changeColor(0);
                        z = z->parent->parent;
                }
                 else
                {
                        if(z == z->parent->lchild)
                        {
                                z = z->parent;
                                Rrotate(z);
                        }
                z->parent->changeColor(1);
                z->parent->parent->changeColor(0);
                Lrotate(z->parent->parent);
                }
        }
}
    root->changeColor(1);
}


// Left rotate
void RBtree::Lrotate(RBnode* x) {

        RBnode* y;

        y = x->rchild;
        x->rchild = y->lchild;
        if(y->lchild != nil)
                y->lchild->parent = x;
        y->parent = x->parent;
        if(x->parent == nil)
                root = y;
        else if(x == x->parent->lchild)
                x->parent->lchild = y;
        else
                x->parent->rchild = y;

        y->lchild = x;
        x->parent = y;
}


// right rotate
void RBtree::Rrotate(RBnode* x) {

        RBnode* y;

        y = x->lchild;
        x->lchild = y->rchild;
        if(y->rchild != nil)
                y->rchild->parent = x;
         y->parent = x->parent;
        if(x->parent == nil)
                root = y;
        else if(x == x->parent->lchild)
                x->parent->lchild = y;
        else
                x->parent->rchild = y;

            y->rchild = x;
            x->parent = y;

}

RBnode.cpp

#include<iostream>
#include"RBnode.h"
#include<cstdlib>

using namespace std;

RBnode::RBnode(){

        int colorData = 1 ;
        parent = NULL;
        lchild = NULL;
        rchild = NULL;
        data = -1;

}
RBnode::~RBnode(){

}
// Assign a color to a node
void RBnode::changeColor(int color){
    this->colorData = color;


}
// Assign data to a node
void RBnode::changeData( int data ){
    this->data = data;
}

RBnode.h

#ifndef RBNODE_H_
#define RBNODE_H_

#include<iostream>
// create reb black node structure
class RBnode{
public:
    RBnode();
    ~RBnode();
    RBnode * parent;
    RBnode * lchild;
    RBnode * rchild;
    int colorData;
        int data;

    void changeColor(int color);
    void changeData(int data);
};



#endif

RBTree.h

#ifndef RBTREE_H_
#define RBTREE_H_
#include<string>
#include <list>
#include<iostream>
#include"RBnode.h"

using std::string;
using std::ifstream;
using namespace std;
// prototype functions
class RBtree{
public:
    RBtree();
    ~RBtree();
    void RBwrite(RBnode* tempRoot, FILE * fd);  
    RBnode* RBinsert(int);
    RBnode* RBinsert(int color, int data);
    void RBinstertFixup(RBnode*);
    void Lrotate(RBnode* x);
    void Rrotate(RBnode* x);
    RBnode* getRoot();

private:
    RBnode* nil;
    RBnode* root;   
};

#endif

main.cpp

#include "RBTree.h"
#include "RBnode.h"
#include <stdint.h>
#include <string>
#include <iostream>
#include <fstream>

using namespace std;

size_t n;
uint32_t data;
RBtree* RB;
bool tree = false;





int main(int argc, char * argv[]){
//declare file pointer
FILE * fs;
FILE * fd;

// init vars here
int n,c;
RBtree* RB = new RBtree();


if (argc < 2){
    printf("ERROR: include the name of the input file as an argument\n");
    return 0;
    }

printf("Attempting to open file %s\n", argv[1]);
char *input = argv[1];
std::ifstream inputfile;
inputfile.open(input);
if(inputfile.fail())  // Error check for file
    {
    std::cout << "The file could not be opened!\n";
    return 0;
    }else{ printf("\nFile opened succesfully!");}
    //begin aquistion of data

fs = fopen(input,"r");
fd = fopen("output.txt","w");
fscanf(fs,"%d",&n);
int color, val;
// Insert existing N number of elements
for(int i = 0; i < n; i++){

    fscanf(fs,"%d %d", &color, &val);

    RB->RBinsert(color, val);

    }

// Insert C number of elements.
fscanf(fs,"%d", &c);
int temp;
for(int i = 0; i < c; i++){

    fscanf(fs,"%d",&temp);
    if(temp != 0){
    RB->RBinstertFixup(RB->RBinsert(temp));
    RB->RBwrite(RB->getRoot(),fd);
    fprintf(fd,"\n\n");
    }


    }

// close files and print status to console
fclose(fd);
fclose(fs);
printf("\nProgram finished!");
return 0;

}

tree - 奇妙な順序を出力する赤黒の木

0 に答える 0

Related

Reference