Tociyuki::Diary RSSフィード

tociyuki による Perl・Ruby・C++・C で書き散らしたコードを中心に、日常雑記も混在 : B  F  twitter  GitHub  CPAN  本館  公開鍵
 

2016年12月07日

[]MurmurHash3 32 ビット char const* 用

今度は char const* 用の関数を作ります。

std::uint32_t murmurhash3_32 (std::size_t const len, char const* const str, std::uint32_t const seed = 0);

昨日の MurmurHash3 32 ビット版は std::string の文字列本体がほとんどの場合 4 バイト・アラインメントされていることを利用して、 ブロックの読み出しを楽にしていました。 4 バイト・アラインメントになっているときは、 同じやりかたで計算します。

// リトル・エンディアンで 4 バイト・アラインメントされた str
uint32_t
murmurhash3_32le_align (std::size_t const len, char const* const str, std::uint32_t const seed)
{
    union {
        std::uint8_t const* p8;
        std::uint32_t const* p32;
        char const* str;
    } s;

    s.str = str;
    std::size_t const count32 = len / 4U;
    std::size_t const tail = len - count32 * 4U;
    std::uint32_t hash = seed;
    for (std::size_t i = 0; i < count32; ++i) {
        hash = murmurhash3_32block (hash, *s.p32++);
    }
    if (tail > 0) {
        std::uint32_t k = read_partial_bytes (s.p8, tail);
        hash = murmurhash3_32mix (hash, k);
    }
    return murmurhash3_32padding (hash, len);
}

ワード読み出しをバイト・スワップするとビッグ・エンディアン用になります。

// ビッグ・エンディアンで 4 バイト・アラインメントされた str
uint32_t
murmurhash3_32be_align (std::size_t const len, char const* const str, std::uint32_t const seed)
{
    // 省略 (リトル・エンディアン murmurhash3_32le_align と同じ)
    for (std::size_t i = 0; i < count32; ++i) {
        hash = murmurhash3_32block (hash, byteswap32 (*s.p32++));
    }
    // 省略 (同上)
}

一般の char const* では、 4 バイト・アラインメントになっていないときがあります。

速度重視の実装なら、 ワード読み出しにこだわることになります。 その場合、 ワード単位で読んだものと欲しいブロックのバイトがずれることがあるので、 バッファリングとバイト・シフトでブロックを組み立ていきます。 例えば、 下の場合では、 先頭 2 バイトをバイト単位で読むと、 次からは 4 バイト・アラインメントでワード読み出しができるので、 3 回ワード単位で読みます。 その後、 残りの 3 バイトをバイト読み出します。 先頭の 2 バイト分がワード読み出しとブロックのずれになります。

    アドレス
    843c6672 'H' バイト読み出し  block[0]  0ビット目の桁
    843c6673 'e' バイト読み出し  block[0]  8ビット目の桁
    843c6674 'l' ワード読み出し  block[0] 16ビット目の桁 lower_shift==16ビット
    843c6675 'l' ↓              block[0] 24ビット目の桁
    843c6676 'o' ↓              block[1]  0ビット目の桁 upper_shift==16ビット
    843c6677 ' ' ↓              block[1]  8ビット目の桁
    843c6678 'M' ワード読み出し  block[1] 16ビット目の桁 lower_shift==16ビット
    843c6679 'u' ↓              block[1] 24ビット目の桁
    843c667a 'r' ↓              block[2]
    843c667b 'm' ↓              block[2]
    843c667c 'u' ワード読み出し  block[2]
    843c667d 'r' ↓              block[2]
    843c667e 'H' ↓              block[3]
    843c667f 'a' ↓              block[3]
    843c6680 's' バイト読み出し  block[3]
    843c6681 'h' バイト読み出し  block[3]
    843c6682 '3' バイト読み出し  block[4]
    843c6683 '\0'

この例のように、 文字列ポインタの指すアドレスから、 ワード読み出しする最初のアドレスまでのバイトアドレスのずれ byteoff を計算すれば、 先頭のバイト読み出し回数 head、 ワード読み出し回数 count32、 末尾のバイト読み出し回数 tail を求めることができます。 なお、 ポインタの指すアドレスを整数演算しなければならないため、 union 型を使って型検査をごまかすことにします。

lower_shift はリトル・エンディアンで読んだワードの下位をブロックへ補充するためのビット・シフト量です。 upper_shift はワードの上位を次のブロックへ格納するビット・シフト量です。 両方とも、 head から算出できます。

//  0123012301230123012301230123
//  c___^___^___^___^___^000....    head==1 count32==5 tail==0
//  c___^___^___^___^___^c00....    head==1 count32==5 tail==1
//  c___^___^___^___^___^cc0....    head==1 count32==5 tail==2
//  c___^___^___^___^___^ccc....    head==1 count32==5 tail==3
//  cc__^^__^^__^^__^^__^^00....    head==2 count32==5 tail==0
//  cc__^^__^^__^^__^^__^^c0....    head==2 count32==5 tail==1
//  cc__^^__^^__^^__^^__^^cc....    head==2 count32==5 tail==2
//  cc__^^__^^__^^__^^__^^ccc000    head==2 count32==5 tail==3
//  ccc_^^^_^^^_^^^_^^^_^^^0....    head==3 count32==5 tail==0
//  ccc_^^^_^^^_^^^_^^^_^^^c....    head==3 count32==5 tail==1
//  ccc_^^^_^^^_^^^_^^^_^^^cc000    head==3 count32==5 tail==2
//  ccc_^^^_^^^_^^^_^^^_^^^ccc00    head==3 count32==5 tail==3
//
//  _ lower_shift, ^ upper_shift, c load uint8_t, 0 zero padding

// リトル・エンディアンで 4 バイト・アラインメントされていない str
uint32_t
murmurhash3_32le_unalign (std::size_t const len, char const* const str, std::uint32_t const seed)
{
    union {
        std::uint8_t const* p8;
        std::uint32_t const* p32;
        char const* str;
        std::uintptr_t i;
    } s;

    s.str = str;
    std::size_t const byteoff = (4U - (s.i & 3U)) & 3U;
    std::size_t const head = byteoff < len ? byteoff : len;
    std::size_t const count32 = (len - head) / 4U;
    std::size_t const tail = len - head - count32 * 4U;
    int const lower_shift = head * 8;
    int const upper_shift = 32 - lower_shift;

    std::uint32_t hash = seed;
    std::uint32_t k = read_partial_bytes (s.p8, head);
    s.p8 += head;
    for (std::size_t i = 0; i < count32; ++i) {
        uint32_t const w = *s.p32++;
        k |= w << lower_shift;
        hash = murmurhash3_32block (hash, k);
        k = w >> upper_shift;
    }
    std::uint32_t v = read_partial_bytes (s.p8, tail);
    k |= v << lower_shift;
    v >>= upper_shift;
    hash = murmurhash3_32mix_unalign (hash, k, v, head + tail);
    return murmurhash3_32padding (hash, len);
}

ビッグ・エンディアン用で、 ワードを読み取ってバイト・スワップするのは同じです。

// ビッグ・エンディアンで 4 バイト・アラインメントされていない str
uint32_t
murmurhash3_32be_unalign (std::size_t const len, char const* const str, std::uint32_t const seed)
{
    // 省略 (リトル・エンディアン murmurhash3_32le_unalign と同じ)
    for (std::size_t i = 0; i < count32; ++i) {
        uint32_t const w = byteswap32 (*s.p32++);
        k |= w << lower_shift;
        hash = murmurhash3_32block (hash, k);
        k = w >> upper_shift;
    }
    // 省略 (同上)
}

上記のブロックの組み立て例のように、 末尾の扱いは tail バイト数だけでなく、 head バイト数も勘定にいれて、 最後のブロックを閉じて、 余りのバイト列をハッシュへ加えます。

// 末尾のバイト列をハッシュへ加えます
static inline uint32_t
murmurhash3_32mix_unalign (std::uint32_t hash, std::uint32_t k, uint32_t v, std::size_t rem_bytes)
{
    // rem_bytes == head + tail
    if (rem_bytes == 4) {
        hash = murmurhash3_32block (hash, k);
    }
    else if (rem_bytes > 4) {
        hash = murmurhash3_32block (hash, k);
        hash = murmurhash3_32mix (hash, v);
    }
    else if (rem_bytes > 0) {
        hash = murmurhash3_32mix (hash, k);
    }
    return hash;
}

ここまでの関数では 4 バイトより小さなバイト列を読み出すインライン関数を使っています。

static inline std::uint32_t
read_partial_bytes (std::uint8_t const* s, std::size_t const byte_count)
{
    std::uint32_t w = 0;
    switch (byte_count) {
    case 3:
        w |= s[2] << 16;
    case 2:
        w |= s[1] << 8;
    case 1:
        w |= s[0];
    }
    return w;
}

MurmurHash3 のそれぞれのブロックをハッシュへミキシングする操作はインライン関数へくくりだしておいたものを使います。

static inline std::uint32_t
murmurhash3_32block (std::uint32_t hash, std::uint32_t k)
{
    k *= 0xcc9e2d51LU;                  // C1
    k = (k << 15) | (k >> 17);          // R1==15
    k *= 0x1b873593LU;                  // C2
    hash ^= k;
    hash = (hash << 13) | (hash >> 19); // R2==13
    hash = hash * 5U + 0xe6546b64LU;
    return hash;
}

ブロック幅に満たない余りのバイト列のミキシング操作も同様にくくりだしています。

static inline std::uint32_t
murmurhash3_32mix (std::uint32_t hash, std::uint32_t k)
{
    k *= 0xcc9e2d51LU;                  // C1
    k = (k << 15) | (k >> 17);          // R1==15
    k *= 0x1b873593LU;                  // C2
    hash ^= k;
    return hash;
}

最後のパディング操作も同様です。

static inline std::uint32_t
murmurhash3_32padding (std::uint32_t hash, std::uint32_t len)
{
    hash ^= len;
    hash ^= hash >> 16;
    hash *= 0x85ebca6bLU;
    hash ^= hash >> 13;
    hash *= 0xc2b2ae35LU;
    hash ^= hash >> 16;
    return hash;
}

エントリ・ポイントではエンディアンとアラインメントをチェックして、 それぞれの関数を呼ぶようにします。

uint32_t
murmurhash3_32 (std::size_t const len, char const* const str, std::uint32_t const seed)
{
    static const std::uint32_t ck = 0x04030201LU;
    static const bool little_endian = *(reinterpret_cast<std::uint8_t const*> (&ck)) == 0x01U;

    union {
        char const* str;
        std::uintptr_t i;
    } s;

    s.str = str;
    if (little_endian) {
        if ((s.i & 3U) == 0) {
            return murmurhash3_32le_align (len, str, seed);
        }
        else {
            return murmurhash3_32le_unalign (len, str, seed);
        }
    }
    else {
        if ((s.i & 3U) == 0) {
            return murmurhash3_32be_align (len, str, seed);
        }
        else {
            return murmurhash3_32be_unalign (len, str, seed);
        }
    }
}

2016年12月06日

[]MurmurHash3 の 32 ビット版

MurmurHash3 の 32 ビット版を書いてみました。

// MurmurHash3 was written by Austin Appleby, and is placed in the public domain.

#include <cstdint>
#include <string>

uint32_t murmurhash3_32 (std::string const& str, std::uint32_t const seed = 0);

文字列を 4 オクテットのブロック列として、 それぞれのブロックをリトル・エンディアンで 32 ビット符号なし整数に読み取っていきます。 末尾でオクテットが足りないときはゼロ・パディングします。 最後に文字列長と定数をミキシングしてハッシュ値とします。 試しに、 リトル・エンディアンの x86 と、 ビッグ・エンディアンの power pc の両方でコンパイル & 実行し、 結果が同一になることを確認しています。

//@<byteswap32 インライン関数を定義します@>

std::uint32_t
murmurhash3_32 (std::string const& str, std::uint32_t const seed)
{
    enum { r1 = 15, r2 = 13 };
    static const std::uint32_t c1 = 0xcc9e2d51LU;
    static const std::uint32_t c2 = 0x1b873593LU;
    std::uint32_t hash = seed;
    std::uint32_t const len = str.size ();
    std::size_t const nblock = len / 4U;
    std::uint32_t const* s32 = reinterpret_cast<std::uint32_t const*> (&str[0]);

    std::size_t const nblock = len / 4U;
    std::uint32_t const* s32 = reinterpret_cast<std::uint32_t const*> (&str[0]);
    if (*(reinterpret_cast<std::uint8_t const*> (&c1)) == 0x51U) {
        for (std::size_t i = 0; i < nblock; ++i) {
            std::uint32_t k0 = *s32++;                 // リトル・エンディアン
            k0 *= c1;
            k0 = (k0 << r1) | (k0 >> (32 - r1));
            k0 *= c2;
            hash ^= k0;
            hash = (hash << r2) | (hash >> (32 - r2));
            hash = hash * 5U + 0xe6546b64LU;
        }
    }
    else {
        for (std::size_t i = 0; i < nblock; ++i) {
            std::uint32_t k0 = byteswap32 (*s32++);    // ビッグ・エンディアン
            k0 *= c1;
            k0 = (k0 << r1) | (k0 >> (32 - r1));
            k0 *= c2;
            hash ^= k0;
            hash = (hash << r2) | (hash >> (32 - r2));
            hash = hash * 5U + 0xe6546b64LU;
        }
    }

    std::uint8_t const* const s = reinterpret_cast<std::uint8_t const*> (s32);
    std::uint32_t k1 = 0;
    switch (len & 3U) {
    case 3:
        k1 ^= static_cast<unsigned char> (s[2]) << 16;
    case 2:
        k1 ^= static_cast<unsigned char> (s[1]) << 8;
    case 1:
        k1 ^= static_cast<unsigned char> (s[0]);
        k1 *= c1;
        k1 = (k1 << r1) | (k1 >> (32 - r1));
        k1 *= c2;
        hash ^= k1;
    }
    hash ^= len;
    hash ^= hash >> 16;
    hash *= 0x85ebca6bLU;
    hash ^= hash >> 13;
    hash *= 0xc2b2ae35LU;
    hash ^= hash >> 16;
    return hash;
}

上のコードは、 可搬性を重視して実行時にエンディアン判定をおこなって、 リトル・エンディアンのためのループと、 ビッグ・エンディアンのためのそれに条件分岐しています。 この 2 つのループは、 文字列から読み取るときにバイト・スワップをおこなうかどうかだけが異なっています。 賢いコンパイラなら、 繰り返し中に値が変化しない条件式がループ中に含まれていると、 上のコードのように条件文をくくりだす最適化をしてくれますが、 コンパイラの働きをあてにせずに手動で最適化をおこなっています。

//@<byteswap32 インライン関数を定義します@>=
#if defined(__GNUC__) && (__GNUC__ > 4 || (__GNUC__ == 4 && __GNUC__MINOR__ >= 3))
#define byteswap32(x) __builtin_bswap32(x)
#else
static inline std::uint32_t
byteswap32 (std::uint32_t x)
{
    x = ((x & 0x00ff00ffLU) << 8) | ((x & 0xff00ff00LU) >> 8);
    return (x << 16) | (x >> 16);
}
#endif

[][]Hash オブジェクトの内部データ構造が更新されていました

CRuby の開発リポジトリの trunk へ、 1 月間前の2016年11月7日にハッシュ法の新しい実装がマージされました。

CRuby trunk st.c ⇒ Introduce table improvement by Vladimir Makarov <vmakarov@redhat.com>. · ruby/ruby@7577515 · GitHub

開発ブランチ ⇒ GitHub - vnmakarov/ruby at hash_tables_with_open_addressing

オリジナルの st.c のハッシュ表はチェイン法で、 チェインの各エントリを小さなオブジェクトとして記憶割り当てするやりかたになっていました。 このエントリはハッシュ法のチェインとは独立にエントリの登録順に連なる双方向リストにもなっていました。 CRuby の Hash オブジェクトを inspect したり each でなぞると登録順に並ぶのはそのためです。

11月にマージされた新しい実装のソース・ファイル名は st.c のままで、 オリジナルのクレジットも残されていますが、 中身はアルゴリズムもデータ構造も一新されて別物になりました。 エントリは大きな配列ベクタに格納順に並べられて Array オブジェクトの内部配列に似た方式へ変わってます。 これは添字アクセスなしの push、 shift、 delete、 each が可能な Array の機能限定版のような感じですが、 途中のエントリを delete すると削除マークをエントリに書き込み、 each でスキップします。 エントリへの索引は、 オープン・アドレス法へアルゴリズムが変更になっています。

オープン・アドレス法は、 mruby の Hash オブジェクトの内部実装にも採用されていました。 ですが、 mruby ではオープン・アドレスのハッシュ表へ直接エントリを書き込んでおり、 エントリには登録順のリスト情報がなかったため、 each をおこなうと登録順ではなく、 ハッシュ表内での出現順でエントリをリストアップしていました。 mruby はフットプリントを抑えるために、 新しい st.c のハッシュ検索表と配列ベクタを組み合わせる方式へ今後変えるのかどうかわかりませんが、 可能性はありそうです。

2016年11月28日

[]非破壊操作型赤黒木の挿入と削除の手直し

以前書いた「非破壊操作型赤黒木の挿入と削除」はノード・オブジェクトを非破壊扱いにして挿入・削除をおこなった新しい赤黒木を作成するようにしましたが、 オブジェクトの生成と削除に無駄があるのが気になってきたので、 条件を緩めて元の木からコピーしたノード・オブジェクトを破壊的に修正するやりかたに手直しすることにします。

さらに、 手直しついでに、 キーと値のペアを赤黒木に登録できるようにします。

class RedBlacktree
  include Enumerable

  attr_reader :root

  def initialize(root = NULL)
    @root = root
  end

  def inspect() @root.inspect end

#@<NULL オブジェクトを定義します@>
#@<Node 構造体を定義します@>
#@<キー値のペアを登録順に列挙する each メソッドを定義します@>
#@<キー値を赤黒木に挿入した新しい木を作る insert メソッドを定義します@>
#@<キーに一致するキー値ペアを削除した新しい赤黒木を作る delete を定義します@>
end

赤黒木のノードと終端は、 赤か黒の 2 つの色を持ちます。 赤黒木はページ中のキーの個数が 1 個から 3 個 に限定した B 木と同等で、 黒に塗られたノードが B 木のページに相当し、 赤に塗られたノードは B 木のページ中の項目セルに相当します。 終端 NULL はページと同格なので色を黒に固定します。

#@<NULL オブジェクトを定義します@>=
  NULL = Object.new
  def NULL.color() :black end
  def NULL.null?() true end
  def NULL.black?() true end
  def NULL.red?() false end
  def NULL.inspect() 'null' end
  NULL.freeze

赤色ノードと黒色ノードは同じ構造体に格納し、 色フィールドで区別を付けます。 ノードの色の塗り替えを頻繁におこなうため、 色ごとに別の構造体にしてしまって色の塗り替えごとに全フィールドのコピーが発生するのを防ぐため、 そうします。 色の塗り替えメソッドには感嘆符付きの破壊操作版と感嘆符なしの非破壊操作版の 2 種類を定義して使い分けます。

#@<Node 構造体を定義します@>=
  class Node
    attr_accessor :color, :left, :key, :value, :right
    def self.black(left, key, value, right) new(:black, left, key, value, right) end
    def self.red(left, key, value, right) new(:red, left, key, value, right) end

    def initialize(color, left, key, value, right)
      @color, @left, @key, @value, @right = color, left, key, value, right
    end

    def replace(node)    #+ 追加
      @color, @left, @key, @value, @right = node.color, node.left, node.key, node.value, node.right
      self
    end

    def null?() false end
    def black?() @color == :black end
    def red?() @color == :red end
    def paint_black!() @color = :black end
    def paint_red!() @color = :red end

    def paint_black()
      if @color == :black
        self
      else
        Node.new(:black, @left, @key, @value, @right)
      end
    end

    def paint_red()
      if @color == :red
        self
      else
        Node.new(:red, @left, @key, @value, @right)
      end
    end

    def inspect
      if @color == :black
        "[#{@left.inspect} #{@key.inspect},#{@value.inspect} #{@right.inspect}]"
      else
        "(#{@left.inspect} #{@key.inspect},#{@value.inspect} #{@right.inspect})"
      end
    end
  end

each メソッドは、 ノードの色を区別せずに二分探索木として全ノードを行きがけ順に訪れて、 キーと値のペアを渡す内部イテレータにしています。

#@<キー値のペアを登録順に列挙する each メソッドを定義します@>=
  def each
    return to_enum(:each) if not block_given? and respond_to?(:to_enum)
    path = []
    node = @root
    while true
      if not node.null?
        while not node.left.null?
          path.push node
          node = node.left
        end
      elsif path.empty?
        break
      else
        node = path.pop
      end
      yield [node.key, node.value]
      node = node.right
    end
    self
  end

insert メソッドは、 レシーバの赤黒木にキー値ペアを挿入した新しい木を作って返します。 すべてのノードをコピーするのではなく、 変更が必要なノードだけが新しく生成され、 それ以外の未変更のノードは元の木と挿入後の木で共用します。 このメソッドは 2 つの while からできています。 最初のループで根から葉へキーを探して降っていきます。 キーに一致するノードに辿りついたときは、 値を変更したノードを作って while ループを抜けます。 一致するノードがないときは葉まで降りていって、 キー値ペアを格納する新しいノードを作って while ループを抜けます。 次のループでは、 根へ向かって最初のループで降りてきたノードを逆に辿って戻っていきます。 戻っていく過程で、 ノードを新しく作りつつ、 バランスが崩れるときは調整をしていきます。 最後に根まで戻ったら、 新しい赤黒木の根が手に入るので、 それを使って木を作成して返します。

#@<キー値を赤黒木に挿入した新しい木を作る insert メソッドを定義します@>=
  def insert(key, value)
    if @root.null?
      return self.class.new(Node.black(NULL, key, value, NULL))
    end
    path = []
    node = @root
    while true
      path.push node
      if key == node.key
        return self if value == node.value
        child = node.left
        node = Node.new(node.color, child, key, value, node.right)
        break
      elsif key < node.key
        if node.left.null?
          child = Node.red(NULL, key, value, NULL)
          node = Node.new(node.color, child, node.key, node.value, node.right)
          break
        end
        node = node.left
      else
        if node.right.null?
          child = Node.red(NULL, key, value, NULL)
          node = Node.new(node.color, node.left, node.key, node.value, child)
          break
        end
        node = node.right
      end
    end
    while not path.empty?
      original_node = path.pop
      break if path.empty?
      original_parent = path.last
      parent = original_parent.dup
      if original_node.equal?(original_parent.left)
        parent.left = node
        if child.red? and node.red?
          balance_left_insert(child, node, parent)
        end
      else
        parent.right = node
        if child.red? and node.red?
          balance_right_insert(child, node, parent)
        end
      end
      child = node
      node = parent
    end
    if node.red?
      node.paint_black!    #! 修正
    end
    return self.class.new(node)
  end

#@<ノードの左側の子ノードがバランスが崩れているのを調整します@>
#@<ノードの右側の子ノードがバランスが崩れているのを調整します@>
#@<2 つのノードのキーと値だけを交換します@>

赤色ノードに直に他の赤色ノードがつながっていると挿入によるバランス崩れが生じています。 左右それぞれで、 ページ中のセルがあふれているとき、 ページ中の左右のバランスだけが崩れているときで、 3 通りの崩れかたがあります。 あふれているときは、 ページ分割をおこなうのですが、 赤黒木では単純に色を塗り替えるだけでページ分割ができてしまいます。

バランス調整時には、 親ノード、 注目ノード、 子ノードの 3 つのノードの内容を書き換えます。 これら 3 つはすべて新しく生成されたノードであることが保証されるため、 書き換えても、 元の木に影響が及びません。

#@<ノードの左側の子ノードがバランスが崩れているのを調整します@>=
  def balance_left_insert(child, node, parent)
    if parent.right.red?
      # セルがあふれているので分割します
      parent.paint_red!                        #! 修正
      parent.left.paint_black!                 #! 修正
      parent.right = parent.right.paint_black  #! 修正
    elsif child.equal?(node.left)
      # 左側のさらに左側に伸びて左右のバランスが崩れているのを調整します
      node.left = node.right
      node.right = parent.right
      parent.left = child
      parent.right = node
      swap_key_value(node, parent)
    else
      # 左側の右側に伸びて左右のバランスが崩れているのを調整します
      node.right = child.left
      child.left = child.right
      child.right = parent.right
      parent.right = child
      swap_key_value(child, parent)
    end
  end

右側のバランスが崩れているときも、 左側の場合から左右対称でバランスを調整します。

#@<ノードの右側の子ノードがバランスが崩れているのを調整します@>=
  def balance_right_insert(child, node, parent)
    if parent.left.red?
      parent.paint_red!                        #! 修正
      parent.left = parent.left.paint_black    #! 修正
      parent.right.paint_black!                #! 修正
    elsif child.equal?(node.left)
      node.left = child.right
      child.right = child.left
      child.left = parent.left
      parent.left = child
      swap_key_value(child, parent)
    else
      node.right = node.left
      node.left = parent.left
      parent.right = child
      parent.left = node
      swap_key_value(node, parent)
    end
  end

バランス調整時に、 2 つのノードのキーと値を交換する必要があるので、 そのためのメソッドを定義します。

#@<2 つのノードのキーと値だけを交換します@>=
  def swap_key_value(node0, node1)
    tmpk = node0.key
    node0.key = node1.key
    node1.key = tmpk
    tmpv = node0.value
    node0.value = node1.value
    node1.value = tmpv
  end

挿入は以上です。

今度は、 元の赤黒木から指定したキーをもつノードを削除した新しい木を作る delete メソッドを定義します。 2つの while からなるのは挿入と同じですが、 挿入とは異なり、 削除では必ず葉まで降ります。 途中にキーに一致するノードを通過する場合に、 そのノードを入れている path の場所を just に記録しておきます。 削除のバランス調整は、 挿入よりも場合分けが多くなります。 バランス調整中では、 node の下の黒ノードの深さが一段減っており、 node の親である parent の他のノードの配置を組みかえて、 node を含めて同じ黒ノードの深さになるように変更を試みます。 parent 中の他のノードの個数が足りないときは、 配置を組みかえても黒ノードの深さが相変わらず一段少ないままになるときがあり、 そのときは、 さらに親側でバランス調整をおこなっていきます。

#@<キーに一致するキー値ペアを削除した新しい赤黒木を作る delete を定義します@>=
  def delete(key)
    return self if @root.null?
    path = []
    just = nil
    node = @root
    while true
      if key == node.key
        just = path.size
      end
      parent = node
      if key <= node.key
        break if node.left.null?
        node = node.left
      else
        break if node.right.null?
        node = node.right
      end
      path.push parent
    end
    return self if just.nil?
    leaf = node
    original_node = node
    node = if node.right.null? then node.left else node.right end
    if path.empty?
      return self.class.new(node.paint_black)   #! 修正
    end
    balanced = false
    if original_node.red?
      balanced = true
    elsif node.red?
      node = node.paint_black                   #! 修正
      balanced = true
    end
    while not path.empty?
      original_parent = path.pop
      parent = original_parent.dup
      if just == path.size
        parent.key = leaf.key
        parent.value = leaf.value
      end
      if original_node.equal?(original_parent.left)
        parent.left = node
        if not balanced
          balanced = balance_left_delete(parent)
        end
      else
        parent.right = node
        if not balanced
          balanced = balance_right_delete(parent)
        end
      end
      node = parent
      original_node = original_parent
    end
    if node.red?
      node.paint_black!                         #! 修正
    end
    self.class.new(node)
  end

#@<parent の左側が右側よりも一段減っているとき右側からノードをとって深さを揃えます@>
#@<parent の右側が左側よりも一段減っているとき左側からノードをとって深さを揃えます@>

新しい木の parent の左側が右側よりも黒ノードの深さが一段減ってバランスが崩れているとき、 古い木の右側の黒い sibling を使って黒ノードの深さを揃えます。 揃え方の最初の場合は、 sibling に黒ノードが 2 つしかないときで、 sibling を赤ノードに塗り替えることで右側の黒ノードの深さを一段減らした上で parent を黒ノードにして一段深くします。 他の場合は sibling に 3 つか 4 つ の黒ノードがある場合で、 その 1 つか 2 つと parent の左側で新しい黒ノードを作り、 残りの 2 つで別の黒ノードを作って parent の両側にぶらさげて左右の黒ノードの深さを同じにします。

#@<parent の左側が右側よりも一段減っているとき右側からノードをとって深さを揃えます@>=
  def balance_left_delete(parent)
    sibling = parent.right
    if parent.black? and sibling.left.black? and sibling.black? and sibling.right.black?
      parent.right = sibling.paint_red
      return false
    elsif sibling.black?
      balance_left_node_delete(parent, sibling)
    else
      node = parent.paint_red               # この場合の parent は黒ノードなので必ず複製される
      parent.replace(sibling).paint_black!
      parent.left = balance_left_node_delete(node, sibling.left)     # sibling.left は黒ノード
    end
    true
  end

  def balance_left_node_delete(parent)
    sibling = parent.left
    if sibling.left.black? and sibling.right.black?
      parent.paint_black!                       #! 修正
      parent.right = sibling.paint_red          #! 修正
    elsif sibling.left.red? and sibling.right.black?
      sleft = sibling.left
      parent.left = Node.black(parent.left, parent.key, parent.value, sleft.left)
      parent.right = Node.black(sleft.right, sibling.key, sibling.value, sibling.right)
      parent.key = sleft.key
      parent.value = sleft.value
    else
      parent.left = Node.black(parent.left, parent.key, parent.value, sibling.left)
      parent.right = sibling.right.paint_black  #! 修正
      parent.key = sibling.key
      parent.value = sibling.value
    end
    parent
  end

上とは逆に parent の右側の黒ノードの深さが一段少ないときは、 左右を逆にひっくりかえして同じ処理をおこないます。

#@<parent の右側が左側よりも一段減っているとき左側からノードをとって深さを揃えます@>=
  def balance_right_delete(parent, sibling)
    if parent.black? and sibling.left.black? and sibling.black? and sibling.right.black?
      parent.left = sibling.paint_red
      return false
    elsif sibling.black?
      balance_right_node_delete(sibling, parent)
    else
      node = parent.paint_red
      parent.replace(sibling).paint_black!
      parent.right = balance_right_node_delete(sibling.right, node)
    end
    true
  end

  def balance_right_node_delete(sibling, parent)
    if sibling.left.black? and sibling.right.black?
      parent.paint_black!                       #! 修正
      parent.left = sibling.paint_red           #! 修正
    elsif sibling.left.black? and sibling.right.red?
      sright = sibling.right
      parent.left = Node.black(sibling.left, sibling.key, sibling.value, sright.left)
      parent.right = Node.black(sright.right, parent.key, parent.value, parent.right)
      parent.key = sright.key
      parent.value = sright.value
    else
      parent.left = sibling.left.paint_black    #! 修正
      parent.right = Node.black(sibling.right, parent.key, parent.value, parent.right)
      parent.key = sibling.key
      parent.value = sibling.value
    end
    parent
  end