Tree Data Structure

Types of Data Structure

There are two types of data structures; linear and nonlinear. In linear data structure, elements will be attached linearly, like in the case of stack, linked lists, queue etc.  In nonlinear data structure elements will not be arranged in sequential order, as seen in trees or graphs, so it is more difficult to traverse.

Definition

A tree is a collection of nodes. These nodes are arranged in a hierarchical structure and  linked to each other by edges (not making a cycle). Trees are preferred when we want to reduce the cost of operations and memory use.

Figure 1

Types of Trees

The different types of trees in data structure based on their properties : general tree, binary tree, binary search tree, AVL tree, red-black tree, splay tree, and B-tree.

General tree:

In this tree its node can have 0 to N number of nodes, in which every node has no degree restrictions. Mainly, a general tree does not have ordered nodes. Hence its subtree will also be unordered.

Figure 2

Binary tree:

It is a recursive tree in which each node can have two child nodes at most.

Properties of binary trees are:

The number of the total nodes on each level will be double the nodes present at the previous level. The last level will have the number of nodes present on all levels plus one.

Binary search tree:

Is a node-based binary tree but with different properties like:

1. Left subtree will contain the nodes with the values lesser than the value of its root node.

2. Right subtree will contain nodes with values greater than the value of its root.

3. The left and right subtrees should be binary trees in themselves.

Figure 3

AVL tree:

It satisfies both binary tree and binary search tree properties. This tree is a self-balancing tree which was invented by the mathematician Adelson Velsky Lindas.  The self-balancing property says that the difference between the height of the left and right subtree should not be more than one and it is implemented on all the nodes.

Figure 4

Properties of Trees and Terminologies

Node

Basic unit containing value and nodes pointing to left and right subtree.

1
2
3
4
5
6
7
Code: class Node {

  int data;

  Node left, right; //pointer to left and right subtree

}

Root

Topmost node in a tree; it is the ancestor of all the nodes in a tree.

Child

Any node which is connected to another node when moving away from the root is called a child of its ancestor.

Level

Total count of edges between current node and root of a tree plus one.

Leaf

Any node which doesn’t have any child.

Edge

Link between the two different nodes which does not lead to a cycle.

Height

The longest path which can be drawn between root node and leaf node.

Breadth

Total number of leaf nodes present in a tree.

Degree

The count of child nodes that exist for a node is the degree of a  node.

Tree Uses in the Real World

Trees are used widely in databases to implement indexing, to implement dictionaries, for quick pattern searching, and finding the shortest distance. Binary trees are used for fast searching and sorting data.