2-3-4 trees node members

Question

I would really appreciate a clarification in 2-3-4 trees... Suppose you have a tree defined like this:

class N234{  //node class
    public:
        int firstData, secondData, thirdData;
        N234 *firstChild,*secondChild,*thirdChild,*fourthChild,*parent;
};

class T234{ //tree with root node
public:
T234(){
this->root->parent=NULL;
this->root->firstChild=NULL;
this->root->secondChild=NULL;
this->root->thirdChild=NULL;
this->root->fourthChild=NULL;
}
private:
N234* root;
};

My question actually is how do i know whether a node is full (has all three values in it) when its variables(firstData, secondData, thirdData) have already some value in them as?

for example:
root: |4| left child of root:|1,2|
right child of root |7,9|

Here root has one value (4). My question is how do we know that it actually has one value, since all of his other variables(secondData, thirdData) have some value in them (even if it is trash).. Thanks in advance!

Answer 1

If we had only internal nodes to worry about, the simplest way would be to look at the child pointers:

If thirdChild is null, then the node is a 2-node, so it has only one meaningful value (firstData), and the rest (secondData, thirdData) contain junk.

If thirdChild is not null, but fourthChild is null, then it's a 3-node; the first two data variables contain meaningful values.

If all child pointers are non-null, then it's a 4-node.

The only problem with this approach is that it requires that a pointer be null iff it is actually invalid (e.g. the thirdChild of a 2-node) and not just unused. But not all valid child pointers will be in use (e.g. the firstChild of a 2-node that is a leaf).

So one solution is to create a node which all invalid pointers point to, and which is not used in any other way. In a sense, it acts as a second NULL, distinct from the ordinary one.

Note that it doesn't matter which kind of pointer (invalid, or valid-but-unused) points to NULL and which points to the phony node. (Also note that you could use any non-NULL value for the "second NULL", it wouldn't have to be the address of an actual node, but you'd have to be certain that it could never become the address of an actual node, and anyway it would make me nervous to use such an approach.)