StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PORed Black Tree insertion, I think I might have the rotations messed up
primarykey
Id
5455964
data
AcceptedAnswerId
5456135
AnswerCount
1
ClosedDate
CommentCount
2
CommunityOwnedDate
CreationDate
2011-03-28T07:41:33.727
FavoriteCount
0
LastActivityDate
2011-03-28T08:00:47.527
LastEditDate
2011-03-28T07:46:42.087
LastEditorUserId
622647
OwnerUserId
679804
ParentId
0
PostTypeId
1
Score
1
ViewCount
5523
LastEditorDisplayName
text
Body
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 <code>insertFix()</code> method correctly, as well as the rotations. Below is my header file to give you an idea of how I set up the nodes: <pre><code>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 }; </code></pre> And here is my <code>insertFix()</code> method, which is ran after a normal insertion that you would find in any ordinary binary search tree: <pre><code>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; } </code></pre> Below are my two rotation methods, one is a Right Rotation (RR), and the other is a Left Rotation (LR): <pre><code>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; } </code></pre> 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!
Tags
<c++><algorithm><tree><red-black-tree>
Title
Red Black Tree insertion, I think I might have the rotations messed up
singulars
PostAcceptedAnswerId
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. USquasiverse
UserOwnerUserId
1. USRyanE
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
 singulars
 PostTypePostTypeId
 PTAnswer
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PORed Black Tree insertion, I think I might have the rotations messed up
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId
1. COAfter this "normal insertion", do you set the children to nil , colour the node red and then call insertFix()?
 singulars
 PostPostId
 PORed Black Tree insertion, I think I might have the rotations messed up
 UserUserId
 USquasiverse
2. CO@quasiverse Yes those are the last things I do before I call insertFix()
 singulars
 PostPostId
 PORed Black Tree insertion, I think I might have the rotations messed up
 UserUserId
 USRyanE

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.