Ruby で赤黒木を実装してみた

この記事は Okinawa.rb Advent Calendar 2019 の 15日目の記事です。

結論

実装しました。

https://gist.github.com/siman-man/a8ed58effeaaf59855deac490574760c

二分探索木

前々から赤黒木を実装しようと思っていたのですがずっと放置していたので、今回実装してみました。

まず比較用に二分探索木から実装します。

https://gist.github.com/siman-man/dc79878e5a8d93c73299c1145458a820

二分探索木ではデータの検索、挿入、削除といった操作が O(log n) で可能となるデータ構造です。

探索木の各ノードは以下の条件を満たします。

あるノード x において、y が左側に存在するノードであるならば「x.value >= y.value」、右側であれば「x.value <= y.value」を満たす。

この条件が満たされていることで、値の検索が下記のようなコードで可能となり、その実行時間は O(log n) となります。

  def find(value)
    z = @root

    while z != NUL && z.value != value
      if value < z.value
        z = z.left
      else
        z = z.right
      end
    end

    z
  end

データの挿入時についても、値の挿入先を探すのに上記と似たような処理を実行するのですが、入力されるデータによっては実行時間が O(n) となってしまいます。

例として 1000 件のデータをランダムに入れるコードを書いてみます。

require 'benchmark'

nums = (1..1000).to_a.shuffle

time = Benchmark.measure { nums.each { |n| bst.insert(n) } }

puts time

結果

$ ruby binary_search_tree.rb
  0.006067   0.000049   0.006116 (  0.006128)

ここでランダムだった部分を取り除きます。

  require 'benchmark'

- nums = (1..1000).to_a.shuffle
+ nums = (1..1000).to_a

  time = Benchmark.measure { nums.each { |n| bst.insert(n) } }

  puts time

すると実行時間が遅くなることが確認出来ます。

$ ruby binary_search_tree.rb
  0.192344   0.000213   0.192557 (  0.192703)

このように特定の入力によって操作の速度が低下してしまうのを回避できるのが「平衡二分探索木」であり、その一つに赤黒木があります。

赤黒木

赤黒木では先程の二分探索木の各ノードに色情報が付与されます。ノードの色は「赤」か「黒」です。赤黒木では以下の制約によって木の高さの差が2倍を超えることが無いことが保証されています。

1. 各ノードは赤または黒色
2. ルートノードの色は黒色
3. すべての葉は黒色
4. あるノードが赤色であればその子ノードは黒色
5. あるノードからその子孫に対する経路について、その経路に含まれる黒色のノードの数が同数である。

実際に実装してみたのがこちらになります。

https://gist.github.com/siman-man/a8ed58effeaaf59855deac490574760c

実際に速度を測ってみます。

require 'benchmark'

rbt = RedBlackTree.new

nums = (1..1000).to_a

puts Benchmark.measure { nums.shuffle.each { |n| rbt.insert(n) } }
puts Benchmark.measure { nums.each { |n| rbt.insert(n) } }

結果

$ ruby red-black-tree.rb
  0.005910   0.000016   0.005926 (  0.005923)
  0.005540   0.000009   0.005549 (  0.005549)

このように偏った入力についても実行時間が遅くならないことが確認出来ました。

おわりに

前々から実装しようと思っていたので実装できる良い機会でした。（思った以上に実装量が多かった）

本当は定数名に NUL じゃなくて NIL を使おうと思ったのですが ruby 側で定義されていたのでそれは避けました（deprecated みたいなので将来的に無くなるとは思いますが）

今後も色々とアルゴリズムの実装をしていきたいと思います。（競プロ用のライブラリ整備）

参考文献

実装と詳細については「アルゴリズムイントロダクション 第3版」を参考にしました。

• https://www.amazon.co.jp/dp/476490408X