true

Find the best tutors and institutes for BCA Tuition

Find Best BCA Tuition

Please select a Category.

Please select a Locality.

No matching category found.

No matching Locality found.

Outside India?

Search for topics

DATA FILE STRUCTURE

Binary Search Tree

  • A tree is a connected, acyclic, unidirectional graph.
  • It emulates a tree structure with a set of linked nodes. 
  • The topmost node in a tree is called the root node, node of a tree that has child nodes is called an

    internal node or inner node and the bottom most nodes are called a leaf node.

  • The root is a node that has no parent; it can have only child nodes. Leaves, on the other hand, have

    no children. 

  • The simplest form of a tree is a Binary Tree which has a root node and two subtrees (which is a

   portion of a    tree data structure that can be viewed as a complete tree in itself) - left and right.

  • A Binary Search Tree is a binary tree in which if a node has value N, all values in its left sub-tree

   are less than N, and all values in its right sub-tree are greater than N.

  • This property called binary search tree property holds for each and every node in the tree.

               Basic operations of Binary Search tree are:

  • Finding a node with a specific data value.
  • Finding a node with minimum or maximum data value.
  • Insertion and deletion of a node.
  • Three (preorder, postorder and inorder) operations for depth-first traversal of a tree

Preorder: 

  • Visit a node before traversing it’s sub-trees

Inorder: 

  • Visit a node after traversing it’s left subtree but before traversing it’s right sub-tree

Postorder: 

  • Visit a node after traversing all of it’s subtrees
  • Binary search tree has three properties: data stands for the value of the node, *left is the left subtree

   of a node and *right (a pointer of type struct treeNode) is the right subtree of a node.

Heap

  • The Heap data structure is an array object that can be viewed as a complete and balanced

   binary tree.

  • Min (Max)-Heap has a property that for every node other than the root, the value of the node is at

   least (at most) the value of its parent.

  • Thus, the smallest (largest) element in a heap is stored at the root, and the sub-trees rooted at a

    node contain larger (smaller) values than does the node itself.

  • A Min-heap viewed as a binary tree and an array.
  • Heaps can be used as an array.
  • For any element at array position I, left child is at ( 2i ), right child is at ( 2i+1 ) and parent is at

    (int) (i / 2).

  • Heap size is stored at index 0.
  • Basic operations of a heap are:
  1. Insert – Insert an element.
  2. Delete minimum – Delete and return the smallest item in the heap.

        Performance

  1. Worst case complexity of Insert is O (lg n), where n is the number of elements in the heap.
  2. Worst case running time of DeleteMin is O (lg n) where n is the number of elements in the heap.

Graphs and Graph Algorithms 

Depth-First Search

  • Depth-first search algorithm searches deeper in graph whenever possible.
  • In this, edges are explored out of the most recently visited vertex that still has unexplored edges

    leaving it.

  • When all the vertices of that vertex’s edges have been explored, the search goes backtracks to

    explore edges leaving the vertex from which a vertex was recently discovered.

  • This process continues until we have discovered all the vertices that are reachable from the

      original source vertex.

  • It works on both directed and undirected graphs.

Analysis

  • The DFS function is called exactly once for every vertex that is reachable from the start vertex. 
  • Each call looks at the successors of the current vertex, so total time is O(# reachable nodes + total

    # of outgoing edges from those nodes).

  • The running time of DFS is therefore O(V + E). 

Breadth-First Search

  • Breadth-first search is one of the simplest algorithms for searching a graph.
  • Given a graph and a distinguished source vertex, breadth-first search explores the edges of the

    graph to find every vertex reachable from source.

  • It computes the distance (fewest number of edges) from source to all reachable vertices and

     produces a “breadth-first tree” with source vertex as root, which contains all such reachable

     vertices.

  • It works on both directed and undirected graphs.
  • This algorithm uses a first-in, first-out Queue Q to manage the vertices.

Analysis

  • Initializing takes O(V) time The queue operations take time of O(V) as enqueuing and

   dequeuing takes O(1) time.

  • In scanning the adjacency list at most O(E) time is spent.
  • Thus, the total running time of BFS is O(V + E).

Dijkstra’s Algorithm

  • Dijkstra’s algorithm solves the single source shortest path problem on a weighted, directed

   graph only when all edge-weights are non-negative.

  • It maintains a set S of vertices whose final shortest path from the source has already been

   determined and it repeatedly selects the left vertices with the minimum shortest-path estimate,

     inserts them into S, and relaxes all edges leaving that edge.

  • In this we maintain a priority-Queue which is implemented via heap.

            Algorithm (described in detail within the document for this tutorial)

  • Input Format: Graph is directed and weighted.
  • First two integers must be number of vertices and edges which must be followed by pairs of

   vertices which has an edge between them.

Floyd-Warshall Algorithm

  • Floyd-Warshall algorithm is a dynamic programming formulation, to solve the all-pairs

    shortest path problem on directed graphs.

  • It finds shortest path between all nodes in a graph.
  • If finds only the lengths not the path.
  • The algorithm considers the intermediate vertices of a simple path are any vertex present in that

    path other than the first and last vertex of that path.

               Algorithm

  • Input Format: Graph is directed and weighted.
  • First two integers must be number of vertices and edges which must be followed by pairs of

   vertices which has an edge between them.

 

Bellman –Ford

  • The bellman-Ford algorithm solves the single source shortest path problems even in the cases

    in which edge weights are negative.

  • This algorithm returns a Boolean value indicating whether or not there is a negative weight cycle

    that is reachable from the source.

  • If there is such a cycle, the algorithm indicates that no solution exists and it there is no such cycle,

    it produces the shortest path and their weights.

            Complexity 

  • The Bellman-Ford algorithm runs in time O(VE), since the initialization takes Θ(V) time, each

    of the |V| - 1 passes over the edges takes O(E) time and calculating the distance takes O(E) times.

 

 

0 Dislike
Follow 0

Please Enter a comment

Submit

Other Lessons for You

Description of an Algorithm
What is an Algorithm? An Algorithm is a step-by-step procedure, which defines a set of rules to be executed in a specific order to get the desired output. Characteristics of Algorithm: Language independent Feasible Unambiguous Finiteness Well-define...
P

Parul R. | 04 Aug

1 0
0

C program for Beginners
A Program to print 2 integer value. #include<stdio.h> #include<conio.h> main() int a,b,add; a=5; b=3; add=a+b; printf(“ Addition=%d”,&add); getch(); Brief description...
P

Parul R. | 02 Aug

1 0
0

Key Tips On How To Study Smart
The study is a method in which we gain knowledge which in turn leads to the broadening of our mindset and the significance of it is that we implement this knowledge in our daily life which is called common...

Sumit Agarwal | 24/05/2019

1 0
0

What is DBMS and RDBMS
Database Management Systems A database is a collection of data or records. Database management systems are designed to work with data. A database management system (DBMS) is a software system that uses...

Amit Patil | 15/04/2019

0 0
0

Mastering in Java Programming
Core java topics What is Java?Execution Model Of JavaBytecodeHow to Get Java?A First Java ProgramCompiling and Interpreting ApplicationsThe JDK Directory StructureUsing Eclipse Data types and Variables What...

Rajeev Majumdar | 12/07/2018

1 0
0
X

Looking for BCA Tuition Classes?

Find best tutors for BCA Tuition Classes by posting a requirement.

  • Post a learning requirement
  • Get customized responses
  • Compare and select the best

Looking for BCA Tuition Classes?

Find best BCA Tuition Classes in your locality on UrbanPro

Post your learning requirement

UrbanPro.com is India's largest network of most trusted tutors and institutes. Over 25 lakh students rely on UrbanPro.com, to fulfill their learning requirements across 1,000+ categories. Using UrbanPro.com, parents, and students can compare multiple Tutors and Institutes and choose the one that best suits their requirements. More than 6.5 lakh verified Tutors and Institutes are helping millions of students every day and growing their tutoring business on UrbanPro.com. Whether you are looking for a tutor to learn mathematics, a German language trainer to brush up your German language skills or an institute to upgrade your IT skills, we have got the best selection of Tutors and Training Institutes for you. Read more