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?