Splat | WiseTome.com

This time, we will look at yet another data structure - tree. The structure of the tree is quite different from the linked list. Going into details of tree data structure makes it look much lesser like a list and more like - well - a tree.

But it must be noted that the ‘linked’ can still remain in a description. The tree data structure is a set of linked nodes. They are linked in a specific manner. The fundamental nodes have following elements.

• Data element
• One or more reference elements

The tree structure has a root node, which contains data and contains references to child nodes. The child nodes, recursively will have data elements and reference to more nodes. This continues down to different branches, and ends when the entire bottom most nodes have their reference nodes empty. The child nodes are also called as leaf nodes.

Note that I say ‘down’ or ‘bottom’ when moving from parent node to child node, because even though the data structure is called a tree, it is traditionally drawn from top to bottom. The parent node is situated at the top of the structure, and the entire child nodes ‘grow’ down from it. Of course, this is just a representation, and the actual structure of the data and references are abstractly stored in the memory.

As stated earlier, there are one or more reference elements in the node of a tree data structure. The set of reference elements is either unordered or ordered; the tree is thus said to be an unordered tree or an ordered tree respectively. The order of the reference elements is usually numbered using natural numbers. These specific types of ordered trees have rules to specify which child node needs to be placed in a reference elements based on the data held by the child and the parent node.

When designing a tree data structure, the following operations are considered.

• Adding a new leaf node or child node (in a specific position)
• Removing a child node or leaf node
• Searching the node containing specific data
• Removing sections of the tree (pruning)
• Merging two nodes

These operations require considerable effort to be spent on designing the code based on the type of tree.

The tree data structure is used in several scenarios.

• Represent hierarchical data
  • Mathematical expressions
  • Organization structures
  • Environment and object data in a game
• Make information easy to search

The flexibility in the ways the tree can be designed has resulted in a number of different types of trees. These are used for specific purposes and are designed to be optimized for those operations.