Red Black Tree insertion, I think I might have the rotations messed up
I have been trying to create a red black tree that only implements an insert, search, and in-order traversal method so that I can compare it to a similar AVL tree I made previously. I have used all of the algorithms that are found in the Cormen text: Introduction to Algorithms, but for some reason I can't seem to get it to work correctly.
For example, when I insert a, b, then c and try to do an in-order traversal, I am losing c. I have gone over the algorithms in the text about 10 times to make sure I have everything right and I can't seem to find any mistakes.
Can anyone tell me if I am doing the insertFix()
method correctly, as well as the rotations.
Below is my header file to give you an idea of how I set up the nodes:
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
};
And here is my insertFix()
method, which is ran after a normal insertion that you would find in any ordinary binary search tree:
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
开发者_如何学Python {
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;
}
Below are my two rotation methods, one is a Right Rotation (RR), and the other is a Left Rotation (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;
}
I know this is a lot of code to look over, but I am at my wits end trying to find out what I am doing wrong. I have a feeling I am messing up the pointers somewhere in one of the rotations but I can't figure out where. Any help would be really appreciated!
In the insertFix() function, in this section:
else
{
if( z == z->parent->RCH)
{
z = z->parent;
RBT::LR(z);
}
z->parent->isRed = false;
z->parent->parent->isRed = true;
RBT::RR(z);
}
you should change
RBT::RR(z);
to
RBT::RR(z->parent->parent);
Same as the left rotate case in the same function:
RBT::LR(z);
to
RBT::LR(z->parent->parent);
精彩评论