Tree in Data Structure

What is a tree in Data Structure? 

A tree is often used to represent a hierarchy. This is because the relationships between the items in the hierarchy suggest the branches of a botanical tree.

A tree is a non-empty collection of vertices & edges that satisfies certain requirements. A vertex is a simple object (node) that can have a name and carry other associated information. An edge is a connection between two vertices.

For example, a tree-like organization chart is often used to represent the lines of responsibility in a business as shown in Figure. The president of the company is shown at the top of the tree and the vice-presidents are indicated below her. Under the vice-presidents we find the managers and below the managers the rest of the clerks. Each clerk reports to a manager, each manager reports to a vice-president, and each vice-president reports to the president.

Tree in Data Structure

A tree is a non-empty collection of vertices & edges that satisfies certain requirements. A vertex is a simple object (node) that can have a name and carry other associated information. An edge is a connection between two vertices.

The following is a mathematical definition of a tree:

A tree T is a finite, non-empty set of nodes (or vertices) with the following properties:

1.A designated node of the set, r, is called the root of the tree; and

2.The remaining nodes are partitioned into subsets each of which is a tree.

Notice that Definition is recursive--a tree is defined in terms of itself! Fortunately, we do not have a problem with infinite recursion because every tree has a finite number of nodes and because in the base case a tree has n=0 subtrees.

It follows from Definition that the minimal tree is a tree comprised of a single root node. For example Ta in figure 6.4 is such a tree. When there is more than one node, the remaining nodes are partitioned into subtrees as in tree Tc  in figure.

Example of a binary tree

Of course, trees drawn in this fashion are upside down. Nevertheless, this is the conventional way in which tree data structures are drawn. In fact, it is understood that when we speak of ``up'' and ``down,'' we do so with respect to this pictorial representation. E.g., when we move from a root to a subtree, we will say that we are moving down the tree.

The inverted pictorial representation of trees is probably due to the way that genealogical lineal charts are drawn. A lineal chart is a family tree that shows the descendants of some person. And it is from genealogy that much of the terminology associated with tree data structures are taken.

Basic Terminology

Node – A node stands for the item of information plus the branches to other items.

Root - A Tree is a finite set of a zero or more vertices such that there is one specially designated vertex called Root and the remaining vertices are partitioned into a collection of sub-trees, each of which is also a tree.

Branch or Edge - The line from parent to a child is called a branch or an edge.

Children – The roots of the subtrees of a node X are childrens of X.

Sibling - Children to same parent are called siblings.

Parent – Node X is parent of its childrens.

Degree - The degree of a node is the number of subtrees associated with that node.

Leaf or Terminal node -  A node may not have children, such node is known as Leaf (terminal node). A node of degree zero has no subtrees

Nonterminal nodes – Nodes that are not leaf nodes.

Path - A path in a tree a list of distinct vertices in which successive vertices are connected by edges in the tree. There is exactly one path between the root and the other nodes in tree.

Ancestors – If a path exists from node p to node q, then p is an ancestor of q.

Descendent - If a path exists from node p to node q, then q is a descendant of p.

Length - A Length is a path is a number of ranches on the path, in path from m to n, m is an ancestor of n & n is descendent of m.

Depth - A Depth of any node m is the length of the path from root to m. Thus root is always at 0 depth. Sometime Depth is referred as level of the tree from root.

Height - The Height of a node m is the longest path from m to leaf. Thus all leaves are at height zero.

Forest - A set of tree is called forest.

Binary Tree - A Binary Tree is tree which either empty or consists of a root node & two disjoint trees called left & right sub-tree. 2-tree or strict binary tree, is a binary tree, which either contains no children or two disjoint children.

Multi-way tree (M-WAY) - A tree which is having a two values in its node & can have max of three branches, one values lesser than node value, second value in between of two values in node & lastly value grater than the values in node. Such type of tree is known as Multi-way tree (M-WAY).

AVL Tree - An almost height balanced tree is known as AVL tree. Each subsequent levels will be as full as possible i.e. 2 nodes at level 2. 4 nodes at level 3 and so on. In general there will be 2^L-1, where L is the level. There fore the number of nodes from level 1 to level h-1 will be (2^h-1) –1. So, total number of nodes n of the tree may range as (2^h-1) to (2^h) -1

B-Tree - A B-Tree is a balanced M-way tree. It’s also known as balanced sort tree. It finds its use in external sorting. It’s not a Binary Tree.

Next Topic: Binary Tree