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 >>

 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 >>

B-TREES
> n keys, n+1 children
> a fixed integer t >= 2 called the minimum degree
> Every node other than the root must have at least t - 1 keys, t children.
> Every node can contain at most 2t - 1 keys, 2t children.
> at depth h there are at least 2t^(h-1) nodes

B-Tree-Search(x, k)
  i <- 1
  while i <= n[x] and k > keyi[x]
      do i <- i + 1
  if i <= n[x] and k = keyi[x]
      then return (x, i)
  if leaf[x]
      then return NIL
  else Disk-Read(ci[x])
      return B-Tree-Search(ci[x], k)

B-Tree-Create(T)
  x <- Allocate-Node()
  leaf[x] <- TRUE
  n[x] <- 0
  Disk-Write(x)
  root[T] <- x

B-Tree-Split-Child(x, i, y)
  z <- Allocate-Node()
  leaf[z] <- leaf[y]
  n[z] <- t - 1
  for j <- 1 to t - 1
      do keyj[z] <- keyj+t[y]
  if not leaf[y]
      then for j <- 1 to t
          do cj[z] <- cj+t[y]
  n[y] <- t - 1
  for j <- n[x] + 1 downto i + 1
      do cj+1[x] <- cj[x]
  ci+1 <- z
  for j <- n[x] downto i
      do keyj+1[x] <- keyj[x]
  keyi[x] <- keyt[y]
  n[x] <- n[x] + 1
  Disk-Write(y)
  Disk-Write(z)
  Disk-Write(x)

B-Tree-Insert(T, k)
  r <- root[T]
  if n[r] = 2t - 1
      then s <- Allocate-Node()
      root[T] <- s
      leaf[s] <- FALSE
      n[s] <- 0
      c1 <- r
      B-Tree-Split-Child(s, 1, r)
      B-Tree-Insert-Nonfull(s, k)
  else B-Tree-Insert-Nonfull(r, k)

B-Tree-Insert-Nonfull(x, k)
  i <- n[x]
  if leaf[x]
      then while i >= 1 and k < keyi[x]
          do keyi+1[x] <- keyi[x]
          i <- i - 1
          keyi+1[x] <- k
          n[x] <- n[x] + 1
          Disk-Write(x)
      else while i >= and k < keyi[x]
          do i <- i - 1
          i <- i + 1
          Disk-Read(ci[x])
          if n[ci[x]] = 2t - 1
              then B-Tree-Split-Child(x, i, ci[x])
                  if k > keyi[x]
                      then i <- i + 1
          B-Tree-Insert-Nonfull(ci[x], k)

 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