Tree- Discrete Structures

 

TREE

Introduction-Properties-Special Classes of Trees-Definition of Spanning Tree-Minimal Spanning tree.

INTRODUCTION: TREE

Tree is a connected graph without any circuits (cycle/loop/parallel edge) is called tree, which represents hierarchical relationship between individual data (item/nodes).

In a tree, nodes are organized in the hierarchical way such that

There is specially designated node called the root, at the beginning of the structure except when the tree is empty.

Lines connecting the nodes are called branches and every node except the root is joined to just one node at the next higher level (its parents).

Nodes that have no children are called leaf nodes or terminal nodes.

 

BASIC TERMINOLOGIES

The important terms related to tree data structure are-

 

Root

The first node from where the tree originates is called as a root node.

In any tree, there must be only one root node.

We can never have multiple root nodes in a tree data structure.

Example

 

Here, node A is the only root node.

 

Edge

The connecting link between any two nodes is called as an edge.

In a tree with n number of nodes, there are exactly (n-1) number of edges.

Example

 

 

Parent

The node which has a branch from it to any other node is called as a parent node.

In other words, the node which has one or more children is called as a parent node.

In a tree, a parent node can have any number of child nodes.

Example

 

Here,

Node A is the parent of nodes B and C

Node B is the parent of nodes D, E and F

Node C is the parent of nodes G and H

Node E is the parent of nodes I and J

Node G is the parent of node K

 

Child

The node which is a descendant of some node is called as a child node.

All the nodes except root node are child nodes.

Example

 

Here,

Nodes B and C are the children of node A

Nodes D, E and F are the children of node B

Nodes G and H are the children of node C

Nodes I and J are the children of node E

Node K is the child of node G

 

Siblings

Nodes which belong to the same parent are called as siblings.

In other words, nodes with the same parent are sibling nodes.

Example

 

 Here,

Nodes B and C are siblings

Nodes D, E and F are siblings

Nodes G and H are siblings

Nodes I and J are siblings

 

Degree

Degree of a node is the total number of children of that node.

Degree of a tree is the highest degree of a node among all the nodes in the tree.

Example

 

Here,

Degree of node A = 2

Degree of node B = 3

Degree of node C = 2

Degree of node D = 0

Degree of node E = 2

Degree of node F = 0

Degree of node G = 1

Degree of node H = 0

Degree of node I = 0

Degree of node J = 0

Degree of node K = 0

 

Internal Node

The node which has at least one child is called as an internal node.

Internal nodes are also called as non-terminal nodes.

Every non-leaf node is an internal node.

Example

 

 Here, nodes A, B, C, E and G are internal nodes.

 

Leaf Node

The node which does not have any child is called as a leaf node.

Leaf nodes are also called as external nodes or terminal nodes.

Example

 

Here, nodes D, I, J, F, K and H are leaf nodes.

 

Level

In a tree, each step from top to bottom is called as level of a tree.

The level count starts with 0 and increments by 1 at each level or step.

Example

 

 

Height

Total number of edges that lies on the longest path from any leaf node to a particular node is called as height of that node.  Height of a tree is the height of root node.

Height of all leaf nodes = 0

Example

                                    

Lmax+1=1+1=2=Height(B)=2

Here,

Height of node A = 3

Height of node B = 2

Height of node C = 2

Height of node D = 0

Height of node E = 1

Height of node F = 0

Height of node G = 1

Height of node H = 0

Height of node I = 0

Height of node J = 0

Height of node K = 0

 

Depth

Total number of edges from root node to a particular node is called as depth of that node.

Depth of a tree is the total number of edges from root node to a leaf node in the longest path.

Depth of the root node = 0

The terms “level” and “depth” are used interchangeably.

Example

 

 

Here,

Depth of node A = 0

Depth of node B = 1

Depth of node C = 1

Depth of node D = 2

Depth of node E = 2

Depth of node F = 2

Depth of node G = 2

Depth of node H = 2

Depth of node I = 3

Depth of node J = 3

Depth of node K = 3

 

Subtree

In a tree, each child from a node forms a subtree recursively.

Every child node forms a subtree on its parent node.

Example

 

Forest

A forest is a set of disjoint trees. 

Example

 

TREE PROPERTIES

The important properties of tree data structure are

1.There is one and only one path between every pair of vertices in a tree.

2.A tree with n nodes/vertices has exactly (n-1) edges.

3.A graph is a tree if and only if it is minimally connected.

4. The minimum number of nodes possible in a binary tree of height h is h+1

Example

To construct a binary tree of height = 4, we need at least 4 + 1 = 5 nodes.

 

 

5.The maximum number of nodes possible in a binary tree of height h is 2h-1

Height h = lmax+1

Example

Maximum number of nodes in a binary tree of height 3

= 23+1 – 1

= 16 – 1

= 15 nodes

Thus, in a binary tree of height = 3, maximum number of nodes that can be inserted = 15.

 6.In any binary tree, the maximum number of nodes at any level l is 2l, where l>0.

Level 

Node

0

20=1

 

1

21=2

 

2

22=4

 

3

23=8

 

Example

Maximum number of nodes at level-2 in a binary tree

= 22 = 4

Thus, in a binary tree, maximum number of nodes that can be present at level-2 = 4.

 


TYPES OF TREES

Binary Tree

A binary tree (T) is a finite set of nodes each node have a maximum of two children.

1. T is tree that has no nodes is called empty binary tree.

2. T contains a specially designated node called the root of T and the remaining nodes of T has disjoint binary trees T1 and T2 which is called the subtrees of the root T.

Below mentioned trees are special kind / classes of binary trees.

Skewed Tree

The minimum number of nodes possible at every level is only one when every parent has one child.

Such kind of trees called Skew binary trees.

 

Complete Binary tree

A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Full binary tree

A binary tree is said to be full binary tree, if it contains maximum possible number of nodes in all level

           

Expression Tree

Binary tree can be used to represent algebraic expression which shows the evaluation of expressions.

To represent expressions in three different ways,

1.Prefix

2.Infix

3.Postfix

Prefix:

An expression is called the prefix expression if the operator appears in the expression before the operands.

The form of prefix expression is (operator operand1 operand2).

Example : *+AB-CD (Infix : (A+B) * (C-D) )

 

Infix: An expression in which the operation placed between its operation is called the infix notation.

The form of infix expression is (operand1 operator operand2).

Example: Infix : (A+B) * (C-D)

 

Postfix: An expression is called the postfix expression if the operator appears in the expression after the operands.

The form of postfix expression is (operand1 operand2 operator).

Example : AB+CD-* (Infix : (A+B * (C-D) )

 

TREE TRAVERSAL

1.Bredth First Search

     Level order

2.Depth First Search

     Preorder

     Inorder

     Postorder


 

1.Bredth First Search-Level Order

To traverse from the Root node and process the node in each level from Level from Left to Right

         A,B,C,D,E,F,G

2.Depth First Search

     Preorder: ( Root, Left, Right)   - A, B, D, E, C, F, G                      

     Inorder: ( Left, Root, Right)     - D, B, E, A, F, C, G


     Postorder (Left, Right, Root)   - D, E, B, F, G, C, A

SPANNING TREE

If the subgraph T of a connected graph G is a tree containing all the vertices of G then T is called a spanning tree of G.

Example

Let us consider the graph G has 3 vertices, any spanning tree of G will also have 4 vertices and hence, 2 edges.

Since G has 3 edges, removal of 1 edge may result in spanning tree. 

This can be done in 3C1=3!/(1!(3-1)!)= 3!/(1! x 2!)=3x2x1/2x1=3ways.

All the possible spanning trees are shown below


Since it contain all the vertices of the graph G. We may call it a spanning tree of the connected graph G.

Note

If there are n vertices in a tree, there are n-1 edges in it.

So if a connected graph G has m edges we must remove m-(n-1) edges to produce a spanning tree.

Real time Example

A telephone network linking branches of company through cables for information storage and retrieval.

There are too many links in the network. If it is required to remove extra links, how many links are needed for each branch.

MINIMUM SPANNING TREE

Definition: A minimum spanning tree is a spanning tree T is such that sum of the weights associated with all edges in it is a minimum.

Two algorithms for constructing minimum spanning tree, which are,

1.      Prim’s Algorithm

2.      Kruskal’s Algorithm


1. Prim’s Algorithm:

Prim's algorithm is to construct spanning tree with minimum cost.

Prim's algorithm shares a similarity with the shortest path first algorithms.

1.Remove all self –loops and all parallel edges.

If two nodes have a parallel edge, keep the one which has the least cost.

2.Select a random node. Check the outgoing edges of that node and pick the edge with the least cost and not forming a circuit.

3.Check each node until all nodes are visited.

4.This Process is stopped when (n-1) edges have been added.

 Example

Step 1 - Remove all loops and parallel edges

Remove all loops and parallel edges from the given graph. In case of parallel edges, keep the one which has the least cost associated and remove all others.

Step 2 - Choose any arbitrary node as root node

Step 3 - Check outgoing edges and select the one with less cost

After choosing the root node S, we see that (S,A) and (S,C) are two edges with weight 7 and 8, respectively. We choose the edge (S,A) as it is lesser than the other.

From vertex A (to check for all edges going out from it), to select the next one, this has the lowest cost and includes it in the tree.

After this step, S-A-C tree is formed. Now we'll again treat it as a node and will check all the edges again. However, we will choose only the least cost edge. In this case, (C,D) is the new edge, which is less than other edges' cost 8, 6, 4, etc.

After adding node D to the spanning tree, we now have two edges going out of it having the same cost, i.e. (D,T) and (D,B). Thus, we can add either one. But the next step will again yield edge 2 as the least cost. Hence, we are showing a spanning tree with both edges included.

Since all the 6 vertices are connected by 5 edges that do not from a circuit, the edges of the spanning tree are (S,A),(A,C),(C,D),(D,B) and (D,T). 

The total weight of the minimum spanning tree = 7+3+3+2+2 =17.

 

2.Kruskal's algorithm

To find the minimum cost spanning tree uses the greedy approach. This algorithm treats the graph as a forest and every node it has as an individual tree.


Example 

Step 1 - Remove all loops and Parallel Edges

In case of parallel edges, keep the one which has the least cost associated and remove all others.

Step 2 - Arrange all edges in their increasing order of weight

The next step is to create a set of edges and weight, and arrange them in an ascending order of weightage (cost)

Edge

Cost

(B,D)

2

(D,T)

2

(A,C)

3

(C,D)

3

(C,B)

4

(B,T)

5

(A,B)

6

(S,A)

7

(S,C)

8

Step 3 - Add the edge which has the least weightage

Now we start adding edges to the graph beginning from the one which has the least weight. Throughout, we shall keep checking that the spanning properties remain intact.

The least cost is 2 and edges involved are (B,D) and (D,T). We add them. Adding them does not violate spanning tree properties, so we continue to our next edge selection.

Next cost is 3, and associated edges are (A,C) and (C,D). We add them again

Next cost in the table is 4, and we observe that adding it will create a circuit in the graph

We ignore it. In the process we shall ignore/avoid all edges that create a circuit.

We observe that edges with cost 5 and 6 also create circuits. We ignore them and move on.

Now we are left with only one node to be added. Between the two least cost edges available 7 and 8, we shall add the edge with cost 7

By adding edge (S,A) we have included all the nodes of the graph and we now have minimum cost spanning tree.

Since all the 6 vertices are connected by 5 edges that do not from a circuit, the edges of the spanning tree are (S,A),(A,C),(C,D),(D,B) and (D,T). 

The total weight of the minimum spanning tree = 7+3+3+2+2 =17. 

                                                                  

 


Comments

Post a Comment

Popular posts from this blog

Backtracking - N-Queens Problem, Sum of Subsets, Graph Colouring, Hamiltonian Cycle

Image
UNIT - V : BACKTRACKING General Method – 8-Queens Problem – Sum Of Subsets – Graph Coloring –  Hamiltonian Cycles General Method Backtracking is a problem-solving technique used in algorithms to find solutions by exploring all possible options. In backtracking, a state-space tree is a tree-like structure that represents all possible states (solutions or non-solutions) of a problem. Backtracking algorithms explore this tree using a depth-first search approach, systematically checking each path until a solution is found or all possibilities have been exhausted.  Here’s how it works, step-by-step: Start with a choice : Make a decision and move forward. Check feasibility : If this choice leads to a solution or partial solution, continue. If not, stop exploring this path. Go back and try a different path : If you reach a dead end, go back to the last point where you made a choice. Try a different path from there. Repeat until you find a solution ...
Read more

Divide and Conquer Technique - Binary Search, Quick Sort, Merge Sort

Image
  UNIT II - DIVIDE AND CONQUER TECHNIQUE General Method – Binary Search – Merge Sort – Quick Sort.  GENERAL METHOD The divide and conquer technique is a problem-solving approach that works in three main steps: 1.       Divide : Break down a large problem into smaller, simpler sub-problems. 2.       Conquer : Solve each of the sub-problems individually. This can often be done recursively if the sub-problems are still large. 3.     Combine : Combine the solutions of the sub-problems to get the solution to the original, larger problem. This approach is commonly used in algorithms like binary search, merge sort and quick sort, where breaking down a problem makes it easier and faster to solve.   BINARY SEARCH Binary search is an efficient algorithm for finding a target value within a sorted list. Here’s how it works: Start in the Middle : Look at the middle element of the list. Compare : ...
Read more

GRAPH THEORY

Image
  GRAPH THEORY DEFINITION A graph G = (V, E) consists of a non-empty set V, called the set of vertices (points, nodes) and a set  of ordered or unordered pairs of elements of V, called the edges E set (links), such that there is a mapping from the set E to the set of ordered or unordered pairs of elements of V. Example In the first graph, V = { A , B , C , D } E = {(A,B) , (A,C) , (A,D), (B,C), (B,D) , (C,D)} In the second graph, V = { E, F, G } E = {(F,E) , (E,G) , (G,F)} If an edge e ∈ E is associated with an ordered pair (u,v) or an unordered pair (u,v), where u,v ∈ V, then e is said to connect or join the nodes u and v.  The edge e that connects the nodes u and v is said to be incident on each of the nodes.  The pair of each node that is connected by an edge is called adjacent nodes . Isolated Nodes If any node has no edges connected with any other node then its degree will be zero(0) and it will be called as isolated node. Adjacent Nodes Her...
Read more