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.