Я пытался создать красное черное дерево, которое реализует только метод вставки, поиска и обхода по порядку, чтобы я мог сравнить его с аналогичным деревом AVL, которое я создал ранее. Я использовал все алгоритмы, которые можно найти в тексте Кормена: Введение в алгоритмы, но по некоторым причинам я не могу заставить его работать правильно.
Например, когда я вставляю a, b, затем c и пытаюсь выполнить обход в порядке, я теряю c. Я перебрал алгоритмы в тексте около 10 раз, чтобы убедиться, что у меня все в порядке, и я не могу найти никаких ошибок.
Может кто-нибудь сказать мне, правильно ли я выполняю метод insertFix(), а также повороты.
Ниже приведен мой заголовочный файл, чтобы дать вам представление о том, как я настраивал узлы:
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
};
А вот мой insertFix() метод, который запускается после обычной вставки, которую вы найдете в любом обычном бинарном дереве поиска:
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;
}
Ниже приведены два моих метода вращения: один - правое вращение (RR), а другой - левое вращение (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;
}
Я знаю, что это большой код, который нужно просмотреть, но я со своей стороны пытаюсь выяснить, что я делаю неправильно. У меня такое чувство, что я путаю указатели где-то в одном из поворотов, но я не могу понять, где. Любая помощь будет принята с благодарностью!