McGraw Hill Introduction To Algorithms (2nd Ed) >>

 HEAPSORT (112 - 127) 15 pages
  6    1    1,2,3,4,5,6,7
  6    2    1,2,3,4,5
  6    3    1,2,3
  6    4    1,2,3,4 >>

 SORTING IN LINEAR TIME (145 - 160) 15 pages
  8    1    1,2,3,4*
  8    3    1,2,3,4,5*
  8    4    1,2
  8    Pro  2,4,6 >>

 HASH TABLES (192 - 219) 27 pages
  11    1    1,2,3
  11    2    1,2,3,4*
  11    3    1,2,3,4
  11    4    1,2,3,4 >>

 BINARY SEARCH TREES (220 - 238) 18 pages
  12    1    1,2,3,4,5
  12    2    1,2,3,4,5,6,7,8,9
  12    3    1,2,3,4,6 >>

BINARY SEARCH TREES
Search, Minimum, Maximum, Predecessor, Successor, Insert & Delete Operations

INORDER-TREE-WALK(x) // LEFT-TOP-RIGHT
1 if x != NIL
2     then INORDER-TREE-WALK(left[x])
3     print key[x]
4     INORDER-TREE-WALK(right[x])

PREORDER-TREE-WALK(x) // TOP-LEFT-RIGHT
POSTORDER-TREE-WALK(x) // LEFT-RIGHT-TOP

TREE-SEARCH (x, k)
1 if x= NIL or k = key[x]
2     then return x
3 if k < key[x]
4     then return TREE-SEARCH(left[x], k)
5 else return TREE-SEARCH(right[x], k)

SUCCESSOR : minimum key in the right subtree

ITERATIVE-TREE-SEARCH(x, k)
1 while x != NIL and k != key[x]
2     do if k < key[x]
3            then x <-- left[x]
4        else x <-- right[x]
5 return x

TREE-MINIMUM (x)
1 while left[x] != NIL
2     do x <-- left[x]
3 return x

TREE-SUCCESSOR(x)
1 if right[x] != NIL
2     then return TREE-MINIMUM (right[x])
3 y <-- p[x]
4 while y!= NIL and x = right[y]
5     do x <-- y
6     y <-- p[y]
7 return y

TREE-INSERT(T, z)
1 y <-- NIL
2 x <-- root[T]
3 while x != NIL
4     do y <-- x
5     if key[z] < key[x]
6         then x <-- left[x]
7     else x <-- right[x]
8 p[z] <-- y
9 if y = NIL
10    then root[T] <-- z     // Tree T was empty
11 else if key[z] < key[y]
12        then left[y] <-- z
13    else right[y] <-- z

TREE-DELETE(T, z)
1 if left[z] = NIL or right[z] = NIL
2     then y <-- z
3 else y <-- TREE-SUCCESSOR(z)
4 if left[y] != NIL
5     then x <-- left[y]
6 else x <-- right[y]
7 if x != NIL
8     then p[x] <-- p[y]
9 if p[y] = NIL
10    then root[T] <-- x
11 else if y = left[p[y]]
12        then left[p[y]] <-- x
13    else right[p[y]] <-- x
14 if y != z
15    then key[z] <-- key[y]
16    copy y's satellite data into z
17 return y

 RED-BLACK TREES (238 - 261) 23 pages
  13    1    1,2,6
  13    2    1,2,3
  13    3    1,2, 3, 6
  13    4    1, 2, 3, 4, 6, 7 >>

 B-TREES (371 - 388) 17 pages
  18    1    1, 2, 3, 4, 5
  18    2    1, 3, 5, 6 >>

 BINOMIAL HEAPS (388 - 405) 17 pages
  19    1    1, 2
  19    2    1, 2, 3, 5, 7 >>

 SORTING NETWORKS (614 - 632) 18 pages >>

 MATRIX OPERATIONS (632 - 673) 41 pages >>

 Show All