Binary Search Trees PDF

Preview

Summary

Binary Search Trees...

Description

Binary Search Trees (BST)     

Previously looked at traversal of trees Will now look at insert/delete tree nodes These all begin with searching for the node in the tree BSTs are a type of binary tree with a special organizational data This data organization leads to O(log2n) complexity for searches, insertions, and deletions in certain types of the BST (balanced trees).

Recap on graphs  Vertices (or endpoints) of an edge o Uand Vare the endpoints of a  Edgesincident on a vertex o and bare incident on V  Degree of a vertex o Xhas degree 5  Parallel edges o hand iare parallel edges  Self-loop o jis a self-loop  Cycle o circular sequence of alternating vertices and edges where each edge is preceded and followed by its endpoints (U-V-X-W) The use of graphs in searching  Weights can be distance, money, load, etc  Digraph G= (V,E) with weight function W: E→R (assigning real values to edges)  Weight of path p= v1→v2→… →vkis

 The weights associated with each edge can represent o –Cost (laying communications cabling) o –Time (airline flight times including waiting in transit) o –Distance (Transportation courier services) o –Data traffic (network routing including transfer/receive rate) or any other quantity we are interested in measuring between vertices

 Once we have weights associated with the edges of a graph we can try and minimiseor maximisetotals or take lowest or highest weighted paths through the graph  Can find the minimum accumulated weights to provide o –full connectivity (Krushkal’salgorithm) o –shortest route between two vertices (Dijkstra’s algorithm)  Suppose that G is a weighted graph. A minimum spanning treeis a spanning tree of G which minimisesthe weights on the edges in the tree.  Kruskal's algorithm (uses a greedy algorithm) finds aspanning tree with the minimum accumulated weights  There may be more than one spanning tree with this smallest accumulated weight This method builds the graph as you go along starting with just the vertices Algorithm: 1. The graph T initially consists of the vertices of G and no edges. 2. Add an edge to Thaving minimum weight but which does not give a cycle in T. 3. Repeat step 2 until T has n-1 edges.  You must arrange the edges in increasing size, check you haven’t left any out.  You must add the edges to the graph in the right order, it may not connect at first  If two edges are the same it does not matter which order you arrange them  Not all answers will be the same but all minimal spanning trees will give the same totals  For a graph with n vertices the final tree should have n-1 edges Dijkstra’s algorithm  Dijkstra’s algorithm (uses a greedy algorithm) and can be used to find the shortest path from any start vertex to any other vertex in the network  Dijkstra’s algorithm assumes that o the graph is connected o edges are undirected o edge weights are non-negative 1. Label the start vertex as the “boxed vertex” and has a permanent cost 0 . All other vertices have undefined temporary costs. 2. Assign temporary accumulated costs to all the vertices that can be reached directly from the boxed vertex. Note, if there is an existing temporary

accumulated cost at a vertex, it should be replaced only if the new cost is smaller. 3. Select the vertex with the smallest temporary accumulated cost from all unboxed vertices and make this vertex permanently boxing it and store the accumulated cost. 4. Using the newly boxed vertex, repeat steps 2-4 until all vertices have been boxed. 5. find the shortest path(s), trace back from the end vertex to the start vertex. Write the route forwards and state the length. Variations to Dijkstra Algorithm  There are other search algorithms such as Prim-Jarnik, Bellman-Ford (works with negative edges but they must be directed), etc ...  Dijkstra’s algorithm just looks at the current cost g(n) from the start node to a given node (n)  algorithm solves the same problem but as well as g(n) also includes a heuristic h(n) which is the estimated cost from nto end destination point f(n) = g(n) + h(n)  heuristic A* becomes Dijkstra’s algorithm h(n) = 0  covered in introduction to AI module Summary  Looked at searching in the context of trees BST and more balanced AVL trees  Looked at searching in graphs and how the search is based on the nature of the problem being solved.  Krushkal’s algorithm can be used when we need to find a subset of the graph which still allows connectivity between all vertices  Dijkstra’s algorithm can be used to find the shortest path between two vertices in a graph  Many variations A* extends Dijkstra’s with a heuristic...