前回の続きです。今回も Ruby の例題として、いろいろなコレクションクラスを作ってみましょう。
ハッシュ法 (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