General Trees

Implementations for General Trees

Parent Pointer

·  Each node contains a pointer to it’s parent node.

Parent’s Index / 0 / 0 / 1 / 1 / 1 / 2
Label / R / A / B / C / D / E / F
Node Index / 0 / 1 / 2 / 3 / 4 / 5 / 6

·  In this way, the entire structure of the tree is stored.

·  A tree stored in this way does not store the order of siblings.

·  This is a common way of representing tree structures inside a database such as a MySQL database.

·  Tree traversals are difficult in this kind of implementation.

·  Useful for tree structures where a ‘find root’ operation is needed.

List of Children

·  Each node contains a list of pointers to the node’s children.

·  The list can use any implementation such as a linked list or dynamic array.

·  Tree traversals are trivial in this kind of implementation.

·  This method can be combined with the parent pointer implementation to allow for both simple traversals and simple ‘find root’ operations.

A list-of-children implementation with parent pointers using a linked list structure.

Left Child / Right Sibling

·  Each node contains a pointer to it’s leftmost child and it’s right sibling.

·  Works much like a linked-list version of the list-of-children implementation. The right sibling pointers behave like a linked list where the leftmost-child pointer simply refers to the head.

·  Since each node now contains two pointers, we have essentially represented a general tree by using a binary tree.

·  A binary tree for which the root node has no right child, can be viewed as a general tree, and any binary tree can be viewed as a collection (forest) of general trees.

K-ary Trees

A K-ary tree is a tree in which no node can have more than K children.

A binary tree is an example of a K-ary tree, where K is 2.

Properties of K-ary trees

  1. The depth of a K-ary tree containing N nodes is at most N-1.
  2. The depth of a K-ary tree containing N leaves is at least .
  3. A K-ary tree of depth d has at most leaves.
  4. The number of nodes in a K-ary tree of depth d is at most .
  5. The average depth of a K-ary tree containing N nodes is .

K-ary Search Trees

An K-ary search tree is a K-ary tree with the following two properties:
A set of K-1 key values is stored at each node
All key values in a sub-tree Sn, lie between the key values Vn and Vn+1 of the parent node.
A binary search tree is an example of an K-ary search tree, where K is 2.
Typical declaration

struct KNode
{
Object keys[K-1];
KNode *subtrees[K];
};

The average depth of an K-ary search tree is Q(log N).