如何在 C++ 中的红黑树中创建哨兵 NIL 对象？

Question

我想实现一棵红黑树，但我在基本步骤上遇到困难。我习惯于只使用结构，但现在我想让它变得干净并使用类。

我想创建一个特殊的对象 NIL（树中的一个成员？）（NIL 是黑色的，所有节点都引用这个单一对象，在 CLRS 中它说 "T.NIL is an object with the same attributes as an ordinary node, its color is black and its left, right and p attributes can take arbitrary values"，"we use one sentinel T.nil to represent all the NILs")

如何将左、右、p 设置为 NIL？ NIL 是否应该先创建一个单独的单例 class 然后在树定义中使用？当我分配给 T.NIL（评论）

时，我现在遇到错误

#include <iostream>
enum color_t {red, black};

class Tree; // declare first
Tree *T;

class Node { // could be a struct!
public:
    int data;
    color_t color = red;
    Node *left;
    Node *right;
    Node *parent;
    Node() { // default constructor
        left = T->NIL; // ERROR: Member access into incomplete type
        right = T->NIL; // ERROR: Member access into incomplete type
        parent = T->NIL;  // ERROR: Member access into incomplete type
    }
    Node(int d, color_t c) { // if data and color are known
        Node();
        data = d;
        color = c;
    }
};

class Tree {
public:
    Node *root;
    Node *NIL;
    Tree();
    void insert(int d);
    void leftRotate(Node *x);
};

Tree::Tree() {
    NIL = new Node();
    NIL->color = black;
    root = NIL;
}

Answer 1

您需要在代码中将 Node::Node() 的正文进一步向下移动； class Tree 之后定义的任何地方（在你拥有它的时候，Tree 只被声明）。

如何在 C++ 中的红黑树中创建哨兵 NIL 对象？

How to create the sentinel NIL object in a red black tree in C++?

c++

red-black-tree