ハッシュ法 (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
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"]
# # 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
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"]
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
# 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 木 (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