Red Black Tree Insert Issue
I am new to red black trees and I am having trouble where this issue is coming from. The rotations and the insertion method looks correct. However, when I enter the numbers
100
45
34
55
74
50
130
120
125
160
165
150
I get the below output from the program. The right most number is the number in the node, then the color, then the parent of the node. The root node does not have a parent listed. Nodes 45 and 74 are both RED and both of these nodes can't be both red because that violates the RED Black Tree property: red parents always have two black children. Any help on this matter would be great.
34 [BLACK] (45)
45 [RED] (74)
50 [RED] (55)
55 [BLACK] (45)
74 [RED] (120)
100 [BLACK] (74)
120 [BLACK]
125 [BLACK] (130)
130 [RED] (120)
150 [RED] (160)
160 [BLACK] (130)
165 [RED] (160)
RedBlackTree.h /*
#ifndef RBTREE
#define RBTREE
#include <iostream>
#include "nodes.h"
#include "BinarySearchTree.h"
using namespace std;
/*
* RedBlackTree
*
* Class defination of RedBlackTree.
*
* This class represents a Red Black Tree data structure where the data is to be
* stored in a node. It is extended from BinarySearchTree.h
*
* @see BinarySearchTree.h, nodes.h
*
*/
class RedBlackTree : protected BST
{
private:
//RBTreeNode *root;
bool rotateLeft(RBTreeNode *);
bool rotateRight(RBTreeNode *);
bool insertFix(RBTreeNode *);
bool delFix(RBTreeNode *);
void recurseDisplay(RBTreeNode *);
RBTreeNode * findNode(int);
public:
RedBlackTree();
bool insert(int);
void display();
bool del(int);
RBTreeNode * successor(int);
RBTreeNode * getRoot();
void setRoot(RBTreeNode *);
~RedBlackTree();
};
#endif
RedBlackTree.cpp The BST::insert(rbnode) function works fine with this class because the differences in the function are done before the other function is used.
#include <iostream>
#include "RedBlackTree.h"
using namespace std;
#define RED 1
#define BLACK 2
/*
* Constructor
*/
RedBlackTree::RedBlackTree(){
setRoot(NULL);
}
/*
* Destructor
*/
RedBlackTree::~RedBlackTree(){
while(getRoot() != NULL){
del(getRoot()->word);
}
}
/*
* get the root
*/
RBTreeNode * RedBlackTree::getRoot(){
return static_cast<RBTreeNode *>(BST::getRoot());
}
/*
* set the root
*/
void RedBlackTree::setRoot(RBTreeNode *rootin){
BST::setRoot(rootin);
}
/*
* Inserts the string into the tree.
*
* @param String The string to add to the tree
* @return False if already in the tree
*/
bool RedBlackTree::insert(int word){
RBTreeNode *rbnode = new RBTreeNode;
rbnode->color = RED;
rbnode->word = word;
rbnode->setLeft(NULL);
rbnode->setRight(NULL);
if(BST::insert(rbnode)){
insertFix(rbnode);
return true;
}else{
delete rbnode;
return false;
}
}
/*
* Display the items in a tree in order and with color
*
* @param RBTreeNode The next node to recurse on
*/
void RedBlackTree::recurseDisplay(RBTreeNode *node){
if(node != NULL){
recurseDisplay(node->getLeft());
cout<<node->word<<"";
cout<<" [";
if(node->color == RED){cout<<"RED";}
if(node->color == BLACK){cout<<"BLACK";}
cout<<"] ";
if(node->getParent() != NULL){
cout << "(" << node->getParent()->word<<")\n";
}else{
cout<<"\n";
}
recurseDisplay(node->getRight());
}
return;
}
/*
* Display the items in a tree in order
*
*/
void RedBlackTree::display(){
recurseDisplay(getRoot());
return;
}
/* Delete a word from the tree
*
* @param string The string to delete
* @return bool False if it does not exist in tree
*/
bool RedBlackTree::del(int word){
RBTreeNode *x, *y, *z;
z = findNode(word);
if(z == NULL){
return false;
}
if((z->getLeft() == NULL) || (z->getRight() == NULL)){
y = z;
}else{
y = successor(z->word);
}
if((y != NULL) && (y->getLeft() != NULL)){
x = y->getLeft();
}else if(y != NULL){
x = y->getRight();
}
if((y != NULL) && (y->color == BLACK)){
delFix(x);
}
return BST::del(word);
}
/*
* Search for the successor of a string and return it if in tree
*
* @param String The string whose successor to search for
* @return RBTreeNode if string in the tree else return null
*/
RBTreeNode * RedBlackTree::successor(int word){
TreeNode *tnode;
tnode = BST::successor(word);
return static_cast<RBTreeNode *>(tnode);
}
bool RedBlackTree::rotateLeft(RBTreeNode *node_x){
RBTreeNode *node_y;
if(node_x->getRight() == NULL){
return false;
}
node_y = node_x->getRight();
if(node_y->getLeft() != NULL){
node_y->getLeft()->setParent(node_x);
node_x->setRight(node_y->getLeft());
}
node_y->setParent(node_x->getParent());
if(node_x->getParent() == NULL){
setRoot(node_y);
}else if(node_x == node_x->getParent()->getLeft()){
node_x->getParent()->setLeft(node_y);
}else{
node_x->getParent()->setRight(node_y);
}
node_x->setRight(node_y->getLeft());
node_y->setLeft(node_x);
node_x->setParent(node_y);
return true;
}
/*
* Rotate the tree right on y
*
* @param RBTreeNode The node to rotate on
* @return False if node to ret on deos not exist
*/
bool RedBlackTree::rotateRight(RBTreeNode *node_y){
RBTreeNode *node_x;
if(node_y->getLeft() == NULL){
return false;
}
node_x = node_y->getLeft();
if(node_x->getRight() != NULL){
node_x->getRight()->setParent(node_y);
node_y->setLeft(node_x->getRight());
}
node_x->setParent(node_y->getParent());
if(node_y->getParent() == NULL){
setRoot(node_x);
}else if(node_y == node_y->getParent()->getLeft()){
node_y->getParent()->setLeft(node_x);
}else{
node_y->getParent()->setRight(node_x);
}
node_y->setLeft(node_x->getRight());
node_x->setRight(node_y);
node_y->setParent(node_x);
return true;
}
/*
* Maintains the red black tree properties after a node is deleted
*
* @param RBTreeNode The node that is in violation
* @return true always
*/
bool RedBlackTree::delFix(RBTreeNode *nodein){
RBTreeNode *x, *w;
x = nodein;
while( x != getRoot() && x != NULL && x->color == BLACK){
if(x->getParent()->getLeft() == x){
w = x->getParent()->getRight();
if(w != NULL && w->color == RED){
w->color = BLACK;
x->getParent()->color = RED;
rotateLeft(x->getParent());
w = x->getParent()->getRight();
}
if((w != NULL && w->getLeft() != NULL) &&
(w->getLeft()->color == BLACK) &&
(w->getRight() && w->getRight()->color == BLACK)){
w->color = RED;
x = x->getParent();
}else if(w != NULL && w->getRight()->color == BLACK){
w->getLeft()->color = BLACK;
w->color = RED;
rotateRight(w);
w = x->getParent()->getRight();
}
if((w != NULL) && (x->getParent() != NULL)){
w->color = x->getParent()->color;
}
if(x->getParent() != NULL){
x->getParent()->color = BLACK;
}
if(w != NULL && w->getRight() != NULL){
w->getRight()->color = BLACK;
}
rotateLeft(x->getParent());
x = getRoot();
}else{
w = x->getParent()->getLeft();
if((w != NULL) && (w->color == RED)){
w->color = BLACK;
x->getParent()->color = RED;
rotateRight(x->getParent());
w = x->getParent()->getLeft();
}
if(w != NULL){
if((w->getRight()->color == BLACK) &&
(w->getLeft()->color == BLACK)){
w->color = RED;
x = x->getParent();
}else if(w->getLeft()->color == BLACK){
w->getRight()->color = BLACK;
w->color = RED;
rotateLeft(w);
w = x->getParent()->getLeft();
}
}
if(w !=NULL){
w->color = x->getParent()->color;
w->getLeft()->color = BLACK;
}
if(x != NULL && x->getParent() != NULL){
x->getParent()->color = BLACK;
rotateRight(x->getParent());
}
x = getRoot();
}
}
if(x != NULL){
x->color = BLACK;
}
return true;
}
/*
* Maintains the red black tree properties after a node is inserted
*
* @param RBTreeNode The node that is in violation
* @return true always
*/
bool RedBlackTree::insertFix(RBTreeNode *nodein){
RBTreeNode *y, *z;
z = nodein;
while((z->getParent() !=NULL) && z->getParent()->color == RED){
if((z->getParent() != NULL) &&
(z->getParent() == z->getParent()->getParent()->getLeft())){
y = z->getParent()->getParent()->getRight();
if((y != NULL) && (y->color == RED)){
z->getParent()->color = BLACK;
y->color = BLACK;
z->getParent()->getParent()->color = RED;
z = z->getParent()->getParent();
}else if(z == z->getPare开发者_运维技巧nt()->getRight()){
z = z->getParent();
rotateLeft(z);
}
if(z->getParent() != NULL){
z->getParent()->color = BLACK;
if(z->getParent()->getParent() != NULL){
z->getParent()->getParent()->color = RED;
rotateRight(z->getParent()->getParent());
}
}
}else if(z->getParent() == z->getParent()->getParent()->getRight()){
y = z->getParent()->getParent()->getLeft();
if((y != NULL) && (y->color == RED)){
z->getParent()->color = BLACK;
y->color = BLACK;
z->getParent()->getParent()->color = RED;
z = z->getParent()->getParent();
}else if(z == z->getParent()->getLeft()){
z = z->getParent();
rotateRight(z);
}
if(z->getParent() != NULL){
z->getParent()->color = BLACK;
if(z->getParent()->getParent() != NULL){
z->getParent()->getParent()->color = RED;
rotateLeft(z->getParent()->getParent());
}
}
}
}
getRoot()->color = BLACK;
return true;
}
/*
* Search for a node and return true if in tree
*
* @param String The string encapsulated in node to search for
* @return True if string in the tree
*/
RBTreeNode * RedBlackTree::findNode(string word){
return static_cast<RBTreeNode *>(BST::findNode(word));
}
It happens already when inserting 165. In this case the parent (160) is red as well as is uncle (125). Thus both are painted black and their parent (130) becomes red.
Now you paint its parent black and do a left rotation. This step however should not occur at this point. Instead you have to recursively proceed with the new red node (130) from the beginning.
The cause why is hidden in the lines of insertFix where you have assigned the grandparent to the new node z (z = z->getParent()->getParent();) but still consider one black uncle case because of a missing else branch.
if((y != NULL) && (y->color == RED)){
...
}else if(z == z->getParent()->getRight()){
...
}else if(z->getParent() != NULL){ // <= this else was missing
...
}
And in the second case:
if((y != NULL) && (y->color == RED)){
...
}else if(z == z->getParent()->getLeft()){
...
}else if(z->getParent() != NULL){ // <= this else also
...
}
Alright this may come across as a bit late but I think I got a simpler solution to your problem but feel free to prove me wrong if it is in correct but that is my interpretation of the algorithm description.
Your original lines:
}else if(z == z->getParent()->getRight()){
z = z->getParent();
rotateLeft(z);
}
if(z->getParent() != NULL){
z->getParent()->color = BLACK;
if(z->getParent()->getParent() != NULL){
z->getParent()->getParent()->color = RED;
rotateRight(z->getParent()->getParent());
}
}
My solution that could replace those particular lines, source: CLRS
Logic: Having an if block nested within an else is equivalent to an else if [at least that is the way I was taught about else if statements]
else
{
if ( z == z->parent->right)
{
z = z->parent;
rotateLeft(z);
}
if(z->parent != NULL)
{
if(z->parent->parent != NULL)
{
z->parent->parent->color = RED;
rotateRight(z->parent->parent);
}
}
}
parent = getParent() etc...
Repeat the same for the equivalent symmetrical case. In addition, you could have used a sentinal node nil to emulate the NULL pointer, but if your Node class has constructors then comparing against NULL is fine too unless you find a way to work around it.
加载中,请稍侯......
精彩评论