今回は Ruby の例題として、いろいろなコレクションクラスを作ってみましょう。
双方向リストは、直後のセルだけでなく直前のセルへの参照を持たせたデータ構造です。双方向リストは「重連結リスト (doubly-linked list)」と呼ばれることもあります。双方向リストを使う場合、ヘッダセルを用意してリストを環状に構成することが多いです。
ヘッダセル ┌─┬─┬─┐ ┌←─┼・│ │・│←───────────────────┐ │┌→│・│ │・┼─→─────────────────┐│ ││ └─┴─┴─┘ ││ ││ ││ ││ data data data ││ ││ ┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ ││ │└←┼・│A│・│←─┼・│B│・│←─┼・│C│・│←┘│ └─→│・│ │・┼─→│・│ │・┼─→│・│ │・┼─→┘ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ prev link prev link prev link 図 : 双方向リスト
連結リストは後ろ方向にしかセルをたどることができませんが、双方向リストでは前後どちらの方向へもセルをたどることができます。セルを削除する場合も、前後のセルがわかるので簡単に削除することができます。詳しい説明は拙作のページ Algorithms with Python: 連結リストとキュー をお読みください。
添字 n が負の場合は後ろから数える。演算子 [ ] による参照と代入もサポートする。
irb> load "dlist.rb" => true irb> d = DList.new => #<DList: ...> irb> d.empty? => true irb> d.insert(0, 1) => 1 irb> d.empty? => false irb> d.at(0) => 1 irb> d.at(-1) => 1 irb> d.delete_at(0) => 1 irb> d.empty? => true irb> d = DList.new(10, 20, 30, 40, 50) => #<DList: ...> irb> 5.times {|i| print d[i], " "} 10 20 30 40 50 => 5 irb> d.each {|x| print x, " "} 10 20 30 40 50 => #<DList: ...> irb> d.insert(0, 0) => 0 irb> d.to_s => "(0,10,20,30,40,50)" irb> d.to_a => [0, 10, 20, 30, 40, 50] irb> d.insert(3, 1) => 1 irb> d.to_a => [0, 10, 20, 1, 30, 40, 50] irb> d.insert(-1, 2) => 2 irb> d.to_a => [0, 10, 20, 1, 30, 40, 50, 2] irb> d.delete_at(0) => 0 irb> d.to_a => [10, 20, 1, 30, 40, 50, 2] irb> d.delete_at(2) => 1 irb> d.to_a => [10, 20, 30, 40, 50, 2] irb> d.delete_at(-1) => 2 irb> d.to_a => [10, 20, 30, 40, 50] irb> d1 = DList.new(1,2,3,4,5,6,7,8) => #<DList:0x104< irb(main):004:0> d1.delete_if{|x| x % 2 == 0} => #<DList:0x104< irb> d1.to_a => [1, 3, 5, 7] irb> d1 = DList.new(1,2,3,4,1,2,3,1,2,1) => #<DList:0x118< irb> d1.to_a => [1, 2, 3, 4, 1, 2, 3, 1, 2, 1] irb> d1.delete(1) => 1 irb> d1.to_a => [2, 3, 4, 2, 3, 2] irb> d.to_a => [10, 20, 30, 40, 50] irb> d.member? 30 => true irb> d.member? 33 => false irb> d.map {|x| x * 10} => [100, 200, 300, 400, 500] irb> d.filter {|x| (x / 10) % 2 == 1} => [10, 30, 50] irb> d.reduce(0){|a, x| a + x} => 150
リスト : 双方向リスト (dlist.rb) class DList include Enumerable # 双方向リスト用セル class Cell2 attr_accessor :data, :link, :prev def initialize(data, link = nil, prev = nil) @data = data @link = link @prev = prev end end def initialize(*args) @head = Cell2.new(nil) # Header Cell @head.link = @head @head.prev = @head args.each do |x| insert(-1, x) end end private # n 番目のセルを求める def _at(n) if n >= 0 cp = @head.link while cp != @head return cp if n == 0 n -= 1 cp = cp.link end else cp = @head.prev while cp != @head n += 1 return cp if n == 0 cp = cp.prev end end end public # n 番目の要素を求める def at(n) cp = _at(n) cp.data if cp end # n 番目のデータを削除 def delete_at(n) cp = _at(n) if cp # p <--> cp <--> q p = cp.prev q = cp.link p.link = q q.prev = p cp.data end end # ブロックが真を返す要素を削除する def delete_if cp = @head.link while cp != @head if yield cp.data p = cp.prev q = cp.link p.link = q q.prev = p end cp = cp.link end self end # 引数 value と等しい要素を削除する def delete(value) data = nil delete_if {|x| if x == value data = value true else false end } data end # n 番目にデータを挿入する def insert(n, data) q = @head if n >= 0 begin if n == 0 # q <--> cp <--> p p = q.link cp = Cell2.new(data, p, q) q.link = cp p.prev = cp return data end n -= 1 q = q.link end while q != @head else begin n += 1 if n == 0 # p <--> cp <--> q p = q.prev cp = Cell2.new(data, q, p) q.prev = cp p.link = cp return data end q = q.prev end while q != @head end end # 空リストか? def empty? @head.link == @head end # Enumerable 用 def each cp = @head.link while cp != @head yield cp.data cp = cp.link end self end # 演算子 [] の定義 # 参照 def [](n) at(n) end # 代入 def []=(n, value) cp = _at(n) cp.data = value if cp end # 文字列に変換 def to_s if @head.link != @head str = "(" each do |x| str << x.to_s str << "," end str[-1] = ")" else str = "()" end str end def inspect sprintf("#<DList:%#x>", self.object_id) end end
deque は「両端キュー」のことで、「デック」とか「ディーキュー」と呼ばれています。キューの場合、データの追加は最後尾に、データの取り出しは先頭に対してのみ行えます。これに対しディーキューは、先頭および最後尾のどちらでもデータの追加と取り出しが行えるデータ構造です。ディーキューは双方向リストを使うと簡単に実現できます。
irb> load "dlist.rb" => true irb> d = Deque.new => #<Deque: ...> irb> d.empty? => true irb> d.size => 0 irb> d.push 1 => 1 irb> d.push 2 => 2 irb> d.unshift 3 => 3 irb> d.unshift 4 => 4 irb> d.to_a => [4, 3, 1, 2] irb> d.empty? => false irb> d.size => 4 irb> d.pop => 2 irb> d.pop => 1 irb> d.shift => 4 irb> d.shift => 3 irb> d.empty? => true irb> 8.times {|x| d.push x} => 8 irb> while not d.empty? irb> print d.pop, " " irb> end 7 6 5 4 3 2 1 0 => nil irb> 8.times {|x| d.push x} => 8 irb> while not d.empty? irb> print d.shift, " " irb> end 0 1 2 3 4 5 6 7 => nil
リスト : ディキュー (dlist.rb) class Deque attr_reader :size def initialize @size = 0 @buff = DList.new end # Array の仕様に合わせる # 最後尾にデータを追加 def push(data) @size += 1 @buff.insert(-1, data) end # 最後尾からデータを削除 def pop if @size > 0 @size -= 1 @buff.delete_at(-1) end end # 先頭にデータを追加 def unshift(data) @size += 1 @buff.insert(0, data) end # 先頭からデータを削除 def shift if @size > 0 @size -= 1 @buff.delete_at(0) end end # 先頭データの取得 def first @buff.at(0) if @size > 0 end # 末尾データの取得 def last @buff.at(-1) if @size > 0 end # デキューは空か? def empty? @size == 0 end # 配列に変換 def to_a @buff.to_a end # 文字列に変換 def to_s @buff.to_s end def inspect sprintf("#<Deque:%#x>", self.object_id) end end
「ヒープ (heap)」は「半順序木 (partial ordered tree)」を配列で実現したデータ構造です。一般的な二分木では、親よりも左側の子のほうが小さく、親よりも右側の子が大きい、という関係を満たすように作ります。「半順序木」の場合、親は子より小さいか等しい、という関係を満たすように作ります。したがって、木の根(配列の添字 0)には、必ず最小値のデータが格納されます。下図にヒープと配列の関係を示します。
0 1 2 3 4 5 6 TABLE [10 20 30 40 50 60 70] (root) 10 (0) / \ 親の添字を k とすると / \ その子は 2*k+1, 2*k+2 になる。 20 (1) 30 (2) 親の値 < 子の値 の関係を満たす。 / \ / \ 40 50 60 70 (3) (4) (5) (6) 図 : ヒープと配列の対応関係
ヒープを利用すると、最小値をすぐに見つけることができ、新しくデータを挿入する場合も、高々要素の個数 (N) の対数 (log2 N) に比例する程度の時間で済みます。詳しい説明は拙作のページ Algorithms with Python: 二分木とヒープ をお読みくださいませ。
それでは、ヒープを使って「優先度つき待ち行列 (priority queue)」を作ってみましょう。一般に、キューは先入れ先出し (FIFO : first-in, first-out) のデータ構造です。キューからデータを取り出すときは、先に挿入されたデータから取り出されます。これに対し、優先度つき待ち行列は、データに優先度をつけておいて、優先度の高いデータから取り出していきます。優先度つき待ち行列は、優先度を基準にヒープを構築することで実現できます。
irb> load "heap.rb" => true irb> pq = PQueue.new => #<PQueue: ...> irb> pq.empty? => true irb> pq.size => 0 irb> pq.insert(5) => nil irb> pq.insert(3) => nil irb> pq.insert(7) => nil irb> pq.insert(1) => nil irb> pq.insert(9) => nil irb> pq.empty? => false irb> pq.size => 5 irb> while not pq.empty? irb> print pq.delete_min, " " irb> end 1 3 5 7 9 => nil irb> a = (1..20).to_a.shuffle => [19, 17, 14, 12, 8, 20, 2, 18, 4, 11, 6, 1, 10, 5, 3, 16, 15, 13, 7, 9] irb> pq = PQueue.new(a) => #<PQueue: ...> irb> while not pq.empty? irb> print pq.delete_min, " " irb> end 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 => nil
リスト : プライオリティキュー (heap.rb) class PQueue def initialize(ary = []) @buff = ary.dup (@buff.size / 2 - 1).downto(0) do |n| reheap_to_leaf(@buff, n) end end private def reheap_to_leaf(ary, n) loop do c = 2 * n + 1 break if c >= ary.size if c + 1 < ary.size c += 1 if ary[c] > ary[c + 1] end break if ary[n] <= ary[c] temp = ary[n] ary[n] = ary[c] ary[c] = temp n = c end end def reheap_to_root(ary, n) loop do p = (n - 1) / 2 break if p < 0 || ary[p] <= ary[n] temp = ary[n] ary[n] = ary[p] ary[p] = temp n = p end end public # 最小値を取り出す def delete_min return nil if @buff.empty? value = @buff[0] last = @buff.pop if @buff.size > 0 @buff[0] = last reheap_to_leaf(@buff, 0) end value end # 最小値を参照 def first return nil if @buff.empty? @buff[0] end # データの挿入 def insert(data) @buff.push data reheap_to_root(@buff, @buff.size - 1) end # キューは空か? def empty? @buff.empty? end # 要素の個数 def size @buff.size end def inspect sprintf("#<PQueue:%#x>", self.object_id) end end
トライは文字列の集合を表すのに都合のよいデータ構造です。トライの語源は、「検索 (retrieval)」という言葉の真ん中 (trie) に由来しています。トライは木構造の一種であり、根から葉までの経路がひとつの単語に対応します。次の図を見てください。
T / \ / \ / \ / \ A H /│\ /│\ / │ \ / │ \ / │ \ / │ \ I K L A E I │ │ /│ │ /│ │ L E K L T $6 N S │ │ │ │ │ │ │ $1 $2 $3 $4 $5 $7 $8 { TAIL, TAKE, TALK, TALL, THAT, THE, THEN, THIS } 図 : 文字列の集合を表したトライ
上図は文字列の集合をトライで表現したものです。ここでは葉を $ で表しています。たとえば、葉 $7 までたどると、それは "THEN" という文字列を表しています。また、文字列 "THE" をトライから探す場合は、節を順番にたどっていって、葉 $6 に達した時点で "THE" を見つけることができます。もし、節 E の子に葉 $6 がなければ、THE はトライに存在しないことになります。詳しい説明は拙作のページ Algorithms with Python: トライとパトリシア をお読みくださいませ。
irb> load "trie.rb" => true irb> a = Trie.new => #<Trie: ...> irb> a.empty? => true irb> a.size => 0 irb> a.insert("hello") => "hello" irb> a.empty? => false irb> a.size => 1 irb> a.insert("world") => "world" irb> a.size => 2 irb> a.member?("hello") => true irb> a.member?("hello,") => false irb> a.member?("hell") => false irb> a.member?("world") => true irb> a.member?("world ") => false irb> a.member?("worl") => false irb> a.delete("hello") => true irb> a.delete("hello") => false irb> a.member?("hello") => false irb> a.delete("world") => true irb> a.delete("world") => false irb> a.member?("world") => false irb> a.empty? => true irb> a.size => 0 irb> s = "abcabbca" irb> for i in 0 ... s.size irb> a.insert(s[i..-1]) irb> end => 0...8 irb> a.each{|xs| print xs, "\n"} ["a", "b", "c", "a", "b", "b", "c", "a"] ["a", "b", "b", "c", "a"] ["a"] ["b", "c", "a", "b", "b", "c", "a"] ["b", "c", "a"] ["b", "b", "c", "a"] ["c", "a", "b", "b", "c", "a"] ["c", "a"] => #<Trie: ...> irb> a.common_prefix("ab"){|xs| print xs.join, "\n"} abcabbca abbca => #<Trie: ...> irb> a.common_prefix("bc"){|xs| print xs.join, "\n"} bcabbca bca => #<Trie: ...> irb> a.common_prefix("ca"){|xs| print xs.join, "\n"} cabbca ca => #<Trie: ...>
リスト : トライ (trie.rb) class Trie attr_reader :size # トライ用節の定義 class Node attr_accessor :data, :child def initialize(data) @data = data @child = [] # 子は配列に格納する end end def initialize @root = Node.new(nil) @leaf = Node.new(nil) @size = 0 end private def search_child(node, x) node.child.find do |n| n.data == x end end # 巡回 def _traverse(node, buff, &block) if node == @leaf yield buff else b = buff + [node.data] for x in node.child _traverse(x, b, &block) end end end public # 探索 def member?(seq) node = @root for x in 0 ... seq.size node = search_child(node, seq[x]) return false unless node end node.child.member?(@leaf) end # 挿入 def insert(seq) node = @root for x in 0 ... seq.size child = search_child(node, seq[x]) unless child child = Node.new(seq[x]) node.child.push child end node = child end unless node.child.member?(@leaf) node.child.push @leaf @size += 1 seq end end # 削除 (葉を削除するだけ) def delete(seq) node = @root for x in 0 ... seq.size node = search_child(node, seq[x]) return nil unless node end if node.child.delete(@leaf) @size -= 1 true else false end end # 共通接頭辞を持つデータを求める def common_prefix(seq, &block) node = @root buff = [] for x in 0 ... seq.size buff.push seq[x] node = search_child(node, seq[x]) return nil unless node end for cnode in node.child _traverse(cnode, buff, &block) end self end # トライは空か? def empty? @size == 0 end # Enumberable 用 def each(&block) for x in @root.child _traverse(x, [], &block) end self end def inspect sprintf("#<Trie:%#x>", self.object_id) end end
トライはとても便利なデータ構造ですが、節にはひとつの文字しか格納できないため、文字列の種類が多くなるとメモリを大量に消費してしまいます。このため、文字ではなく文字列を節に格納する方法があります。次の図を見てください。
T / \ / \ / \ / \ A H /│\ /│\ / │ \ / │ \ / │ \ / │ \ "IL" "KE" L "AT" E "IS" │ │ /│ │ /│ │ $1 $2 K L $5 $6 N $8 │ │ │ $3 $4 $7 { TAIL, TAKE, TALK, TALL, THAT, THE, THEN, THIS } 図:文字列の集合を表したパトリシア
"TAIL" をトライで表すと T - A - I - L となりますが、I の子は L しかありませんね。この部分は "IL" とまとめることができます。つまり、節には部分文字列を格納するわけです。このように、トライにおいて分岐していない節をひとつにまとめたものをパトリシア (Patricia Tree) と呼びます。
パトリシアの場合、データの探索は節の部分文字列を比較していくだけなので、簡単に実現できます。ところが、データの挿入はちょっとだけ複雑になります。たとえば、パトリシアが "ab" - "cdef" という状態で、ここに文字列 "abcdgh" を挿入してみましょう。
挿入する文字列の先頭 2 文字と最初の節 "ab" は一致するので、次の節 "cdef" と残りの文字列 "cdgh" を比較します。"cd" は一致しますが、それ以降で不一致になりますね。この場合、節 "cdef" を不一致の位置で分割します。つまり、節 "cdef" を "cd" - "ef" と分割し、節 "cd" に新しい節 "gh" を追加するのです。このあと、終端を表す葉を追加すれば、パトリシアに "abcdgh" を挿入することができます。
このように、パトリシアにデータを挿入する場合、節の分割が必要になるためプログラムは複雑になります。そのかわり、パトリシアはトライに比べて節の個数を少なくすることができるので、トライよりも少ないメモリで文字列の集合を表すことができます。詳しい説明は拙作のページ Algorithms with Python: トライとパトリシア をお読みくださいませ。
irb> load "patricia.rb" => true irb> a = Patricia.new => #<Patricia: ...> irb> a.empty? => true irb> a.size => 0 irb> ["hello", "world", "hello, world"].each{|s| a.insert(s)} => ["hello", "world", "hello, world"] irb> a.empty? => false irb> a.size => 3 irb> a.member? "hello" => true irb> a.member? "hello," => false irb> a.member? "world" => true irb> a.member? " world" => false irb> a.member? "hello, world" => true irb> a.member? "hello, world!" => false irb> a.delete "hello" => true irb> a.delete "hello" => false irb> a.member? "hello" => false irb> a.delete "world" => true irb> a.delete "world" => false irb> a.member? "world" => false irb> a.delete "hello, world" => true irb> a.delete "hello, world" => false irb> a.member? "hello, world" => false irb> a.size => 0 irb> a.empty? => true irb> s = "abcabbca" => "abcabbca" irb> for i in 0 ... s.size irb> a.insert(s[i .. -1]) irb> end => 0...8 irb> a.size => 8 irb> a.each{|xs| print xs, "\n"} ["a", "b", "cabbca"] ["a", "b", "bca"] ["a"] ["b", "ca", "bbca"] ["b", "ca"] ["b", "bca"] ["ca", "bbca"] ["ca"] => #<Patricia: ...> irb> a.common_prefix("a"){|xs| print xs, "\n"} ["a", "b", "cabbca"] ["a", "b", "bca"] ["a"] => #<Patricia: ...> irb> a.common_prefix("ab"){|xs| print xs, "\n"} ["ab", "cabbca"] ["ab", "bca"] => #<Patricia: ...> irb> a.common_prefix("abc"){|xs| print xs, "\n"} ["abc", "abbca"] => #<Patricia: ...> irb> a.common_prefix("bc"){|xs| print xs, "\n"} ["bc", "a", "bbca"] ["bc", "a"] => #<Patricia: ...> irb> a.common_prefix("bca"){|xs| print xs, "\n"} ["bca", "bbca"] ["bca"] => #<Patricia: ...>
リスト : パトリシア (patricia.rb) class Patricia attr_reader :size # 節の定義 class Node attr_accessor :data, :child def initialize(data, child = []) @data = data @child = child end end def initialize @root = Node.new(nil) @leaf = Node.new(nil) @size = 0 end private # 子を探す def search_child(n, c) n.child.find do |x| x.data && x.data[0] == c end end # 最長一致を求める def longest_match(seq) node = @root i = 0 while i < seq.size child = search_child(node, seq[i]) break unless child j = 1 while j < child.data.size if i + j == seq.size || seq[i + j] != child.data[j] return child, j, i + j end j += 1 end i += j node = child end return node, 0, i end # 巡回 def traverse(node, buff, &block) for x in node.child if x == @leaf yield buff else buff.push x.data traverse(x, buff, &block) buff.pop end end end public # 探索 def member?(seq) node, len, match_len = longest_match(seq) match_len == seq.size && len == 0 && node.child.member?(@leaf) end # 削除 def delete(seq) node, len, match_len = longest_match(seq) if match_len == seq.size && len == 0 && node.child.delete(@leaf) @size -= 1 true else false end end # 挿入 def insert(seq) node, len, match_len = longest_match(seq) if len == 0 if match_len == seq.size return false if node.child.member?(@leaf) node.child.push @leaf else # @node に残りの節を追加する new_node = Node.new(seq[match_len .. -1], [@leaf]) node.child.push new_node end else # @node を分割する node1 = Node.new(node.data[len .. -1], node.child) node.data = node.data[0 ... len] if match_len < seq.size new_node = Node.new(seq[match_len .. -1], [@leaf]) node.child = [node1, new_node] else node.child = [node1, @leaf] end end @size +=1 true end # 共通接頭辞を持つデータを求める def common_prefix(seq, &block) node, len, match_len = longest_match(seq) if match_len == seq.size buff = [seq] buff.push node.data[len .. -1] if len > 0 traverse(node, buff, &block) end self end # パトリシアは空か? def empty? @size == 0 end def each(&block) traverse(@root, [], &block) self end def inspect sprintf("#<Patricia:%#x>", self.object_id) end end
Ternary Search Tree (TST) は三分木を使った探索木で、トライと同様に文字列の集合を表すのに都合のよいデータ構造です。TST の動作はとても簡単で、節に格納されているデータを基準にして、それよりも小さいデータは左の木、等しいデータは中央の木、大きなデータは右の木をたどることで文字列を探索します。簡単な例を示します。下図を見てください。
TST の場合、トライのように「葉」で終端を表すことはできません。このため、終端を表すデータ(たとえば 0)を TST に挿入します。上図では、0 の節を $ で表しています。
たとえば、上図の TST から文字列 "THAT" を探してみましょう。最初の文字は T で、これは最初の節と一致しますね。中央の木をたどって、次の文字 H と比較します。節のデータは A なので、文字 H の方が大きいですね。右側の木をたどって次の節のデータと比較します。文字 H はこの節と一致するので、中央の木をたどって次の節へ進み、次の文字 A と比較します。
今度は E > A なので、左側の木をたどって次の節へ進みます。この節で文字 A と一致するので、中央の木をたどって次の節へ進み、次の文字 T と比較します。この節で文字 T と一致するので、中央の木をたどり終端を表す節 $5 に到達します。ここで、文字列 "THAT" を見つけたことになります。たどった経路は T - A - H - E - A - T - $5 ですが、この経路で表される文字列は "TAHEAT" ではなく "THAT" になることに注意してください。
T │ A │\ │ \ │ \ │ \ │ \ │ \ │ \ K \ /│\ H / │ \ │ I E L E │ │ │ /│\ L $2 L / │ \ │ /│ / $6 \ $1 K $4 A \ I │ │ N │ $3 T │ S │ $7 │ $5 $8 {TAIL,TAKE,TALK,TALL,THAT,THE,THEN,THIS} 図:文字列の集合を表した TST
このように、TST は一致する文字がないか左右の木をたどって探索し、一致したら中央の木をたどって次の文字へ進むことで文字列の探索を行います。それから、終端を表す節にもデータが追加される場合があります。たとえば、文字列 "THE" のあとに "THEN" を挿入すると、節 $6 の右側の木に文字 N の節が追加されます。TST の場合、終端を表す節は「葉」になるとは限りません。詳しい説明は拙作のページ Algorithms with Python: Ternary Search Tree をお読みくださいませ。
irb> load "tst.rb" => true irb> a = Tst.new => #<Tst: ...> irb> a.empty? => true irb> a.size => 0 irb> a.insert "hello" => true irb> a.insert "world" => true irb> a.insert "hello, world" => true irb> a.size => 3 irb> a.empty? => false irb> a.member? "hello" => true irb> a.member? "hello," => false irb> a.member? "world" => true irb> a.member? " world" => false irb> a.member? "hello, world" => true irb> a.member? "hello, world!" => false irb> a.delete "hello" => true irb> a.delete "hello" => false irb> a.member? "hello" => false irb> a.size => 2 irb> a.delete "world" => true irb> a.delete "world" => false irb> a.member? "world" => false irb> a.delete "hello, world" => true irb> a.delete "hello, world" => false irb> a.member? "hello, world" => false irb> a.size => 0 irb> a.empty? => true irb> s = "abcabbca" => "abcabbca" irb> for i in 0 ... s.size irb> a.insert(s[i..-1]) irb> end => 0...8 irb> a.size => 8 irb> a.each{|x| print x, "\n"} ["a"] ["a", "b", "b", "c", "a"] ["a", "b", "c", "a", "b", "b", "c", "a"] ["b", "b", "c", "a"] ["b", "c", "a"] ["b", "c", "a", "b", "b", "c", "a"] ["c", "a"] ["c", "a", "b", "b", "c", "a"] => #<Tst: ...> irb> a.common_prefix("a"){|x| print x, "\n"} ["a"] ["a", "b", "b", "c", "a"] ["a", "b", "c", "a", "b", "b", "c", "a"] => #<Tst: ...> irb> a.common_prefix("ab"){|x| print x, "\n"} ["a", "b", "b", "c", "a"] ["a", "b", "c", "a", "b", "b", "c", "a"] => #<Tst: ...> irb> a.common_prefix("abc"){|x| print x, "\n"} ["a", "b", "c", "a", "b", "b", "c", "a"] => #<Tst: ...> irb> a.common_prefix("b"){|x| print x, "\n"} ["b", "b", "c", "a"] ["b", "c", "a"] ["b", "c", "a", "b", "b", "c", "a"] => #<Tst: ...> irb> a.common_prefix("bc"){|x| print x, "\n"} ["b", "c", "a"] ["b", "c", "a", "b", "b", "c", "a"] => #<Tst: ...> irb> a.common_prefix("c"){|x| print x, "\n"} ["c", "a"] ["c", "a", "b", "b", "c", "a"] => #<Tst: ...>
リスト : Ternary Search Tree (tst.rb) class Tst attr_reader :size # TST 用節の定義 class Node attr_accessor :data, :left, :mid, :right def initialize(x) @data = x @left = nil @mid = nil @right = nil end end def initialize(x = '\0') @root = Node.new(nil) # header @leaf = x @size = 0 end # 木の操作関数 private # 探索 def search_node(node, x) while node return node if node.data == x if x < node.data node = node.left else node = node.right end end end # 挿入 # x は節 def insert_node(node, x) if not node return x elsif x.data == node.data return node elsif x.data < node.data node.left = insert_node(node.left, x) else node.right = insert_node(node.right, x) end node end # 最小値を探す def search_min_node(node) if node.left search_min_node(node.left) else node.data end end # 最小値を削除する def delete_min_node(node) if node.left node.left = delete_min_node(node.left) node else node.right end end # 削除 def delete_node(node, x) if node if x == node.data if not node.left return node.right elsif not node.right return node.left else node.data = search_min_node(node.right) node.right = delete_min_node(node.right) end elsif x < node.data node.left = delete_node(node.left, x) else node.right = delete_node(node.right, x) end end node end # 巡回 def traverse_node(node, buff, leaf, &block) if node traverse_node(node.left, buff, leaf, &block) if node.data == leaf yield buff else buff.push node.data traverse_node(node.mid, buff, leaf, &block) buff.pop end traverse_node(node.right, buff, leaf, &block) end end # TSTの操作 public # 探索 def member?(seq) node = @root for i in 0 ... seq.size node = search_node(node.mid, seq[i]) return false unless node end # check leaf search_node(node.mid, @leaf) ? true : false end # 挿入 def insert(seq) node = @root for i in 0 ... seq.size x = seq[i] child = search_node(node.mid, x) if not child child = Node.new(x) node.mid = insert_node(node.mid, child) end node = child end # check leaf if search_node(node.mid, @leaf) false else node.mid = insert_node(node.mid, Node.new(@leaf)) @size += 1 true end end # 削除 def delete(seq) node = @root for i in 0 ... seq.size node = search_node(node.mid, seq[i]) return false unless node end # delete leaf if search_node(node.mid, @leaf) node.mid = delete_node(node.mid, @leaf) @size -= 1 true else false end end # 巡回 def each(&block) traverse_node(@root.mid, [], @leaf, &block) self end # 共通接頭辞を持つデータを求める def common_prefix(seq, &block) node = @root buff = [] for i in 0 ... seq.size x = seq[i] buff.push x node = search_node(node.mid, x) return self unless node end traverse_node(node.mid, buff, @leaf, &block) self end def empty? @size == 0 end def inspect sprintf("#<Tst:%#x>", self.object_id) end end