Categories
Algorithms Computer Science

Determine if tree is AVL in O(n)

The following java method will determine if a binary tree is AVL (and, obviously BST)

/**
 * This recursive method will calculate if a tree is AVL by returning
 * its max depth.
 *
 * @param t  
 * @param p 
 * @return Max depth of the binary tree if it's avl else -1
 **/
static int isAVL(Node t, int p){
  int fl = 0; // This is the left factor
  int fr = 0; // This is the right factor
  if(t.hasLeft()){
    if(key(t.leftChild() > key(t))) return -1;
    fl = isAVL(t.leftChild(), p + 1);
  }
  if(t.hasRight()){
    if(key(t.rightChild()) < key(t)) return -1;
    fr = isAVL(t.rightChild(), p + 1);
  }
  if(fr == -1 || fl == -1) return -1;
  if(abs(fr - fl) == 0 || abs(fr - fl) == 1) return max(fl, fr, p);
  else return -1;
}
Categories
Algorithms Computer Science

Determine max and min root leaf path in a Binary Search Tree (BST)

Let’s view an algorithm that manage to find the minimum and the maximum root-leaf path in a binary search tree. I used three stacks in this algorithm, one is temporary and the other will be filled with the results. Note that if we change:

  • i > maxSeq.size() with i >= maxSeq.size() we get the longest root-leaf path from the right instead of from the left
  • i < minSeq.size() with i <= minSeq.size() we get the shortest root-leaf path from the left instead of from the right
/**
 * Find the longest root-leaf path
 * 
 * @param t A BST tree
 * @param depth Initially set to 0
 * @param tempSeq Empty stack
 * @param minSeq Empty stack
 * @param maxSeq Empty stack
 */
public void maxMinPath(BSTNode t, int depth, Stack tempSeq, Stack minSeq, Stack maxSeq){
  tempSeq.push(t);
  if(t.hasLeft()) maxMinPath(t.left(), depth + 1, tempSeq, minSeq, maxSeq);
  if(t.hasRight()) maxMinPath(t.right(), depth + 1, tempSeq, minSeq, maxSeq);
  if(t.isLeaf()){
    if(i > maxSeq.size()) maxSeq = tempSeq.clone();
    if(minSeq.size() == 0 || i <= minSeq.size()) minSeq = tempSeq.clone();
  }
  tempSeq.pop();
}
Categories
Algorithms Computer Science

Algorithms on Graphs

Depth-First-Search (DFS)

The first kind of visit in a graph is the DFS and its output is:

  • Generate a spanning forest;
  • Visit every edge and every vertex;
  • Determine if the graph is connected;
  • Calculate the connected components of the graph.

First Part – First Labeling

The first labeling part will initialize the graph. In a non-directed graph we have these statuses:

  • Vertices can be:
    • UNEXPLORED
    • VISITED
  • Edges can be:
    • UNEXPLORED
    • DISCOVERY
    • BACK
DFS(Graph G)
  for all u in G.vertices()
    setLabel(u, UNEXPLORED)
  for all e in G.edges()
    setLabel(e, UNEXPLORED)
  for all v in G.vertices()
    DFS(G, v)

Second Part – True Labeling

In the second part we choose visited and discovery edges.

DFS(Graph G, Vertex v)
  setLabel(v, VISITED)
  for e in G.incidentEdges()
    if getLabel(e) == UNEXPLORED
       w = opposite(v, e)
       if getLabel(w) == UNEXPLORED
         setLabel(e, DISCOVERY)
         DFS(G, w)
       else
         setLabel(e, BACK)

Direct Depth First Search (D-DFS)

In a direct graph

  • Vertices has two fields:
    • int discovery_label – a progessive number 0, 1, 2 … n (if zero vertex is UNEXPLORED)
    • int leaving_label – a progressive number 0, 1, 2, … n
  • Edges can be:
    • UNEXPLORED
    • DISCOVERY/TREE
    • BACK
    • FORWARD
    • CROSS

We also define two methods:

  • getNextLLabel – which generate the next leaving_label progessive number;
  • getNextDLabel -which generate the next discovery_label progessive number.
D-DFS(Graph G, Vertex v)
  setDiscoveryLabel(v, getNextDLabel())
  for all e in G.outgoingEdgesFrom(v)
    if getLabel(e) == UNEXPLORED
      w = opposite(v, e)
      if getDiscoveryLabel(v) == UNEXPLORED
        setLabel(e, DISCOVERY)
        D-DFS(G, w)
      else if getLeavingLabel(w) == 0
        setLabel(e, BACK)
      else if getLeavingLabel(v) < getLeavingLabel(w)
        setLabel(e, FORWARD)
      else
        setLabel(e, CROSS)
  setLeavingLabel(v, getNextLLabel)

Strong connected di-graphs

A di-graph is connected if for every pair of vertices A and B we have an oriented path from A to B and from B to A.

Connection test algorithm

We can use the just explained D-DFS in order to understand if a graph is connected, we have to follow these steps:

  1. D-DFS on a graph G. After that we have every vertex and every label assigned, starting from whatever vertex;
  2. Check for UNEXPLORED vertex. If there's even only one vertex labeled UNEXPLORED the graph isn't connected;
  3. Transpose the graph to G'. Let's invert every edge orientation to get a transposed graph;
  4. D-DFS on G'. Another labeling but now on the transposed graph;
  5. Check for UNEXPLORED vertices. As before, if we have no UNEXPLORED vertices the graph G' is connected and at this point even G is connected.

Calculate the connected components algorithm

Suppose we have a not connected graph. If we try to execute the previous algorithm at the step 5. or 2. it ends telling us that the graph is not connected but.. we have a connected component ready! So could try another D-DFS but starting from an unexeplored vertex but how can we choose it?

We have to note somewhere (an array) the leaving order of the vertex because we will start from the last leaved vertext but unexplored!

Breadth-First-Search (BFS)

Let's see the breadth-first-search that it's useful if we have to calculate shortest paths or if we want to visit every discendet of a vertices before go on in the search.

BFS(Graph G, Vertex v)
  setLabel(v, VISITED)
  L[0] <- new empty sequence
  L[0].insertLast(v)
  i <- 0
  while -L[i].isEmpty()
    L[i+1] <- new empty sequence
    for all e in G.incidentEdges(v)
      if getLabel(e) == UNEXPLORED
        w <- opposite(v,e)
        if getLabel(w) == UNEXPLORED
          setLabel(e, DISCOVERY)
          setLabel(w, VISITED)
          L[i+1].insertLast(w)
        else
          setLabel(e, CROSS)
    i <- i+1

Dijkstra's shortest path algorithm

Let's view now a simple example of a Dijkstra's algorithm for finding the shortest path from a vertex.

DijkstraDistances(Graph G, Vertex s)
  Q <- new heap-based priority queue
  for all v in G.vertices()
    if v == s setDistance(v, 0)
    else setDistance(v, infinite)
    l <- Q.insert(getDistance(v), v)
    setLocator(v,l)
    while -Q.isEmpty()
      u <- Q.removeMin()
      for all e in G.incidentVertices(u)
        w <- opposite(e, u)
        r <- getDistance(u) + weight(e)
        if r < getDistance(w)
          setDistance(w, r)
          Q.replaceKey(getLocator(w), r)
Categories
Algorithms Computer Science Senza categoria

Quickselect algorithm

18  8  3  2  1  5  4  9  10

Suppose we want to know the k-th element of the array, how we would do?

  1. We would sort the array, with O(nlogn) for example
  2. Then we will get the element searched

But there’s a faster method using a similar idea of QuickSort. Let’s view the QuickSelect algorithm in pseudocode applied to the problem of find the kth element of an array.Integer KthElement(Sequence S, Integer k)

Integer KthElement(Sequence S, Integer k)
  if length(S) <= 1 return 0
  m <- choosePivotPosition(S)
  L <- new empty sequence
  G <- new empty sequence
  E <- new empty sequence
  (L,G,E) <- partition(S,m)
  if length(L) == k - 1
    return E[0]
  if length(L) < k - 1
    r <- KthElement(G, k - lenght(L))
  if length(L) > k - 1
    r <- KthElement(L, k)
  return r

The idea is:

  1. Choose a random position in the array
  2. Partition the sequence in three sub-set: L of the elements that are Less of the element chosen, G of elements that are Greater and E of elements that are Equal
  3. Then if the L set has just k - 1 elements, in the E set we have the kth element anche we can return it
  4. Else we have other 2 possibilities: L is greater than our k or less, in both cases we run recursively but we will enter only in one of this two ways because if the L set is smaller than k it makes no sense to search the kth element there, so let's search only on the greater set (setting k passed as parameter opportunely) and vice versa
  5. Finally return the result of the recursive call

Note that this algorithm does not handle the case in which we have repetition in the array, as for example:

7 12 15 2 4 2 1 4 2

In this case the first step will do (chosen 12 for example)

7 2 4 2 1 4 2 -- 12 -- 15
^----- L ---^    E    G

If we want to search for the 8th element of the array the repetition of 2 and 4 in the L set will alter the result because the algorithm at the first step, because L is 7 elements big, will return 12 as the 8th element while if we ordered the array

1 2 2 2 4 4 7 12 15
1 2 --- 3 - 4 5  6th

there's no 8th element!