Cos Cos - 2 years ago 62
C++ Question

What is the correct structure for a node in any BST Tree

What is the correct way based on the theory to create a Node for a Binary Tree?
For example:

struct Node
{
int data;
Node *left;
Node *right;
};


The problem I'm currently facing is that I have 2 different answers from several sources (books,website,online lectures.. etc).

From "Introduction to Algorithms",edition 3, p 286,287 : "In addition to a key and satellite data, each node contains attributes left, right, and p that point to the nodes corresponding to its left child,its right child, and its parent, respectively."

Which means something like this:

struct Node
{
int data;
Node *parent;
Node *left;
Node *right;
};


On the other hand, I found several links which DO NOT follow this design such as:

http://algs4.cs.princeton.edu/32bst/

http://math.hws.edu/eck/cs225/s03/binary_trees/

http://www.cprogramming.com/tutorial/lesson18.html

These implementations DO NOT keep a link to the parent and from some online lectures it is said that Trees do NOT traverse backwards (aka. can't see the parent) which counters the notion from the book!

In RedBlack trees for instances you NEED to see the grandparent and uncle of that node to determine whether to re-colour and/or rotate to rebalance the tree.
In AVL trees you don't since the focus is on the height of sub-trees.
Quad Trees and Octrees are the same that you don't need the parent.

Questions:

Can someone please answer me this and with valid sources explain which is the CORRECT way to design a node for a Binary Tree or for Any Tree (B-Trees,..etc)?

Also what is the rule with Traversing Backwards? I know of Pre-order, In-order, Post-order, Breadth-First, Depth-First(Pre-order) and other AI Heuristic algorithms for traversals.

Is it true that you are NOT allowed to move backwards in a tree ie from child to parent? If so, then why does the book suggest a link to parent node?

Answer Source

The fundamental Binary Tree (foundation) requires child pointers:

struct binary_tree_node
{
  binary_tree_node * left_child;
  binary_tree_node * right_child;
};

There are many modifications that can be made to the foundation that help facilitate searching or storage.

These can include (but are not limited to):

  • parent pointer
  • array of child pointers
  • "color" indicator
  • specialized leaf nodes -- no child links

The amenities depend on the usage of the data structure. For example, an array of child nodes may help speed up I/O access, where reading a "page" node is as efficient as reading a single node (See B-Tree). The "color" indicator may help with the decision for balancing. The specialized "leaf" nodes reduce the amount of memory occupied by the tree.

As for traversal, a tree can be traversed in any method. There are no rules preventing a traversal from child to parent. Some traversals may include sibling to sibling.

Some books or websites may pick nits about a traditional or fundamental "binary tree" data structure. I find that restrictions get in the way.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download