二分木を使ったソート

ヒープじゃなくて単純な二分木を使ったソート。すなわち、

  • 左の子は親よりも小さい
  • 右の子は親よりも大きい

という構造。で、これを通りがけ順(左の枝、根、右の枝の順に調べる)に出力すると昇順にソートされる。

takatoh@nightschool $ ruby btree_sort.rb
unsorted: [47, 97, 34, 39, 74, 44, 38, 5, 10, 53]
sorted:   [5, 10, 34, 38, 39, 44, 47, 53, 74, 97]

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です