In a tree structure, how to name the tree, the nodes, the leaves?

Question

Hello, this question is about best practices. I'm implementing a 3D interval Kd-Tree and, because of the recursive structure of the tree I would be tempted to create a unique class, KdTree to represent the tree itself, the nodes and the leaves.

However: elements are contained only at leaves, some general tree parameters (such as the maximum number of elements before splitting the space) are meant to be the same for all the tree and finally splitting planes have no sense at all in leaves.

That said: should I make up three classes (KdTree, KdNode, KdLeaf) or just pretend that each node or leaf is in fact a Kd-Tree (which, in fact, is precisely the case) and duplicate data?

Tommaso

Answer 1

Create and use the classes KdNode and KdLeaf privately within the context of KdTree. This will make your life easier, and hide the complexity from other parts of the program

Answer 2

It seems the lead and tree are nodes that are simply at the beginning of the end of the "branch".

In these cases, I just name them "nodes" and when parsing through them, I would refer to them as KdParentNode, KdNode and KdChildNode. If a node does not have a parent, It's the tree (root) node, and if it does not have children, it's a leaf node.

Answer 3

I would say there is no need for a Tree class. The top element is a node like all the rest.

To differentiate the leaves and the branch nodes, I'd go for

 namespace KdTree
 { 
       abstract class Node 
       {
             virtual EnumLeafNodes(LeafNodeCallback callback);
             virtual GetLeafCount();

       }

       class Leaf : Node 
       {
             // implement virtuals by returning/counting leaf values
       }

       class Branch : Node
       {
             // implement virtuals by delegating to child nodes

             // direct children:
             Node[] children;  
       }   
 }

Note that this is very much pseudocode (C#-ish). The idea behind this design is that you use virtual functions to differentiate the behavior between branches and leaf nodes, and the branches can delegate to their child nodes. This is a trivial example on what is know as the Visitor pattern.