tree data structure (with all its types and operations)- TechAlmirah

The tree is a non-linear data structure. This structure is mainly used to represent data containing a hierarchal relationship between elements (For example) record, family relationship, and table contents. The earth structure is a good example of a tree.

If we want to represent the structure graphically, we will have the following diagram.

All data elements are in trees are called nodes. The node, which does not have its preceding nodes, is called ROOT node and it is considered at level number one. If a tree has ROOT node N and S1 and S2 left and right successor then N is called parent or father and S1 is called left child and S2 is called the right child. S1 and S2 are called brothers or siblings. The node on the same level is called “NODE OF THE SAME GENERATION”.

Table of Contents

Basic Terminologies:

The root is a specially designed node (or data items) in a tree. It is the first node in the hierarchical arrangement of the data items. Each data item in a tree is called a node. It specifies the data information and links (branches) to other data items.
A node is a structure that may contain a value, a condition, or represent a separate data structure (which could be a tree of its own). Each node in a tree has zero or more child nodes, which are below it in the tree (by convention, trees are drawn growing downwards). A node that has a child is called the child’s parent node (or ancestor node, or superior). A node has at most one parent
An internal node (also known as an inner node or branch node) is any node of a tree that has child nodes.
Similarly, an external node (also known as an outer node, leaf node, or terminal node) is any node that does not have child nodes.
The topmost node in a tree is called the root node. Being the topmost node, the root node will not have a parent. It is the node at which operations on the tree commonly begin (although some algorithms begin with the leaf nodes and work up ending at the root). All other nodes can be reached from it by following edges or links. (In the formal definition, each such path is also unique). In some trees, such as heaps, the root node has special properties. Every node in a tree can be seen as the root node of the subtree rooted at that node. A free tree is a tree that is not rooted.
The height of a node is the length of the longest downward path to a leaf from that node. The height of the root is the height of the tree.
The depth of a node is the length of the path to its root (i.e., its root path). This is commonly needed in the manipulation of the various self-balancing trees, AVL Trees in particular. Conventionally, the value −1 corresponds to a subtree with no nodes, whereas zero corresponds to a subtree with one node.
A subtree of a tree T is a tree consisting of a node in T and all of its descendants in T. (This is different from the formal definition of subtree used in graph theory.) The subtree corresponding to the root node is the entire tree; the subtree corresponding to any other node is called a proper subtree (in analogy to the term proper subset).

Binary Tree Data Structure:

A tree is said to be a binary tree if it has at most two nodes. In simple words, we say that a binary tree must have zero, one, or two nodes. A binary tree is a very important tree structure.

Complete Binary Tree:

A tree is said to be a complete binary tree if it has exactly two nodes except the last node.

Similar Binary Tree:

Two binary trees T1 and T2 are said to be a similar binary trees if they have the same structure. In simple words, we say that if two trees have the same shape then they are called similar trees.

Copy of Tree Data Structure:

Two binary tree T1 and T2 are said to be copy of each other if they have same structure and same contents.

Binary Tree Representation Using Linked List Representation:

The most popular and practical way of representing a binary tree is using a linked list (or pointers). In the linked list, every element is represented as a node. A node consists of three fields such as :

Left Child (Lchild)
Information of the Node (Info)
Right Child (Rchild)

struct Tree
{
     int information;
     struct Tree *Lchild;
     struct Tree *Rchild;
}

Operation On Binary Tree

Create an empty binary tree
Traversing a binary tree
Inserting a Binary Tree
Deleting a Node
Searching for a Node
Copying the mirror image of a tree
Determine the total no: of Nodes
Determine the total no: leaf Nodes
Determine the total no: non-leaf Nodes
Find the smallest element in a Node
Finding the largest element
Find the Height of the tree
Finding the Father/Left Child/Right Child/Brother of an arbitrary node

Traversing of Binary tree data structure:

A tree can be traversed using the following three methods

Pre Order Traversing: –
- Visit the ROOT node.
- Traverse the LEFT subtree in pre-order.
- Traverse the RIGHT subtree in pre-order.
In Order Traversing: –
- Traverse the LEFT subtree in pre-order.
- Visit the ROOT node.
- Traverse the RIGHT subtree in pre-order.
Post Order Traversing: –
- Traverse the LEFT subtree in pre-order.
- Traverse the RIGHT subtree in pre-order.
- Visit the ROOT node.

Example: If we take the following expression.

[a +(b-c)] * [d –c) / (f + g –h)]

The following tree represent the above expression:

Pre order traversing:

* + a - b c / - d e - + f g h

Post Order traversing:

a b c - + d e - f g + h - / *

Threaded Binary Tree

Traversing a binary tree is a common operation and it would be helpful to find a more efficient method for implementing the traversal. Moreover, half of the entries in the Lchild and Rchild field will contain an NULL pointer. These fields may be used more efficiently by replacing the NULL entries with special pointers which point to nodes higher in the tree. Such types of special pointers are called threads and binary trees with such pointers are called threaded binary trees.

Expression Tree Data structure

An ordered tree may be used to represent a general expression, which is called an expression tree. Nodes in one expression tree contain operators and operands.

Balanced Binary Tree

A balanced binary tree is one in which the largest path through the left subtree is the same length as the largest path of the right subtree, i.e., from root to leaf. Searching time is very less in balanced binary trees compared to unbalanced binary trees. i.e., balanced trees are used to maximize the efficiency of the operations on the tree.

There are two types of balanced trees :

Height Balanced Trees
Weight Balanced Trees

1. Height Balanced Trees

In height-balanced trees balancing the height is the important factor. There are two main approaches, which may be used to balance (or decrease) the depth of a binary tree :

Insert a number of elements into a binary tree in the usual way, using the algorithm given in the previous section (i.e., Binary search Tree insertion). After inserting the elements, copy the tree into another binary tree in such a way that the tree is balanced. This method is efficient if the data(s) are continually added to the tree.
Another popular algorithm for constructing a height-balanced binary tree is the AVL tree, which is discussed in the next section.

2. Weight Balanced Trees

A weight-balanced tree is a balanced binary tree in which an additional weight field is also there. The nodes of a weight-balanced tree contain four fields:

Data Element
Left Pointer
Right Pointer
A probability or weight field

The data element left and right pointer fields are save as that in any other tree node. The probability field is a specially added field for a weight-balanced tree. This field holds the probability of the node being accessed again, that is the number of times the node has been previously searched for.

AVL Tree Data structure:

This algorithm was developed in 1962 by two Russian Mathematicians, G.M. Adel’s son Vel’sky and E.M. Landis; here the tree is called AVL Tree. An AVL tree is a binary tree in which the left and right subtree of any node may differ in height by at most 1, and in which both the subtrees are themselves AVL Trees.

Each node in the AVL Tree possesses any one of the following properties:

A node is called left heavy if the largest path in its left subtree is one level larger than the largest path of its right subtree.
A node is called right heavy if the largest path in its right subtree is one level larger than the largest path of its left subtree.
The node is called balanced if the largest paths in both the right and left subtrees are equal.

Posts

tree data structure