2

Red Black Tree implementation in C++

 4 months ago
source link: https://gist.github.com/SubCoder1/70c2cedc44353ffc539c7567b1051028
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Red Black Tree implementation in C++ · GitHub

Instantly share code, notes, and snippets.

Red Black Tree implementation in C++

Not working, the recoloring has problems. Test this sequence, 35, 55, 75, 100, 80. all 75, 100, and 80 are red and two reds cant be one after the other.

Storing color as string is extremely inefficient. There are only 2 colors, so it should be stored as a bool

Hey man, I hope you are doing fine!
On the code for the LeftRotate() method above, aren't we missing the recoloring of the x node? See below.

void LeftRotate(node* x) {
            node* nw_node = new node();
            if(x->right->left) { nw_node->right = x->right->left; }
            nw_node->left = x->left;
            nw_node->data = x->data;
            nw_node->color = x->color;
            x->data = x->right->data;
            x->color = x->right->color; **//this line here might be missing**
            x->left = nw_node;
            if(nw_node->left){ nw_node->left->parent = nw_node; }
            if(nw_node->right){ nw_node->right->parent = nw_node; }
            nw_node->parent = x;

            if(x->right->right){ x->right = x->right->right; }
            else { x->right = nullptr; }

            if(x->right){ x->right->parent = x; }
        }

Thanks for posting your code, man! Good job!

Also, on line 124 of the RemoveNode(...) method, since the idea here is to remove the left child of curr, shouldn't the recursive call be
RemoveNode(curr, curr->left, stuff);
instead of
RemoveNode(curr, curr->right, stuff); ?

Thanks again!

i am confused in one thing if user enters 1 insert value in the tree but if users enters 7 it should read the file .

Seems good... easy to make so the color is bool or uint8_t. Just interested in the order lowest to highest so fiddled the output function. Been looking for a fast BPlus Tree but this seemed just as good and has the right output.

Need fast ability to sort scene elements in a game engine which at the moment is a binary tree that's suffering due to being unbalanced for ~1000 inserts. I will pre-allocate all the nodes at the start and instead of allocating all the time just pull them from a pool. Also... due to this allocation pruning the tree is as simple as resetting the root each time.

   void InOrderTraversal(node* temp) 
    {
        if(!temp)
        {
            return; 
        }

        if (temp->left)
        {
            InOrderTraversal(temp->left);
             printf(">%d%c\n", temp->data,  (temp->color ? 'B' : 'R')) ;
        }
        else
        {
            printf(">%d%c\n", temp->data,  (temp->color ? 'B' : 'R')) ;
        }

        if (temp->right)
        {
            InOrderTraversal(temp->right);
        }
    }

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK