我是红黑树的新手，我不知道这个问题是从哪里来的。旋转和插入方法看起来是正确的。但是，当我输入数字时
100
45
34
55
74
50
130
120
125
160
165
150
我从程序中得到以下输出。最右边的数字是节点中的数字，然后是颜色，然后是节点的父节点。根节点没有列出父节点。节点 45 和 74 都是红色的，这两个节点不能都是红色的，因为这违反了红色黑树属性:红色父节点总是有两个黑色子节点。在这件事上的任何帮助都会很棒。
34 [黑色] (45)
45 [红色] (74)
50 [红色] (55)
55 [黑色] (45)
74 [红色] (120)
100 [黑色] (74)
120 [黑色]
125 [黑色] (130)
130 [红色] (120)
150 [红色] (160)
160 [黑色] (130)
165 [红色] (160)
红黑树.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
红黑树.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));
}
最佳答案
插入 165 时已经发生了。在这种情况下，父项 (160) 和叔叔 (125) 都是红色的。因此两者都被涂成黑色，而它们的父级 (130) 变成红色。
现在您将其父对象涂成黑色并向左旋转。然而，这一步不应在此时发生。相反，您必须从头开始递归处理新的红色节点 (130)。
原因隐藏在 insertFix 行中，您已将祖 parent 分配给新节点 z (z = z->getParent() ->getParent();) 但由于缺少 else 分支，仍然考虑一个黑人叔叔案例。
if((y != NULL) && (y->color == RED)){
...
}else if(z == z->getParent()->getRight()){
...
}else if(z->getParent() != NULL){ // <= this else was missing
...
}
在第二种情况下:
if((y != NULL) && (y->color == RED)){
...
}else if(z == z->getParent()->getLeft()){
...
}else if(z->getParent() != NULL){ // <= this else also
...
}
关于c++ - 红黑树插入问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5682549/