我正在用 C++ 实现一棵红黑树，并且在插入后我一直在修复颜色违规。
我的左右旋转似乎工作正常，但树右分支的颜色永远无法正确修复。我想我在我的 fixViolation(Node*n) 方法中涵盖了所有情况，但也许我错了。
我还将感谢有关我的代码的所有其他建议和技巧。pastebin 链接到我的代码
我的代码：
#include "pch.h"
#include <iostream>
#include <random>
#include <string>
#include <functional>
using namespace std;
enum Color { Black, Red };
template<typename T>
class RBTree;
template <typename T>
class Node
{
friend class RBTree<T>;
T data;
Color color;
Node* parent;
Node* leftChild;
Node* rightChild;
public:
Node()
{
this->parent = nullptr;
this->leftChild = nullptr;
this->rightChild = nullptr;
color = Red;
}
void gibColor(Node<T>*x)
{
if (x->color == Black)
cout << "black";
else
cout << "red";
}
};
template <typename T>
class RBTree
{
Node<T>* root;
int size;
public:
RBTree()
{
root = nullptr;
size = 1;
}
void leftRotate(Node<T>*child, Node<T>*parent)
{
child = parent->rightChild;
parent->rightChild = child->leftChild;
if (child->leftChild != nullptr)
{
child->leftChild->parent = parent;
}
child->parent = parent->parent;
if (parent->parent == nullptr)
{
root = child;
}
else if (parent == parent->parent->leftChild)
{
parent->parent->leftChild = child;
}
else {
parent->parent->rightChild = child;
}
child->leftChild = parent;
parent->parent = child;
}
void rightRotate(Node<T>*child, Node<T>*parent)
{
child = parent->leftChild;
parent->leftChild = child->rightChild;
if (child->rightChild != nullptr)
{
child->rightChild->parent = parent;
}
child->parent = parent->parent;
if (parent->parent == nullptr)
{
root = child;
}
else if (parent == parent->parent->rightChild)
{
parent->parent->rightChild = child;
}
else
{
parent->parent->leftChild = child;
}
child->rightChild = parent;
parent->parent = child;
}
void fixViolation(Node<T>*n)
{
Node<T>*grandparent;
Node<T>*parent;
//Node<T>*uncle;
parent = n->parent;
while (parent != nullptr&& parent->color == Red)
{
Node<T>*uncle;
grandparent = n->parent->parent;
if (grandparent->leftChild == parent)
{
uncle = grandparent->rightChild;
if (uncle != nullptr&&uncle->color == Red)
{
parent->color = Black;
uncle->color = Black;
grandparent->color = Red;
n = grandparent;
parent = n->parent;
}
else
{
if (parent->rightChild == n)
{
n = parent;
leftRotate(n->parent, n);
}
parent->color = Black;
grandparent->color = Red;
rightRotate(parent, grandparent);
}
}
else
{
uncle = grandparent->leftChild;
if (uncle != nullptr&&uncle->color == Red)
{
uncle->color = Black;
parent->color = Black;
grandparent->color = Red;
n = grandparent;
parent = n->parent;
}
else
{
if (parent->leftChild == n)
{
n = parent;
rightRotate(n->parent, n);
}
parent->color = Black;
grandparent->color = Red;
leftRotate(parent, grandparent);
}
}
}
root->color = Black;
}
void addElement(T el)
{
Node<T>*n = new Node<T>();
n->data = el;
n->leftChild = nullptr;
n->rightChild = nullptr;
n->color = Red;
Node<T>*temp = this->root;
Node<T>*y = nullptr;
if (root == nullptr)
{
n->color = Black;
root = n;
}
else
{
while (temp != nullptr)
{
y = temp;
if (temp->data < n->data)
{
temp = temp->rightChild;
}
else
{
temp = temp->leftChild;
}
}
n->parent = y;
if (y->data == n->data)
{
cout << "Duplikaty won!" << endl;
return;
}
if (y->data < n->data)
{
y->rightChild = n;
size = size + 1;
}
else
{
y->leftChild = n;
size = size + 1;
}
//InsertFixUp(n);
fixViolation(n);
}
}
void print(Node<T>*x)
{
//cout << "size: " << size << endl;
if (x == nullptr)
{
return;
}
if (x->parent == nullptr)
{
cout << "(" << x->data << ")";
cout << "[" << "kolor:";
x->gibColor(x);
cout << ", parent: NULL," << " l.child: ";
if (x->leftChild == nullptr)
{
cout << "NIL";
}
else
cout << x->leftChild->data;
cout << ", r.child: ";
if (x->rightChild == nullptr)
{
cout << "NIL";
}
else
cout << x->rightChild->data;
cout << "]";
cout << "-root " << endl;
//rodzic, l.dziecko, p.dziecko
}
else if (x->parent->leftChild == x)
{
//int c = x->gibColor(x);
cout << "(" << x->data << ")";
cout << "[" << "kolor:";
x->gibColor(x);
cout << ", parent: " << x->parent->data << ", l.child: ";
if (x->leftChild == nullptr)
{
cout << "NIL";
}
else
cout << x->leftChild->data;
cout << ", r.child: ";
if (x->rightChild == nullptr)
{
cout << "NIL" << "]" << endl;
}
else
cout << x->rightChild->data << "]" << endl;
}
else
{
cout << "(" << x->data << ")";
cout << "[" << "kolor:";
x->gibColor(x);
cout << ", parent: " << x->parent->data << ", l.child: ";
if (x->leftChild == nullptr)
{
cout << "NIL";
}
else
cout << x->leftChild->data;
cout << ", r.child: ";
if (x->rightChild == nullptr)
{
cout << "NIL" << "]" << endl;;
}
else
cout << x->rightChild->data << "]" << endl;
}
print(x->leftChild);
print(x->rightChild);
}
void printTree()
{
if (root == nullptr)
{
cout << "Empty tree!" << endl;
}
else
print(root);
}
};
int randomInt()
{
uniform_int_distribution<int> rozklad{ 0, 11000000 };
default_random_engine generator{ 11 };
function<int()> los{ bind(rozklad, generator) };
int l = los();
return l;
}
int main()
{
RBTree<int>* d1 = new RBTree<int>();
d1->addElement(55);
d1->addElement(69);
d1->addElement(62);
d1->addElement(71);
d1->addElement(70);
d1->addElement(14);
d1->printTree();
}