0
votes

I'm currently implementing a red-black tree in C++. One issue I've run into is that, originally, my Node class's constructor would initialize each Node object like so:

(The Node class attributes)

    Tree_node *left;
    Tree_node *right;
    Tree_node *parent;
    static Tree_node *node_to_delete;
    static Tree_node *successor;
    static bool is_balanced_tree;
    static int black_depth_count;
    int val;
    int color;
    int visited;
    int visited_deletion;
};

(Node class constructor)

Tree_node::Tree_node(int v){
    val=v;
    left=NULL;
    right=NULL;
    parent=NULL;
    color=1;
    visited=0;
    visited_deletion=0;
}

Of course, I realized eventually that instantiating the left/right children to be NULL by default leads to my tree not truly having black external nodes but instead simply null values. This causes issues in the deletion cases where the right child of the node to replace our original node is an external node (and therefore considered simply NULL in my code), and I therefore cannot access any of the class methods to return the parent of our current node, or sibling, as the node itself isn't even a node, it's just NULL.

So what I'm trying to do now is built a subclass, Nil_Black_Node, which will be the external nodes of the tree, not just a NULL value. The difference is that this constructor by default initializes the Node's color to be 0(black) and not 1(red) like the Tree_node non-external nodes' constructors do. My Nil Black Node is declared as such (it's a subclass the Tree_node class)

class Nil_Black_Node:public Tree_node{
public:
    Nil_Black_Node();
};

And it's constructor simply sets it's color value to be 0:

Nil_Black_Node::Nil_Black_Node():Tree_node(0){
    color=0;
}

But the issue is now that my Nil Black Node is initialized to have a value of 0. I do not want my Nil Black Node to have any value- really all that matters in the context of these external nodes is that they have a parent pointer to the Tree_node that they are children of, and the color 0. Allowing them to have a value would mess up my insertion methods since my method would traverse the tree and see that the nil black nodes have a value 0 and attempt to insert nodes as children of it like it was any other node. Is there a way to get around them having any value whatsoever? Like some kind of null placeholder?

1

1 Answers

1
votes

Of course, I realized eventually that instantiating the left/right children to be NULL by default leads to my tree not truly having black external nodes but instead simply null values.

It doesn't need to be a problem that the leaves aren't "true nodes". We can simply decide that null pointers are nil black leaves and write our algorithms accordingly.

Alternative representation is to use a sentinel node which allows you to set the blackness on an actual object same way as with branch nodes. Whether you choose to use a sentinel or null affects how you write the algorithms, but neither is a problem that would prevent those algorithms from being written.

So what I'm trying to do now is built a subclass,

You don't necessarily need a derived class to represent a sentinel node. You could simply use an instance of Tree_node.

Allowing them to have a value would mess up my insertion methods since my method would traverse the tree and see that the nil black nodes have a value 0

How would not having any value at all solve this problem? I don't see how it could. What happens when your insertion methods attempt to get the value to see what it is when there is no value? The actual solution is to fix the insertion methods to check whether the node is a leaf node or not, and behave accordingly.

That way it won't matter whether the sentinel has a value, and in the case it has, it won't matter what that value happens to be. You simply never read it. Having a superfluous value can however become a problem when the tree is templetised to support non-trivial types in which case we may need to avoid creating instances.


Is there a way to get around them having any value whatsoever?

Keeping in mind what I've written above that we don't necessarily need to care about this, and also considering that inheritance is not necessarily needed either, here is an inheritance based way to avoid storing a value in the sentinel:

struct Base_Node {
    // no value
    ...

    virtual ~Base_Node() = default;
};

struct Branch_Node : Base_Node {
    int value; // has value
};

struct Nil_Black_Node : Base_Node {
    // no value
} sentinel;