M.Hiroi's Home Page

お気楽 Ruby プログラミング入門

番外編 : コレクションクラス

[ PrevPage | R u b y | NextPage ]

コレクションクラス [2]


●ハッシュ法

ハッシュ法 (hashing) は高速なデータ検索アルゴリズムです。ハッシュ法はハッシュ表 (hash table) と呼ばれるデータを格納する配列と、データを数値に変換するハッシュ関数 (hash function) を用意します。たとえば、ハッシュ表の大きさを N とすると、ハッシュ関数はデータを 0 から N - 1 までの整数値に変換します。この値をハッシュ値 (hash value) と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める探索方法がハッシュ法なのです。

ハッシュ法で不特定多数のデータを扱う場合、異なるデータでも同じハッシュ値が生成される可能性があります。これをハッシュ値の衝突といいます。つまり、データをハッシュ表に登録しようとしても、すでに先客が居座っているわけです。この場合、2 種類の解決方法があります。

第 1 の方法はハッシュ表に複数のデータを格納することです。配列にはひとつのデータしか格納できないので、複数個のデータをまとめて格納する工夫が必要になります。このときよく利用されるデータ構造が連結リストです。ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されているリストの中からデータを探索します。これをチェイン法といいます。

第 2 の方法は空いている場所を探して、そこにデータを入れる方法です。新しい場所を探すといっても、ハッシュ表の先頭から線形探索するのではなく、最初とは違うハッシュ関数を用意して、新しくハッシュ値を計算させて場所を決めます。これを空いている場所が見つかるまで繰り返します。これをオープンアドレス法といいます。

Ruby にはクラス Hash が用意されているので、私たちがハッシュを実装する必要はありませんが、アルゴリズムのお勉強ということで、あえてプログラムを作ってみましょう。アルゴリズムの詳しい説明は拙作のページ Algorithms with Python: ハッシュ法 をお読みくださいませ。

●仕様

●テストプログラム

リスト : 簡単なテスト

def test1(dic)
  a = ["foo", "bar", "baz", "oops"]
  b = ["Foo", "Bar", "Baz", "Oops"]
  printf "dic.empty? => %s\n", dic.empty?
  printf "dic.size => %s\n", dic.size
  a.each{|x|
    v = rand(100)
    printf "dic[%s] = %d\n", x, v
    dic[x] = v
  }
  printf "dic.empty? => %s\n", dic.empty?
  printf "dic.size => %s\n", dic.size
  (a + b).each{|x|
    printf "dic[%s] => %p\n", x, dic[x]
    printf "dic.member?(%s) => %s\n", x, dic.member?(x)
  }
  print "dic.each{|x| ...}", "\n"
  dic.each{|xs| print xs, "\n"}
  a.each{|x|
    printf "dic[%s] *= 10, ", x
    dic[x] *= 10
    printf "dic[%s] => %d\n", x, dic[x]
  }
  a.each{|x|
    printf "dic.delete(%s) => %d\n", x, dic.delete(x)
    printf "empty? => %s\n", dic.empty?
    printf "size => %s\n", dic.size
    printf "dic.member?(%s) => %s\n", x, dic.member?(x)
  }
end

def test2(nums, dic)
  for n in nums
    b = (1..n).to_a.shuffle
    printf "%6d ", n
    s = Time.now
    b.each{|x| dic[x] = true}
    e = Time.now
    printf ": %.3f ", e - s
    s = Time.now
    (1..n).each{|x| raise "search error" if !dic[x]}
    e = Time.now
    printf ": %.3f ", e - s
    s = Time.now
    (1..n).each{|x| raise "delete error" if !dic.delete(x)}
    e = Time.now
    printf ": %.3f \n", e - s
  end
end

●実行例1 (チェイン法)

irb> test1(Hash1.new)
dic.empty? => true
dic.size => 0
dic[foo] = 45
dic[bar] = 18
dic[baz] = 50
dic[oops] = 50
dic.empty? => false
dic.size => 4
dic[foo] => 45
dic.member?(foo) => true
dic[bar] => 18
dic.member?(bar) => true
dic[baz] => 50
dic.member?(baz) => true
dic[oops] => 50
dic.member?(oops) => true
dic[Foo] => nil
dic.member?(Foo) => false
dic[Bar] => nil
dic.member?(Bar) => false
dic[Baz] => nil
dic.member?(Baz) => false
dic[Oops] => nil
dic.member?(Oops) => false
dic.each{|x| ...}
["oops", 50]
["bar", 18]
["baz", 50]
["foo", 45]
dic[foo] *= 10, dic[foo] => 450
dic[bar] *= 10, dic[bar] => 180
dic[baz] *= 10, dic[baz] => 500
dic[oops] *= 10, dic[oops] => 500
dic.delete(foo) => 450
empty? => false
size => 3
dic.member?(foo) => false
dic.delete(bar) => 180
empty? => false
size => 2
dic.member?(bar) => false
dic.delete(baz) => 500
empty? => false
size => 1
dic.member?(baz) => false
dic.delete(oops) => 500
empty? => true
size => 0
dic.member?(oops) => false
=> ["foo", "bar", "baz", "oops"]

●プログラム1

#
# hash1.rb : チェイン法
#
#            Copyright (C) 2023 Makoto Hiroi
#
require './dlist'

# 素数 8191, 99991
class Hash1
  include Enumerable
  attr_reader :size

  def initialize(size = 8191)
    @hash_table = Array.new(size)
    @hash_size = size
    @size = 0
  end

  private
  # ハッシュ関数(Object#hash を使用する)
  def hash_func(key)
    key.hash.abs % @hash_size
  end

  public
  # 探索 (等値の判定は eql? を使う)
  def [](key)
    idx = hash_func(key)
    ds = @hash_table[idx]
    if ds
      ds.each {|xs|
        return xs[1] if xs[0].eql?(key)
      }
    end
    nil
  end

  def member?(key)
    self[key] ? true : false
  end

  # 挿入
  def []=(key, val)
    return nil if key == nil || val == nil
    idx = hash_func(key)
    ds = @hash_table[idx]
    if ds
      ds.each {|xs|
        if xs[0].eql?(key)
          xs[1] = val
          return val
        end
      }
      ds.insert(-1, [key, val])
    else
      @hash_table[idx] = DList.new([key, val])
    end
    @size += 1
    val
  end

  def insert(key, data)
    self[key] = data
  end

  # 削除
  def delete(key)
    ds = @hash_table[hash_func(key)]
    data = nil
    ds.delete_if {|xs|
      if xs[0].eql?(key)
        @size -= 1
        data = xs[1]
        true
      else
        false
      end
    }
    data
  end

  # ハッシュは空か?
  def empty?
    @size == 0
  end

  # Enumerable 用
  def each
    @hash_table.each {|ds|
      ds.each {|xs| yield xs.dup} if ds
    }
    self
  end

  def inspect
    sprintf("#<Hash1:%#x>", self.object_id)
  end
end

●実行例2 (オープンアドレス法)

irb> test1(Hash2.new)
dic.empty? => true
dic.size => 0
dic[foo] = 73
dic[bar] = 75
dic[baz] = 50
dic[oops] = 63
dic.empty? => false
dic.size => 4
dic[foo] => 73
dic.member?(foo) => true
dic[bar] => 75
dic.member?(bar) => true
dic[baz] => 50
dic.member?(baz) => true
dic[oops] => 63
dic.member?(oops) => true
dic[Foo] => nil
dic.member?(Foo) => false
dic[Bar] => nil
dic.member?(Bar) => false
dic[Baz] => nil
dic.member?(Baz) => false
dic[Oops] => nil
dic.member?(Oops) => false
dic.each{|x| ...}
["oops", 63]
["bar", 75]
["baz", 50]
["foo", 73]
dic[foo] *= 10, dic[foo] => 730
dic[bar] *= 10, dic[bar] => 750
dic[baz] *= 10, dic[baz] => 500
dic[oops] *= 10, dic[oops] => 630
dic.delete(foo) => 730
empty? => false
size => 3
dic.member?(foo) => false
dic.delete(bar) => 750
empty? => false
size => 2
dic.member?(bar) => false
dic.delete(baz) => 500
empty? => false
size => 1
dic.member?(baz) => false
dic.delete(oops) => 630
empty? => true
size => 0
dic.member?(oops) => false
=> ["foo", "bar", "baz", "oops"]

●実行例3

irb> test2([10000, 20000, 40000, 80000], Hash1.new(99991))
 10000 : 0.025 : 0.010 : 0.006
 20000 : 0.039 : 0.016 : 0.014
 40000 : 0.095 : 0.029 : 0.033
 80000 : 0.139 : 0.127 : 0.068
=> [10000, 20000, 40000, 80000]

irb(main):006:0> test2([10000, 20000, 40000, 80000], Hash2.new(99991))
 10000 : 0.004 : 0.005 : 0.003
 20000 : 0.009 : 0.007 : 0.009
 40000 : 0.024 : 0.020 : 0.018
 80000 : 0.125 : 0.081 : 0.067
=> [10000, 20000, 40000, 80000]

irb> test2([10000, 20000, 40000, 80000], {})
 10000 : 0.002 : 0.001 : 0.001
 20000 : 0.003 : 0.002 : 0.003
 40000 : 0.007 : 0.005 : 0.009
 80000 : 0.017 : 0.017 : 0.017
=> [10000, 20000, 40000, 80000]

実行環境 : Ruby 3.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz

●プログラム2

# coding: utf-8
#
# hash2.rb : オープンアドレス法
#
#            Copyright (C) 2006-2023 Makoto Hiroi
#

# 素数 8191, 99991
class Hash2
  include Enumerable
  attr_reader :size

  # :_my_hash_empty  空き
  # :_my_hash_delete 削除
  def initialize(size = 8191)
    @hash_key_table = Array.new(size, :_my_hash_empty)
    @hash_data_table = Array.new(size)
    @hash_size = size
    @size = 0
  end

  private
  # ハッシュ関数 (Object#hash を使う)
  def hash_func(key)
    key.hash.abs % @hash_size
  end

  # 再ハッシュ (1 次ハッシュ法)
  def next_func(value)
    (value + 1) % @hash_size
  end

  public
  # 探索
  def [](key)
    idx = hash_func(key)
    cnt = 0
    begin
      key1 = @hash_key_table[idx]
      if key.eql? key1
        return @hash_data_table[idx]
      elsif key1 == :_my_hash_empty
        break
      end
      idx = next_func(idx)
      cnt += 1
    end while cnt < @hash_size
    nil
  end

  def member?(key)
    self[key] ? true : false
  end

  # 挿入
  def []=(key, data)
    idx = hash_func(key)
    cnt = 0
    begin
      key1 = @hash_key_table[idx]
      if key.eql? key1
        @hash_data_table[idx] = data
        return data
      elsif key1 == :_my_hash_empty || key1 == :_my_hash_delete
        @hash_key_table[idx] = key
        @hash_data_table[idx] = data
        @size += 1
        return data
      end
      cnt += 1
      idx = next_func(idx)
    end while cnt < @hash_size
    nil
  end

  def insert(key, data)
    self[key] = data
  end

  # 削除
  def delete(key)
    idx = hash_func(key)
    cnt = 0
    begin
      key1 = @hash_key_table[idx]
      if key.eql? key1
        @hash_key_table[idx] = :_my_hash_delete
        @size -= 1
        return @hash_data_table[idx]
      elsif key1 == :_my_hash_empty
        return nil
      end
      idx = next_func(idx)
      cnt += 1
    end while cnt < @hash_size
    nil
  end

  # Enumerable 用
  def each
    @hash_key_table.each_with_index {|key, idx|
      if key != :_my_hash_empty && key != :_my_hash_delete
        yield [key, @hash_data_table[idx]]
      end
    }
    self
  end

  # ハッシュは空か?
  def empty?
    @size == 0
  end

  def inspect
    sprintf("#<Hash2:%#x>", self.object_id)
  end
end

●二分木

拙作のページ Ruby 入門第 13 回 二分木 で作成したプログラムを少し修正したものです。

●仕様

●木のテスト

リスト : 簡単な木のテスト

def test3(dic)
  a = (1..10).to_a.shuffle
  a.each{|x| dic[x] = true}
  printf "dic.empty? => %s\n", dic.empty?
  printf "dic.size => %s\n", dic.size
  printf "dic.max => %s\n", dic.max
  printf "dic.min => %s\n", dic.min
  printf "dic.delete_max => %s\n", dic.delete_max
  printf "dic.delete_min => %s\n", dic.delete_min
  printf "dic.max => %s\n", dic.max
  printf "dic.min => %s\n", dic.min
  printf "dic.empty? => %s\n", dic.empty?
  printf "dic.size => %s\n", dic.size
  4.times {
    printf "dic.delete_max => %s\n", dic.delete_max
    printf "dic.size => %s\n", dic.size
  }
  4.times {
    printf "dic.delete_min => %s\n", dic.delete_min
    printf "dic.size => %s\n", dic.size
  }
  printf "dic.empty? => %s\n", dic.empty?
end

●実行例

irb> test1(Tree.new)
dic.empty? => true
dic.size => 0
dic[foo] = 4
dic[bar] = 63
dic[baz] = 21
dic[oops] = 1
dic.empty? => false
dic.size => 4
dic[foo] => 4
dic.member?(foo) => true
dic[bar] => 63
dic.member?(bar) => true
dic[baz] => 21
dic.member?(baz) => true
dic[oops] => 1
dic.member?(oops) => true
dic[Foo] => nil
dic[Bar] => nil
dic.member?(Bar) => false
dic[Baz] => nil
dic.member?(Baz) => false
dic[Oops] => nil
dic.member?(Oops) => false
dic.each{|x| ...}
["bar", 63]
["baz", 21]
["foo", 4]
["oops", 1]
dic[foo] *= 10, dic[foo] => 40
dic[bar] *= 10, dic[bar] => 630
dic[baz] *= 10, dic[baz] => 210
dic[oops] *= 10, dic[oops] => 10
dic.delete(foo) => 40
empty? => false
size => 3
dic.member?(foo) => false
dic.delete(bar) => 630
empty? => false
size => 2
dic.member?(bar) => false
dic.delete(baz) => 210
empty? => false
size => 1
dic.member?(baz) => false
dic.delete(oops) => 10
empty? => true
size => 0
dic.member?(oops) => false
=> ["foo", "bar", "baz", "oops"]

irb> test3(Tree.new)
dic.empty? => false
dic.size => 10
dic.max => [10, true]
dic.min => [1, true]
dic.delete_max => [10, true]
dic.delete_min => [1, true]
dic.max => [9, true]
dic.min => [2, true]
dic.empty? => false
dic.size => 8
dic.delete_max => [9, true]
dic.size => 7
dic.delete_max => [8, true]
dic.size => 6
dic.delete_max => [7, true]
dic.size => 5
dic.delete_max => [6, true]
dic.size => 4
dic.delete_min => [2, true]
dic.size => 3
dic.delete_min => [3, true]
dic.size => 2
dic.delete_min => [4, true]
dic.size => 1
dic.delete_min => [5, true]
dic.size => 0
dic.empty? => true
=> nil

●プログラム

# coding: utf-8
#
# tree2.rb : 二分探索木
#
#            Copyright (C) 2023 Makoto Hiroi
#

# 二分探索木
class Tree
  include Enumerable
  attr_reader :size

  # 節の定義
  class Node
    def initialize(key, data)
      @key = key
      @data = data
      @left = nil
      @right = nil
    end
    attr_accessor :key, :data, :left, :right
  end

  def initialize
    @root = nil
    @size = 0
  end

  # 操作関数
  private
  # 探索
  def search_node(node, key)
    while node
      if key == node.key
        return node.data
      elsif key < node.key
        node = node.left
      else
        node = node.right
      end
    end
  end

  # 挿入
  def insert_node(node, key, data)
    if node == nil
      return Node.new(key, data), true
    elsif key == node.key
      node.data = data
      return node, false
    elsif key < node.key
      node.left, r = insert_node(node.left, key, data)
    else
      node.right, r = insert_node(node.right, key, data)
    end
    return node, r
  end

  # 最小値を探す
  def search_min_node(node)
    node = node.left while node.left
    return node.key, node.data
  end

  # 最大値を探す
  def search_max_node(node)
    node = node.right while node.right
    return node.key, node.data
  end

  # 最小値を削除する
  def delete_min_node(node)
    return node.right, node unless node.left
    node.left, data = delete_min_node(node.left)
    return node, data
  end

  # 最大値を削除する
  def delete_max_node(node)
    return node.left, node unless node.right
    node.right, data = delete_max_node(node.right)
    return node, data
  end

  # 削除
  def delete_node(node, key)
    if node
      if key == node.key
        return node.right, node.data if !node.left
        return node.left, node.data if !node.right
        data = node.data
        node.key, node.data = search_min_node(node.right)
        node.right, _ = delete_min_node(node.right)
      elsif key < node.key
        node.left, data = delete_node(node.left, key)
      else
        node.right, data = delete_node(node.right, key)
      end
      return node, data
    else
      return node, nil
    end
  end

  # 巡回
  def traverse_node(node, &func)
    if node
      traverse_node(node.left, &func)
      func.call([node.key, node.data])
      traverse_node(node.right, &func)
    end
  end

  # 公開メソッド
  public
  # 空の木?
  def empty?
    @root == nil
  end

  # 探索
  def [](key)
    search_node(@root, key)
  end

  def member?(key)
    self[key] ? true : false
  end

  # 最小値を求める
  def min
    search_min_node(@root) if !empty?
  end

  # 最大値を求める
  def max
    search_max_node(@root) if !empty?
  end

  # 挿入
  def []=(key, value)
    return nil if key == nil || value == nil
    @root, r = insert_node(@root, key, value)
    @size += 1 if r
    value
  end

  def insert(key, value)
    self[key] = value
  end

  # 削除
  def delete(key)
    @root, data = delete_node(@root, key)
    @size -= 1 if data
    data
  end

  def delete_max
    return nil if empty?
    @root, node = delete_max_node(@root)
    @size -= 1
    return node.key, node.data
  end

  def delete_min
    return nil if empty?
    @root, node = delete_min_node(@root)
    @size -= 1
    return node.key, node.data
  end

  # 巡回
  def each(&func)
    traverse_node(@root, &func)
    self
  end

  def inspect
    sprintf("#<Tree:%#x>", self.object_id)
  end
end

●AA 木

AA 木 (Arne Andersson tree) は 1993 年に Arne Andersson 氏が発表した平衡木です。二分木は左右の部分木のバランスが崩れると性能が劣化する欠点があります。極端な例ですが、ソートされたデータを二分木に挿入していくと、データは右側の部分木にしか挿入されず、連結リストと同じ線形探索になってしまいます。これを補うために、木のバランスを一定の範囲に収める平衡木が考案されています。有名なところでは、二分木をベースにした AVL 木、赤黒木、AA 木などや、多分木をベースにした 2-3 木、2-3-4 木、B 木、B* 木などがあります。

赤黒木は 2-3-4 木の動作を二分木で実現したものですが、そのプログラムはとても複雑です。これに対して、AA 木は 2-3 木の動作を二分木で実現したものですが、とても簡単にプログラムを実装できる、という特徴があります。AA 木の詳しい説明は、拙作のページ Algorithms with Python: AA 木 をお読みください。

●仕様

●実行例

irb> test1(AAtree.new)
dic.empty? => true
dic.size => 0
dic[foo] = 49
dic[bar] = 12
dic[baz] = 39
dic[oops] = 47
dic.empty? => false
dic.size => 4
dic[foo] => 49
dic.member?(foo) => true
dic[bar] => 12
dic.member?(bar) => true
dic[baz] => 39
dic.member?(baz) => true
dic[oops] => 47
dic.member?(oops) => true
dic[Foo] => nil
dic[Bar] => nil
dic.member?(Bar) => false
dic[Baz] => nil
dic.member?(Baz) => false
dic[Oops] => nil
dic.member?(Oops) => false
dic.each{|x| ...}
["bar", 12]
["baz", 39]
["foo", 49]
["oops", 47]
dic[foo] *= 10, dic[foo] => 490
dic[bar] *= 10, dic[bar] => 120
dic[baz] *= 10, dic[baz] => 390
dic[oops] *= 10, dic[oops] => 470
dic.delete(foo) => 490
empty? => false
size => 3
dic.member?(foo) => false
dic.delete(bar) => 120
empty? => false
size => 2
dic.member?(bar) => false
dic.delete(baz) => 390
empty? => false
size => 1
dic.member?(baz) => false
dic.delete(oops) => 470
empty? => true
size => 0
dic.member?(oops) => false
=> ["foo", "bar", "baz", "oops"]

irb> test3(AAtree.new)
dic.empty? => false
dic.size => 10
dic.max => [10, true]
dic.min => [1, true]
dic.delete_max => [10, true]
dic.delete_min => [1, true]
dic.max => [9, true]
dic.min => [2, true]
dic.empty? => false
dic.size => 8
dic.delete_max => [9, true]
dic.size => 7
dic.delete_max => [8, true]
dic.size => 6
dic.delete_max => [7, true]
dic.size => 5
dic.delete_max => [6, true]
dic.size => 4
dic.delete_min => [2, true]
dic.size => 3
dic.delete_min => [3, true]
dic.size => 2
dic.delete_min => [4, true]
dic.size => 1
dic.delete_min => [5, true]
dic.size => 0
dic.empty? => true
=> nil
# ランダム
irb> test2([10000,20000,40000,80000], Tree.new)
 10000 : 0.063 : 0.015 : 0.017
 20000 : 0.106 : 0.032 : 0.038
 40000 : 0.240 : 0.068 : 0.080
 80000 : 0.494 : 0.142 : 0.164
=> [10000, 20000, 40000, 80000]

irb> test2([10000,20000,40000,80000], AAtree.new)
 10000 : 0.067 : 0.012 : 0.045
 20000 : 0.156 : 0.027 : 0.096
 40000 : 0.303 : 0.059 : 0.197
 80000 : 0.701 : 0.129 : 0.413
=> [10000, 20000, 40000, 80000]

# 昇順
irb> test2([1000,2000,4000,8000], Tree.new)
  1000 : 0.098 : 0.038 : 0.000
  2000 : 0.383 : 0.161 : 0.001
  4000 : 1.588 : 0.618 : 0.001
  8000 : 6.821 : 2.615 : 0.002
=> [1000, 2000, 4000, 8000]

irb> test2([1000,2000,4000,8000], AAtree.new)
  1000 : 0.005 : 0.001 : 0.004
  2000 : 0.012 : 0.002 : 0.008
  4000 : 0.027 : 0.004 : 0.018
  8000 : 0.060 : 0.010 : 0.046
=> [1000, 2000, 4000, 8000]

# 逆順
irb> test2([1000,2000,4000,8000], Tree.new)
  1000 : 0.100 : 0.037 : 0.095
  2000 : 0.379 : 0.150 : 0.354
  4000 : 1.583 : 0.571 : 1.442
  8000 : 6.695 : 2.456 : 6.108
=> [1000, 2000, 4000, 8000]

irb> test2([1000,2000,4000,8000], AAtree.new)
  1000 : 0.005 : 0.001 : 0.004
  2000 : 0.009 : 0.002 : 0.010
  4000 : 0.021 : 0.004 : 0.018
  8000 : 0.045 : 0.010 : 0.040
=> [1000, 2000, 4000, 8000]

実行環境 : Ruby 3.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz

●プログラム

# coding: utf-8
#
# aatree.rb : AA tree (平衡木)
#
#             Copyright (C) 2023 Makoto Hiroi
#

class AAtree
  include Enumerable
  attr_reader :size
  # 節の定義
  class Node
    attr_accessor :key, :data, :height, :left, :right
    def initialize(k, x, l, r)
      @key = k
      @data = x
      @height = 1
      @left = l
      @right = r
    end

    # 終端の生成
    def Node.make_null
      a = Node.new(nil, nil, nil, nil)
      a.height = 0
      a.left = a
      a.right = a
      a
    end
  end

  # 終端
  Null = Node.make_null

  def initialize
    @root = Null
    @size = 0
  end

  # 節の操作関数
  private
  # 右回転
  def rotate_right(node)
    lnode = node.left
    node.left = lnode.right
    lnode.right = node
    lnode
  end

  # 左回転
  def rotate_left(node)
    rnode = node.right
    node.right = rnode.left
    rnode.left = node
    rnode
  end

  # 左の子が赤の場合
  def skew(node)
    node = rotate_right(node) if node.left.height == node.height
    node
  end

  # 右の孫節が赤の場合
  def split(node)
    if node.height == node.right.right.height
      node = rotate_left(node)
      node.height += 1
    end
    node
  end

  #
  # 探索
  #
  def search_node(node, key)
    while node != Null
      if key == node.key
        return node.data
      elsif key < node.key
        node = node.left
      else
        node = node.right
      end
    end
    nil
  end

  # 最小値を探す
  def search_min_node(node)
    while node.left != Null
      node = node.left
    end
    return node.key, node.data
  end

  # 最大値を探す
  def search_max_node(node)
    while node.right != Null
      node = node.right
    end
    return node.key, node.data
  end

  #
  # 挿入
  #
  def insert_node(node, key, x)
    if node == Null
      return Node.new(key, x, Null, Null), true
    elsif key == node.key
      node.data = x
      return node, nil
    elsif key < node.key
      node.left, r = insert_node(node.left, key, x)
    else
      node.right, r = insert_node(node.right, key, x)
    end
    return split(skew(node)), r
  end

  #
  # 削除
  #

  # バランスのチェックと修正処理
  def delete_balance(node)
    if node.left.height < node.height - 1 || node.right.height < node.height - 1
      node.height -= 1
      node.right.height = node.height if node.right.height > node.height
      node = skew(node)
      node.right = skew(node.right)
      node.right.right = skew(node.right.right)
      node = split(node)
      node.right = split(node.right)
    end
    node
  end

  def delete_node(node, key)
    if node == Null
      return node, nil
    else
      if key == node.key
        return node.right, node.data if node.left == Null
        return node.left, node.data if node.right == Null
        del_data = node.data
        node.key, node_data = search_min_node(node.right)
        node.right, _ = delete_node(node.right, node.key)
      elsif key < node.key
        node.left, del_data = delete_node(node.left, key)
      else
        node.right, del_data = delete_node(node.right, key)
      end
      return delete_balance(node), del_data
    end
  end

  # 最大値を削除
  def delete_max_node(node)
    if node.right == Null
      return node.left, node
    else
      node.right, del_data = delete_max_node(node.right)
      return delete_balance(node), del_data
    end
  end

  # 最小値を削除
  def delete_min_node(node)
    if node.left == Null
      return node.right, node
    else
      node.left, del_data = delete_min_node(node.left)
      return delete_balance(node), del_data
    end
  end

  #
  # 巡回
  #
  def traverse_node(node, &block)
    if node != Null
      traverse_node(node.left, &block)
      yield [node.key, node.data]
      traverse_node(node.right, &block)
    end
  end

  #
  # AA 木のチェック
  #
  def check_tree(node)
    if node != Null
      if node.height != node.left.height + 1
        raise 'aa tree error1'
      end
      if node.height != node.right.height && node.height != node.right.height + 1
        raise 'aa tree error2'
      end
      if node.height == node.right.right.height
        raise 'aa tree error3'
      end
      check_tree(node.left)
      check_tree(node.right)
    end
  end

  #
  # AA tree の操作関数
  #
  public
  # 空の木か?
  def empty?
    @root == Null
  end

  # 探索
  def [](key)
    search_node(@root, key)
  end

  def member?(key)
    self[key] ? true : false
  end

  # 最大値
  def max
    search_max_node(@root) if !empty?
  end

  # 最小値
  def min
    search_min_node(@root) if !empty?
  end

  # 挿入 (nil は除外する)
  def []=(key, x)
    return nil if key == nil || x == nil
    @root, r = insert_node(@root, key, x)
    @size += 1 if r != nil
    x
  end

  def insert(key, x)
    self[key] = x
  end

  # 削除
  def delete(key)
    @root, data = delete_node(@root, key)
    @size -= 1 if data != nil
    data
  end

  # 最大値を削除
  def delete_max
    if !empty?
      @root, node = delete_max_node(@root)
      @size -= 1
      return node.key, node.data
    end
  end

  # 最小値を削除
  def delete_min
    if !empty?
      @root, node = delete_min_node(@root)
      @size -= 1
      return node.key, node.data
    end
  end

  # 巡回
  def each(&block)
    traverse_node(@root, &block)
    self
  end

  # AA 木のチェック
  def check
    check_tree(@root)
    true
  end

  def inspect
    sprintf("#<AAtree:%#x>", self.object_id)
  end
end

●スプレー木

スプレー木 (Splay tree) は 1985 年に Sleater 氏と Tarjan 氏が提案した二分木 (平衡木) の一種です。一般的な平衡木 (赤黒木や AA 木など) の場合、要素数を N とすると最悪でも O(log2 N) の時間で基本的な操作 (探索、挿入、削除) を行うことができますが、スプレー木にはその保証がありません。

そのかわり、基本的な操作を複数回行ったときの平均実行時間が O(log2 N) になるという性質があります。ようするに、一回あたり長い時間がかかる操作があったとしても、全体で平均してみると O(log2 N) になるデータ構造というわけです。スプレー木の詳しい説明は拙作のページ Algorithms with Python: スプレー木 をお読みください。

●仕様

●使用例

irb> test1(Splaytree.new)
dic.empty? => true
dic.size => 0
dic[foo] = 29
dic[bar] = 96
dic[baz] = 1
dic[oops] = 30
dic.empty? => false
dic.size => 4
dic[foo] => 29
dic.member?(foo) => true
dic[bar] => 96
dic.member?(bar) => true
dic[baz] => 1
dic.member?(baz) => true
dic[oops] => 30
dic.member?(oops) => true
dic[Foo] => nil
dic.member?(Foo) => false
dic[Bar] => nil
dic.member?(Bar) => false
dic[Baz] => nil
dic.member?(Baz) => false
dic[Oops] => nil
dic.member?(Oops) => false
dic.each{|x| ...}
["bar", 96]
["baz", 1]
["foo", 29]
["oops", 30]
dic[foo] *= 10, dic[foo] => 290
dic[bar] *= 10, dic[bar] => 960
dic[baz] *= 10, dic[baz] => 10
dic[oops] *= 10, dic[oops] => 300
dic.delete(foo) => 290
empty? => false
size => 3
dic.member?(foo) => false
dic.delete(bar) => 960
empty? => false
size => 2
dic.member?(bar) => false
dic.delete(baz) => 10
empty? => false
size => 1
dic.member?(baz) => false
dic.delete(oops) => 300
empty? => true
size => 0
dic.member?(oops) => false
=> ["foo", "bar", "baz", "oops"]

irb> test3(Splaytree.new)
dic.empty? => false
dic.size => 10
dic.max => [10, true]
dic.min => [1, true]
dic.delete_max => [10, true]
dic.delete_min => [1, true]
dic.max => [9, true]
dic.min => [2, true]
dic.empty? => false
dic.size => 8
dic.delete_max => [9, true]
dic.size => 7
dic.delete_max => [8, true]
dic.size => 6
dic.delete_max => [7, true]
dic.size => 5
dic.delete_max => [6, true]
dic.size => 4
dic.delete_min => [2, true]
dic.size => 3
dic.delete_min => [3, true]
dic.size => 2
dic.delete_min => [4, true]
dic.size => 1
dic.delete_min => [5, true]
dic.size => 0
dic.empty? => true
=> nil
# 乱数
irb> test2([10000,20000,40000,80000], Splaytree.new)
 10000 : 0.060 : 0.012 : 0.015
 20000 : 0.107 : 0.032 : 0.028
 40000 : 0.248 : 0.055 : 0.064
 80000 : 0.575 : 0.097 : 0.130
=> [10000, 20000, 40000, 80000]

# 昇順
irb> test2([10000,20000,40000,80000], Splaytree.new)
 10000 : 0.024 : 0.015 : 0.014
 20000 : 0.032 : 0.039 : 0.026
 40000 : 0.074 : 0.061 : 0.053
 80000 : 0.142 : 0.118 : 0.110
=> [10000, 20000, 40000, 80000]
irb> test2([10000,20000,40000,80000], AAtree.new)
 10000 : 0.086 : 0.013 : 0.052
 20000 : 0.150 : 0.026 : 0.102
 40000 : 0.343 : 0.057 : 0.213
 80000 : 0.743 : 0.118 : 0.470
=> [10000, 20000, 40000, 80000]

# 逆順
irb> test2([10000,20000,40000,80000], Splaytree.new)
 10000 : 0.015 : 0.009 : 0.014
 20000 : 0.026 : 0.021 : 0.031
 40000 : 0.062 : 0.048 : 0.054
 80000 : 0.118 : 0.082 : 0.114
=> [10000, 20000, 40000, 80000]
irb> test2([10000,20000,40000,80000], AAtree.new)
 10000 : 0.065 : 0.012 : 0.051
 20000 : 0.127 : 0.025 : 0.103
 40000 : 0.268 : 0.057 : 0.215
 80000 : 0.558 : 0.118 : 0.447
=> [10000, 20000, 40000, 80000]

●プログラム

# coding: utf-8
#
# splay.py : スプレー木
#
#            Copyright (C) 2023 Makoto Hiroi
#
class Splaytree
  include Enumerable
  attr_reader :size

  # 節 (終端は nil)
  class Node
    attr_accessor :key, :data, :left, :right
    def initialize(k, x)
      @key = k
      @data = x
      @left = nil
      @right = nil
    end
  end

  def initialize
    @root = nil
    @size = 0
  end

  # 作業用
  private
  # 右回転
  def rotate_right(node)
    lnode = node.left
    node.left = lnode.right
    lnode.right = node
    lnode
  end

  # 左回転
  def rotate_left(node)
    rnode = node.right
    node.right = rnode.left
    rnode.left = node
    rnode
  end

  # Top-Down Splay
  def splay(node, key)
    wnode = Node.new(nil, nil)  # Splay 作業用セル
    rnode = wnode  # rnode は右部分木になる節を追加する
    lnode = wnode  # lnode は左部分木になる節を追加する
    while true
      if key == node.key
        break
      elsif key < node.key
        # node は右部分木になる
        break if !node.left
        if key < node.left.key
          # 右回転 (zig - zig)
          node = rotate_right(node)
          break if !node.left
        end
        rnode.left = node
        rnode = node
        node = node.left
      else
        # node は左部分木になる
        break if !node.right
        if key > node.right.key
          # 左回転 (zig - zig)
          node = rotate_left(node)
          break if !node.right
        end
        lnode.right = node
        lnode = node
        node = node.right
      end
    end
    rnode.left = node.right
    lnode.right = node.left
    node.left = wnode.right
    node.right = wnode.left
    node
  end

  def search_max_node(node)
    wnode = Node.new(nil, nil)  # Splay 作業用セル
    lnode = wnode  # lnode は左部分木になる節を追加する
    while node.right
      # node は左部分木になる
      # 左回転 (zig - zig)
      node = rotate_left(node)
      break if !node.right
      lnode.right = node
      lnode = node
      node = node.right
    end
    lnode.right = node.left
    node.left = wnode.right
    node
  end

  def search_min_node(node)
    wnode = Node.new(nil, nil)  # Splay 作業用セル
    rnode = wnode  # rnode は右部分木になる節を追加する
    while node.left
      # node は右部分木になる
      # 右回転 (zig - zig)
      node = rotate_right(node)
      break if !node.left
      rnode.left = node
      rnode = node
      node = node.left
    end
    rnode.left = node.right
    node.right = wnode.left
    node
  end

  # データの挿入
  def insert_node(node, key, x)
    return Node.new(key, x), true if !node
    node = splay(node, key)
    if key == node.key
      node.data = x
      return node, false
    end
    new_node = Node.new(key, x)
    if key < node.key
      new_node.right = node
      new_node.left = node.left
      node.left = nil
    else
      new_node.left = node
      new_node.right = node.right
      node.right = nil
    end
    return new_node, true
  end

  # データの探索
  def search_node(node, key)
    return node, nil if !node
    node = splay(node, key)
    if key == node.key
      return node, node.data
    else
      return node, nil
    end
  end

  # データの削除
  def delete_node(node, key)
    return node, nil if !node
    node = splay(node, key)
    return node, nil if key != node.key
    # データあり
    if !node.left
      return node.right, node.data
    elsif !node.right
      return node.left, node.data
    else
      node1 = splay(node.left, key)
      node1.right = node.right
      return node1, node.data
    end
  end

  # 巡回
  def next_node(node, stack)
    while node
      stack.push node
      node = node.left
    end
  end

  def traverse_node(node, &block)
    stack = []
    next_node(@root, stack)
    while stack.size > 0
      node = stack.pop
      yield [node.key, node.data]
      next_node(node.right, stack)
    end
  end

  # 公開メソッド
  public
  # 木は空か?
  def empty?
    @root == nil
  end

  # 探索
  def [](key)
    @root, r = search_node(@root, key)
    r
  end

  def member?(key)
    self[key] ? true : false
  end

  # 最大値
  def max
    return nil if !@root
    @root = search_max_node(@root)
    return @root.key, @root.data
  end

  # 最小値
  def min
    return nil if !@root
    @root = search_min_node(@root)
    return @root.key, @root.data
  end

  # 挿入
  def []=(key, x)
    return nil if key == nil || x == nil
    @root, r = insert_node(@root, key, x)
    @size += 1 if r
    x
  end

  def insert(key, x)
    self[key] = x
  end

  # 削除
  def delete(key)
    @root, r = delete_node(@root, key)
    @size -= 1 if r
    r
  end

  def delete_max
    return nil if !@root
    node = search_max_node(@root)
    @root = node.left
    @size -= 1
    return node.key, node.data
  end

  def delete_min
    return nil if !@root
    node = search_min_node(@root)
    @root = node.right
    @size -= 1
    return node.key, node.data
  end

  # 巡回
  def each(&block)
    traverse_node(@root, &block)
    self
  end

  def inspect
    sprintf("#<Splaytree:%#x>", self.object_id)
  end
end

Copyright (C) 2023 Makoto Hiroi
All rights reserved.

[ PrevPage | R u b y | NextPage ]