我对红黑树还不熟悉,我遇到了一些问题。旋转和插入方法看起来都是正确的。但是,当我输入以下数字时:100 45 34 55 74 50 130 120 125 160 165 150
程序输出如下。最右边的数字是节点中的数字,然后是颜色,再然后是节点的父节点。
34 [黑] (45)
45 [红] (74)
50 [红] (55)
55 [黑] (45)
74 [红] (120)
100 [黑] (74)
120 [黑]
125 [黑] (130)
130 [红] (120)
150 [红] (160)
160 [黑] (130)
165 [红] (160)
这里有两个问题:节点45和74都为红色,但这违反了红黑树性质:红色父节点必须有两个黑色子节点。如果您能帮忙解决这个问题,将不胜感激。
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 这个类的BST :: insert(rbnode)函数很好用,因为在使用其他函数之前已经完成了该函数中的差异。
#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->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());
}
}
}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));
}