Trees Graphs and Combinatorics
Syllabus (Topic cover in this section):
TREES: Definitions,
Binary tree,
Binary tree traversal,
Binary search tree,
GRAPHS:Definitions and terminology,
Representation of graphs,
Multigraph,
Bipartite Graphs,
Planar graphs,
Isomorphism and Homomorphisms of graph,
Euler and Hamiltonian paths,
Graph Coloring,
Recurrence Relation & Generating Function: Recursive definition of function,
Recursive Algorithms,
Method of solving recurrences.
COMBINATORICS: Introduction,
Counting Techniques,
Pigeonhole Principle.
( Note:- Please check all kinds of information as per your college/university curriculum because it can be update syllabus time to time. )
Tree:
A tree is connected graph that contains no cycle or circuit.It is simple graph having no self loop or parallel edges. A tree contains a finite set of elements which are called vertices or nodes.
Forest:
A forest is collection of disjoint tree. It is an undirected, disconnected,acyclic graph.
Binary tree in discrete structure:
Binary tree is the tree in which the degree of of every node is less than or equal to 2. A tree consisting of no nodes is also a binary tree.
Complete binary tree in discrete structure:
A binary tree is said to be a complete binary tree if all its levels, except the last have maximum number of possible nodes and if all the nodes at the last level appear as far left as possible.
Full binary tree:
A binary tree is said to be extended or full binary tree if each node has either 0 or 2 children.
Tree Traversal:
A traversal of tree is a process in which each vertex is visited exactly once in certain manner. For a binary tree we have three type of traversal:
1.Preorder traversal
Vertex visited in the following order:
- Visit the root(N).
- Visit the left child (or subtree) of root(L).
- Visit the right child (or subtree) of root (R).
2.Inorder traversal
- Visit the left child (subtree) of tree.
- Visit the root.
- Visit the right child (subtree) of root.
3.Postorder traversal
- Visit the left child (subtree) of root.
- Visit the right child (subtree) of root.
- Visit the root.
What is a binary search tree?
- A binary search tree is a binary tree T in which data is associated with the vertices.
- The data are arranged so that, for each vertex v in T, each data item in the left subtree of v is less than the data item in v each data item in the right subtree of v is greater than the data item in v.
- In a binary search tree since every vertex in T exceeds every number in its left subtree and is less than every number in its right subtree.
In other words,
In a binary tree, every node can have a maximum of two children but there is no need to maintain the order of nodes basing on their values. In a binary tree, the elements are arranged in the order they arrive at the tree from top to bottom and left to right.
A binary tree has the following time complexities...
A binary tree has the following time complexities...
- Search Operation - O(n)
- Insertion Operation - O(1)
- Deletion Operation - O(n)
Operations on a Binary Search Tree
The operations are performed on a binary search tree are as follows:
- Search
- Insertion
- Deletion
Search Operation in BST
In a binary search tree, the search operation is performed with O(log n) time complexity. The search operation is performed as follows:
- Step 1 - Read the search element from the user.
- Step 2 - Compare the search element with the value of root node in the tree.
- Step 3 - If both are matched, then display "Given node is found!!!" and terminate the function
- Step 4 - If both are not matched, then check whether search element is smaller or larger than that node value.
- Step 5 - If search element is smaller, then continue the search process in left subtree.
- Step 6- If search element is larger, then continue the search process in right subtree.
- Step 7 - Repeat the same until we find the exact element or until the search element is compared with the leaf node
- Step 8 - If we reach to the node having the value equal to the search value then display "Element is found" and terminate the function.
- Step 9 - If we reach to the leaf node and if it is also not matched with the search element, then display "Element is not found" and terminate the function.
- Difference between BFS and DFS
Breadth First Search (BFS)
Breadth First Search is an algorithm for traversing or searching tree or graph data structure.
It starts at the tree root and explores the neighbour node first, before moving to the next level neighbours.
Algorithmic Steps:
Step 1: Push the root node in the queue.
Step 2: Loop untill the queue is empty.
Step 3: Remove the node fromthe queue.
Step 4: If the removed node has unvisited child nodes, mark them as visited and insert the unvisited children in queue.
Depth First Search (DFS)
Depth first search (DFS) is an algorithmic for traversing or searching tree or graph data structure . One start at the root (selecting some arbitrary node as the root in the case of graph ) and explores as for as possible along each branch before backtracking.
Algorithmic Step:
Step 1: Push the root node in the stack.
Step 2: Loop Until stack is empty.
Step 3: Pick the node on the stack.
Step 4: If the node has unvisited child node, get the unvisited child node, mark it as traversed and push it on stack.
Step 5: If the node does not have any unvisited child nodes, pop the node from the stack.
Define Graph
A graph is a non-linear data structure consisting of notes and edges. A graph consists of two sets as follows:
1. Set V of nodes or point or vertices of graph G.
2. Set E of ordered or unordered pair of distinct edges of G.
We denote such a Graph by G(V,E) and set of vertices as V(G) and set of edges as E(G).
For example:
Order of Graph (G)
If G is finite then number of vertices in G denoted by V(G) is called ordered of G.
Size of Graph (G)
The number of edges denoted by E(G) in a finite graph G is called size of G.
Post a Comment