Search and Inserts

Divide and Conquer:

solve ---> problem (A):
            if size (A) <= Critical-Size
                         then End-Action
            else begin
                  Split-problem;
                  solve-problem (A1)
                  solve-problem (A2)
                  ...........
                  Assemble-Results
             end;


Iterative Applications:

solve ---> problem (S):
              while not empty (S) do begin
                            Apply algorithm to next element of sequence S;
                            Advance S
                            end;
              End-Action

Iterative App. w Array:

solve ---> problem
               for i:=1 to size(A) do
                        Acttion on A[i];
               End-Action


Tail Recursion:

solve-problem (A):
        if size (A) <= Critical - Size
                then End-Action
                else begin
                       Split and select sub-problem i;
                        solve-problem (Ai);
                End-Action


Inversion:

inverted-search (S,A,V):
                  *********Search value V of attribute A in structure S *********
                      search (search (S,A),V)

Digital Decomposition:

solve-problem (A,n):
                    ***** n has a digital decomposition: n=nk.bk+...+n1.b1+n0****

                     Partition the problem into subset
                      A = Aj,i where, size is bi/i is 0 to k/j is 1 to n
                     for i:= 0 to k while not completed do
                             simpler-solve (A1,i;A2,i;....An,i);

Merge:

Merge (S1,S2,.....Sk)
           while at least one Si is not empty do
                   kmin := minimum value of keys in S1 to Sk
                   for i := 1 to k
                             if kmin = head (Si)
                                   then t[i] := head (Si)
                                   else t[i] = null;
                    processing-rule (t[1],t[2],.............,t[k]);
            End-Action

Randomization:

Solve-problem (A)
             repeat begin
                       randomize (A);
                       solve (randomized (A), t(A) units of time);
                       end until Solve-succeeds or Too-many-iterations;
             if Too-many-Iterations
                        then return (No-solution-exists)
                        else return (Solution);



Superimposition:

Solve-problem (A):
          case 1: solve-problem1(A);
          case 2: solve-problem2(A);
          ----------------------------
          case n: solve-problemn(A);



Interleaving:

Open-File 1 to read-write
While (!EOF)
         read line 1 from file
        delete line 1 from file
End-While

Returns empty file


Recursion Termination:

Same as divide and conquer


Interchangeability:

basic algorithms. hashing, direct addressing, interpolation/collision resolution/binary partition, fibonacci partition, median, mode
semantic rules. height balance, weight balance/lexicographic order, priority queue/binary tree, hash table/minimax, minave


Sequential search in Arrays:

i := 1
while ( i < n ) and ( key != r[i].k) do i ++;
if key == r[i].k then
            found ( r[i] )
else
            notfound ( key);


Seq. Search in Arrays with non-repeated keys:

r [n+1].k := key;
i := 1
while key != r[i].k do i++;
if i<=n then found (r[i])
else
   notfound (key);


with secondary keys:

for i:=1 to n do
     if key = r[i].k then found ( r[i] );

in lists:
 for ( p = list; p != null && key != p --->k; p = p--->next)
    if (p == null) notfound (key)
               else found ( *p )

for circular list:

q=list      
if key == q --> k then
    found ( *q)
else
  for ( p = q+1; p != q && key != p --->k; p = p--->next)
    if (p == q) notfound (key)
               else found ( *p )


Self-organizing Sequential Search in Lists (also known as Move-to-Front method)

if (list!=0 && key!=list--->k)
 /*Find record*/
for ( p = list; p--->next != 0; p=p--->next)
     if (key = p---->next--->k)
                    /*Move to Front of List*/
               q = list;
               list = p ---> next;
               p --->next = p--->next--->next;
               list--->next = q;
               break;
               }

if (list!=0 && key == list --->k) found (*list)
      else notfound (key)


Self Organizing Sequential Search in Arrays (Transpose):

i := 1
while ( i < n ) and ( r[i].k != key ) do i++;

if key == r[i].k then
    begin
    if i > 1 then
            begin
            /* Transpose with predecessor */
            tempr := r[i];
            r[i] := r [i-1];
            r[i-1] = tempr;
            i --;
            end;
     found ( r [i] )
   end;
else
     notfound ( key );


Jump Search:

read - first - record
  while key > r.k do Jump-records;
 while key < r.k do read-previous-record;
if key = r.k then
   found ( r )
else notfound ( key )



Insert in Ordered Array:

i := n;
x := false;
if n>=m then Error
else begin
   n++;
  while i > 0 do
         if r[i].k > key then begin
                 r[i+1] := r[i];
                 i--;
         else
              x := true;
              break;

if (x) r [i+1].k = key;
End;


Binary Search:

low := 0;
high := n;

while high - low > 1 do begin
           j := (high+low) div 2;
           if key <= r [j].k then high := j
                      else low := j
           end;

if key == r[high].k then found ( r[high] )
           else notfound ( key );


Interpolation (Estimated Entry) Search:

low := 1;
high := n;
while ( r[high].k >= key ) and ( key > r[low].k ) do
     begin:
     j := trunc( (key - r[low].k ) / ( r[high].k - r[low].k) * (high - low) + low;
     if key > r[j].k then low := j+1;
     else  if key < r[j].k then high := j-1;
     else low := j
     end;

if key == r[low].k then  found ( r[low] )
 else notfound ( key )


 Interpolation-sequential Search:

if n > 1 then
 begin
  j : = trunc ( ( key - r[i].k) / (r[n].k - r[i].k) ) + 1;
if key < r[j].k then
     while (j > 1) and (key<r[j].k) do j --;
else
     while (j < n) and (key >r[j].k) do j++;
end

else
j:=1;

if key == r[j].k then found ( r[j] )
 else notfound ( key );


Linear Probing Hashing

Search:

i := hashfunction (key);
last := (i+m-1) mod m;

while (i != last) and (!empty( r[i] )) and ( r[i].k != key ) do
  i = (i + 1) mod m;
if r[i].k == key then found ( r[i] )
 else notfound ( key );


Insertion:

i := hashfunction ( key );
last := (i+m-1) mod m;

while (i!=last) and (!empty( r[i] ) ) and (!deleted (r[i]) and ( r[i].k != key) do
        i := (i+1) mod m;

if (empty( r[i] )) or (deleted ( r[i] )) then
     begin
           r[i].k = key;
           m = m + 1;
else
     MaxBoundError or DuplicationError



Double Hashing:

if isPrime(m) then

Search:

i := hashfunction ( key );
inc := increment ( key );
last := (i+(m-1*inc) mod m;
while ( i != last ) and (!empty ( r[i] ) ) and ( r[i].k != key ) do
         i = ( i + inc ) mod m;
if r[i].k == key then found ( r[i] )
 else notfound ( key );


Insert:

i := hashfunction ( key );
inc := increment ( key );
last := (i+(m-1*inc) mod m;
while ( i != last ) and (!empty ( r[i] ) ) and (!deleted ( r[i] )) and ( r[i].k != key ) do
   i = ( i + inc ) mod m;
if (empty( r[i] )) or (deleted ( r[i] )) then
     begin
           r[i].k = key;
           m = m + 1;
else
     MaxBoundError or DuplicationError
    

---
else
not possible.


Quadratic Hashing:

Search:

i := hashfunction (key);
inc :=0;
while (inc<m) and (!empty(r[i]) and (r[i].k != key) do
   begin
  i := (i+inc+1) mod m;
  inc := inc + 2;
 end;
if r[i].k == key then found ( r[i] )
 else notfound ( key );


Insertion:

i := hashfunction ( key );
inc := 0;

while ( inc < m ) and ( !empty ( r[i] ) ) and ( !deleted ( r[i] ) ) and ( r[i].k != key ) do begin
   i := ( i + inc + 1 ) mod m;
  inc := inc + 2;

if (empty( r[i] )) or (deleted ( r[i] )) then
     begin
           r[i].k = key;
           m = m + 1;
else
     MaxBoundError or DuplicationError


Ordered Hashing:

Search:

i := hashfunction ( key );
inc := increment ( key );
last := (i+(m-1)*inc) mod m;
while ( i != last ) and (!empty ( r[i] ) ) and ( r[i].k != key ) do
         i = ( i + inc ) mod m;
if r[i].k == key then found ( r[i] )
 else notfound ( key );

Insertion:

if n >= m then MaxBoundError

else begin

i := hashfunction ( key )

while ( !empty(r[i]) and (!deleted(r[i]) and (r[i].k != key ) do begin

   if r[i].k > key then begin

         temp := key;     

         key := r[i].k;

         r[i].k := temp;

         end;

   i := ( i + increment (key) ) mod m;

   end;

if (empty( r[i] )) or (deleted ( r[i] )) then
     begin
           r[i].k = key;
           m = m + 1;
else
     MaxBoundError or DuplicationError



Brent's Insertion ( Reorganized Hashing) :

gotoisbad := false;
init := hashfunction (key);
inc := increment (key);
for i := 0 to n do
   for j := 1 down to 0 begin
          jj := ( init + inc*j ) mod m;
          ii :=  ( jj + increment ( r[jj].k ) * ( i - j ) ) mod m;
          if empty ( r[ii] ) or deleted ( r[ii] ) then begin

                     r [ii] := r [jj];

                    r[jj].k := key;

                     m := m + 1;

                    gotousbad := true;

                    break;

    end;

end;

Direct Chaining Hashing:

Search:

p = ptrs [ hashfunction ( key ) ];
while ( p != 0 && key != p --> k )
   p := p ---> next;

if ( p == 0 ) notfound ( key );
   else found ( *p );


Insertion:

i = hashfunction ( key );
ptrs [i] := newnode ( key, ptrs[i] );
n++;


Separate Chaining Hashing:

Search:

p = &r[ hashfunction ( key ) ];
while ( p != 0 && key != p -->k )
    p = p --> next;
if p == 0 notfound ( key );
   else found ( *p );

Insertion:

i = hashfunction ( key );
if ( empty ( r[i] ) )
     r[i].k = key;
else
    r[i].next = newnode ( key.r[i].next );
n++;


Coalesced Hashing:

Search:

i = hashfunction ( key );
while ( i != null && !empty (r[i]) && r[i].k != key)
             i = r[i].next;
if (i==null || empty (r[i])) notfound ( key )
      else found (r[i]);

Insertion:

i = hashfunction (key);
if empty (r[i])
 r[i].k = key;
 r[i].next = null;
 n++;
else
 while ( r[i].next !=null && r[i].k != key )
{
   i = r[i].next;
   if ( r[i].k == key ) DuplicationError
   else
    { while (!empty (r[nextfree]) && nextfree >= 0 ) nextfree --;
       if nextfree < 0
            MaxBoundsError
      else
         {
                  r[i].next = nextfree;
                 r[nextfree].k = key;
                 r[nextfree].next = null;
                n++;
          }
      }

}


Extendable Hashing Search:

i = hasfunction (key) mod m;
read-directory-entry (i) into npage;
read-leaf-page (npage) into r;

i = 1;
while ( i < b ) and ( r[i].k != key ) do i++;
if r[i].k == key then found ( r[i] )
 else notfound ( key);

Linear Hashing with Bucket:

i = hi (key);
if ( i mod m0) < m - m0 then hashfunction := i mod ( 2m0)
                                     else hashfunction := i mod m0;


Tree:

Binary Tree Definition:

type tree = ^node;
        node = record
            k : typekey;
            left, right : tree;
            end;

Search:

procedure search ( key : typekey ; t : tree )
if (t == null) then notfound ( key );
else if t^.k == key  then found ( t^ );
else  if t^.k < key then search ( key, t^.right );
else search ( key, t^.left );
end;

Insertion:

procedure insert ( key: typekey ; var t : tree );
begin
if (t == null) then
            t = newnode ( key, nil, nil )
else if t^.k == key then DuplicationError
else if t^k < key then insert ( key , t^.right);
else insert ( key, t^.left );
end;


AVL Tree Insertion:

procedure insert ( key: typekey ; var t : tree ) : integer ;
var incr : integer;
begin

insert = 0;

if t == null then begin

    t = newnode ( key, nil, nil );

    t^.bal = 0;

    insert = 1;

   end;

else if t^.k == key DuplicationError;

else with t^ do

  begin

    if k < key then incr = insert ( key, right );

    else incr = - insert (key, left );

bal += incr;

if (incr != 0 ) && ( bal != 0 ) then

       if bal < -1 then

         if left^.bal < 0 then rrot ( t )

         else begin lrot (left) : rrot ( t ) ; end;

       else if bal > 1 then

         if right^.bal > 0 then lrot (t) 

        else begin rrot(right) : lrot ( t ); end;

       else insert = 1;

   end;

end;


Weight Balanced Tree Insertion:

procedure insert( key : typekey ; var t : tree ) :
var wbal ; real ;

begin

if t==nil then begin
            t = newnode ( key, nil, nil );
           t^.weight = 2;
           end;
else if t^.k == key then DuplicationError;
else with t^ do begin
  if k < key then insert ( key, right )
   else insert ( key, left );
weight = wt (left) + wt (right) ;
wbal = wt (left) / wt (t);

if wbal > 0.7 then
  if wt(left^.left)/wt(left) > 0.4 then rrot (t);
  else begin lrot(left); rrot (t) end;
else if wbal < 0.29
  if wt(right^.left)/wt(right) < 0.5 then lrot (t)
  else begin rrot(right); :lrot(t) end;
end;
end;


Rotations:

procedure lrot ( var t : tree )
 var temp : tree;
       a: int;
 begin
  temp = t;
  t = t^.right;
  temp^.right = t^.left;
  t^.left = temp;

  a = temp^.bal;
  temp^.bal = a - 1 - max ( t^.bal, 0);
  t^.bal = min (a-2, a+t^.bal - 2, t^.bal - 1);

end;

procedure rrot ( var t : tree )
var temp : tree;
 begin
   temp = t;
   t = t^.left;
   temp^.left = t^.right;
   t^.right = temp;
end;


Internal Path Reduction Tree Insertion :

procedure checkrots ( var t : tree );

var wl, wr : integer;

begin
if t != nil then with t^ do begin
  wl = wt (left);
  wr = wt (right);
  if wr > wl then begin
     if wt (right^.right) > wl then
         begin lrot(t); checkrots (left); end;
     else if wt (right^.left) > wl then
         begin rrot (right); lrot (t);
                  checkrots (left); checkrots (right);
                  end;
      end;
   else if wl > wr then begin
     if wt (left^.left) > wr then
         begin rrot(t); checkrots (right); end;
     else if wt (left^.right) > wr then
         begin lrot (left); rrot (t);
                  checkrots (left); checkrots (right);
                  end;
      end;
    end;
end;

procedure insert (key:typekey ; var t:tree)
begin
if t == nil then begin
       t = newnode (key,nil,nil);
       t^.weight = 2;
       end;
else if t^.k == key then DuplicationError;
else with t^ do begin
  if k < key then insert (key,right);
  else insert (key,left);
  weight = wt(left) + wt(right);
  checkrots (t);
 end;


Top-down construction, Binary Tree:

BuildTree (SetofKeys) : tree;
   k = select (SetofKeys);
   A1 = Keys in SetofKeys < K;
  A2 = Keys in SetofKeys > K;
  return newnode (K, BuildTree(A1), BuildTree(A2));
end;


Median Split Trees:

Search:
procedure search ( key : typekey ; t : tree );
begin
 if t==nil then
      notfound ( key );
else if t^OwnerKey == key then
      found (t^)
else if t^.SplitKey < key then
      search ( key, t^.right)
   else search (key, t^.left);
end;


Double Left Rotation:

rrot (t^.right); lrot (t);

Double Right Rotation:

lrot(t^.left); rrot (t);



B-Tree Definition:

typedef struct btnode {
     int d;
    typekey k[2*M];
    struct btnode *p[2*M+1];
    } node, *btree;

Search:

search (key, t)
typekey key;
btree t;

{                     int i;
     while (t != null) {
             for ( i=0; i <  t ---> d && key < t ---> k[i] ; i++ );
             if (key  ==  t ---> k[i])
                         { found ( t, i ); return;}
             t = t ---> p[i];
             }
      notfound (key);
}


Insertion: