アルゴリズムイントロダクション 12 章「2分探索木」

数学的基礎とデータ構造 (アルゴリズムイントロダクション)の 12章

12.1-1

木の高さってルートは含まないのか。ノートに描いた。

12.1-2

親と子の関係が異なる。
O(n) では出来ない。兄弟ノードの順序を決められない。

12.1-3

スタックに push して最後に出力。

12.1-4

そのまんま。
L->R->M。M->L->R。

12.1-5

分かりません。

12.2-1

12.2-2

TREE-MINIMUM(x)
  if left[x] == Nil
      return x
  else
     return TREE-MINIMUM(left[x])
  endif

12.2-3

TREE-PREDECESSOR(x)
  if left[x] != NIL
    then return TREE-MINIMUM(left[x])
  y <- p[x]
  while y != NIL and x = left[y]
    do x <- y
      y <- p[y]
  return y

12.2-4

図12.2 の 3 が見つかった葉の場合。

12.2-5

定義より明らか。

12.2-6

分かりません。

12.2-7

そのまま。

12.2-8

TREE-SUCCESSOR は木を降りきるか、そのあと上るだけだから。

12.2-8

x が y の left の場合、二分探索木の定義を再帰的に葉に当てはめていくと明らか。
right の場合も同様。

12.3-1

TREE-INSERT(x, y, z)
  if x == NIL then
    p[z] <- y
  else
    if key[z] < key[y]
      return TREE-INSERT(left[x], x, z)
    else
      return TREE-INSERT(right[x], x, z)
    end
  end
  if y == NIL then
    root[T] <- z
  else if key[z] < key[y]
    left[y] <- z
  else
    right[y] <-z
  end