ツリー構造
計算機科学における「ツリー」とは、階層的なデータ構造を表現するための重要な概念です。ツリーは、一つ以上のノードが親子関係で接続された、木構造のデータを表します。一般的には、根ノード（ルート）から始まり、それに子ノードが接続され、さらにその子ノードにも同様の接続が行われる形態を取ります。
ツリー構造は、階層的な関係や親子関係を表現するのに非常に有用であり、データの組織化や効率的な検索、操作を可能にします。ツリーは、データベースのインデックス、ファイルシステムの階層、コンピュータネットワークの階層的な構造など、さまざまな領域で広く利用されています。
ツリーの種類
[編集]ツリーにはいくつかの種類があります。代表的なものを以下に挙げます。
- 二分木（Binary Tree） 二分木は、各ノードが最大で2つの子ノードを持つツリーです。各ノードは左の子ノードと右の子ノードを持ち、特定の順序でデータが格納されます。
- 二分探索木（Binary Search Tree） 二分探索木は、二分木の一種であり、各ノードが高々2つの子ノードを持つ木構造です。左部分木の全てのノードの値が、親ノードの値よりも小さく、右部分木の全てのノードの値が親ノードの値よりも大きい性質を持ちます。この性質により、データの挿入、削除、検索などの操作を効率的に行うことができます。
- 平衡二分探索木（Self-balancing Binary Search Tree） 平衡二分探索木は、ツリー内のノードの高さの差が1より大きくならないように調整された二分木です。これにより、ツリーの高さが大幅に増加することを防ぎ、検索や挿入などの操作の効率を向上させます。代表的な平衡二分探索木には、AVL木や赤黒木などがあります。
- N分木（N-ary Tree） N分木は、各ノードが最大でN個の子ノードを持つツリーです。二分木は特別な場合であり、Nが2であるN分木と言えます。N分木は、特にファイルシステムやデータ構造の表現など、複数の子ノードが必要な場面で使用されます。
- トライ木（Trie Tree） トライ木は、文字列の集合を格納するために使用される特殊なデータ構造です。各ノードは通常、アルファベットの1文字を表し、ツリーの根から葉までの経路は文字列を表します。トライ木は、文字列の検索や辞書の実装などに効率的です。
- セグメント木（Segment Tree） セグメント木は、数値の区間に関するクエリを高速に処理するためのデータ構造です。各ノードは、区間内のデータの要約を保持し、ツリーの根には全体の区間の情報が格納されます。セグメント木は、範囲クエリの処理や区間更新などの操作を効率的に行うことができます。
これらは代表的なツリーの種類ですが、他にも様々な種類が存在します。適切なツリーの種類を選択することは、特定の問題やアプリケーションにおいて効率的なデータ操作を行うために重要です。
平衡二分探索木
[編集]平衡二分探索木には、以下のようなものがあります:
- AVL木（Adelson-Velskii and Landis' Tree） AVL木は、各ノードの高さの差が1以下であるというバランス条件を満たします。これにより、木の高さが常にO(log n)となり、挿入や削除操作においても効率的な検索が可能となります。ノードの挿入や削除後に、回転操作を行ってバランスを修復します。
- 赤黒木（Red-black_tree） 赤黒木は、各ノードに赤または黒の色を付け、一定の条件を満たすことでバランスを保つ木構造です。条件は以下の通りです：
- ルートは黒である。
- 赤のノードの子ノードは全て黒である。
- 各ノードから葉ノードまでの黒のノード数は同じである（黒の高さが一定）。
- これにより、挿入、削除、検索操作を効率的に行うことができます。
- Splay木 Splay木は、最近アクセスされたノードをルートに移動させることによって操作を効率化する平衡二分探索木です。挿入、削除、検索の操作において、最近アクセスされたノードがより高い位置に移動し、アクセスされたノードがより頻繁にアクセスされるようになります。
- Treap Treapは、二分探索木とランダムヒープの両方の性質を持つデータ構造です。各ノードにはキーと優先度があり、キーは二分探索木の性質を満たし、優先度はヒープの性質を満たします。ランダムな優先度に基づいて平衡が保たれるため、Treapは単純で効率的な平衡二分探索木として知られています。
- アバランチ木（AVL-Trie） アバランチ木は、AVL木とトライ（Trie）の特性を組み合わせたデータ構造です。キーのビットごとのプレフィックスを使ってノードを構築し、各ノードは平衡されたAVL木を保持します。この組み合わせにより、高速な挿入、削除、検索が可能となります。
- AA木 AA木は、アドレス総和（Address-Adjusted）木として知られており、赤黒木のような平衡二分探索木です。しかし、AA木では赤黒木とは異なるバランス条件が使用されています。AA木は、比較的シンプルな操作に基づいて平衡が保たれます。
これらの平衡二分探索木は、それぞれ異なるアプローチを使用して平衡を実現し、異なる利点とトレードオフを持っています。どのデータ構造を選択するかは、特定のアプリケーションの要件や性能目標に依存します。
ツリーの操作
[編集]ツリーには、さまざまな操作があります。代表的なものを以下に説明します。
- 挿入（Insertion）: ツリーに新しいノードを挿入する操作です。挿入されたノードは、適切な位置に配置され、ツリーの構造が保持されます。例えば、二分探索木では、新しいノードは適切な位置に挿入され、ツリーが二分探索木の性質を維持します。
- 削除（Deletion）: ツリーから特定のノードを削除する操作です。削除されたノードの子ノードや親ノードの接続が適切に調整され、ツリーの構造が保持されます。削除操作は、ノードの種類やツリーの種類に応じてさまざまな場合があります。
- 検索（Search）: ツリー内で特定の値を持つノードを見つける操作です。一般的な検索操作は、再帰的な深さ優先探索や幅優先探索などのアルゴリズムを使用して行われます。特に、二分探索木では、効率的な二分探索アルゴリズムが使用されます。
- 走査（Traversal）: ツリー内のすべてのノードを訪問する操作です。一般的な走査方法には、前順走査（Preorder traversal）、中順走査（Inorder traversal）、後順走査（Postorder traversal）などがあります。これらの走査方法は、ツリー内のノードを特定の順序で訪問するために使用されます。
- 更新（Update）: ツリー内の特定のノードの値を変更する操作です。更新操作は、ツリーが特定の属性や状態を持つ場合に有用です。更新操作は、検索操作と組み合わせて使用されることがあります。
これらはツリーの基本的な操作ですが、特定のアプリケーションや問題に応じて、さらに多くの操作が必要になる場合があります。ツリーの操作は、データの効率的な管理や操作を可能にし、多くのアルゴリズムやデータ構造の基礎となります。
反復処理
[編集]ツリーにおける反復処理は、ツリー内のすべての要素を訪問する操作です。主な方法には、深さ優先探索（Depth-First Search, DFS）と幅優先探索（Breadth-First Search, BFS）の2つがあります。それぞれの方法について説明します。
- 深さ優先探索（Depth-First Search, DFS）:
- 深さ優先探索は、ツリーの最大深さまで進んでから次の子ノードに移動する方法です。典型的には再帰的な手法で実装されますが、明示的なスタック（Stack）を使用することもあります。深さ優先探索は、更に以下の３種類に分類されます。
- 先行順序探索（preorder_traversal）:
- ルート、左部分木、右部分木の順に探索する。
- 中間順序探索（inorder_traversal）:
- 左部分木、ルート、右部分木の順に探索する。
- 後行順序探索（postorder_traversal）:
- 左部分木、右部分木、ルートの順に探索する。
- 幅優先探索（Breadth-First Search, BFS）:
- 幅優先探索は、ツリーの各レベルを左から右に順番に探索する方法です。通常はキュー（Queue）を使用して実装されます。
これらの方法を使用することで、ツリー内のすべての要素を効率的に訪問することができます。深さ優先探索は、再帰の性質を利用して実装が比較的簡単ですが、スタックの深さが大きくなる可能性があるため、非再帰的な手法も使用されます。一方幅優先探索は、通常はキューを使用した非再帰的な手法で実装されます。
Ruby
[編集]RubyのEnumerableモジュールは、eachメソッドを含む様々な反復処理に関連するメソッドを提供するためのミックスインです。これにより、クラスがEnumerableモジュールをincludeすると、eachメソッドを実装するだけで、map、select、reduceなど、多くの便利なメソッドを利用することができます。
ツリー構造の場合、Enumerableモジュールをincludeし、eachメソッドを中間順序探索（inorder traversal）として実装することで、簡単にツリーを反復処理することができます。中間順序探索は、左部分木、ルート、右部分木の順に要素を訪問する方法であり、これをeachメソッドによって実装することで、ツリー内の要素を効率的かつ直感的に取得することができます。
Kotlin
[編集]KotlinのIterableインターフェースは、各メソッドを含む様々な反復処理に関連するメソッドを提供するためのインターフェースです。これにより、クラスがIterableを実装すると、forEachなどの便利なメソッドを利用することができます。
ツリー構造の場合、Iterableを実装し、iteratorメソッドを中間順序探索（inorder traversal）として実装することで、簡単にツリーを反復処理することができます。中間順序探索は、左部分木、ルート、右部分木の順に要素を訪問する方法であり、これをiteratorメソッドによって実装することで、ツリー内の要素を効率的かつ直感的に取得することができます。
このように、KotlinではIterableインターフェースを使用して反復処理を行います。RubyのEnumerableモジュールと同様に、Iterableインターフェースも様々な便利なメソッドを提供し、ツリー構造の反復処理を簡潔かつ効率的に実装することができます。
Rust
[編集]RustのIteratorトレイトは、各メソッドを含む様々な反復処理に関連するトレイトを提供するためのトレイトです。これにより、クラスがIteratorトレイトを実装すると、map、filter、foldなどの便利なメソッドを利用することができます。
ツリー構造の場合、Iteratorトレイトを実装し、nextメソッドを中間順序探索（inorder traversal）として実装することで、簡単にツリーを反復処理することができます。中間順序探索は、左部分木、ルート、右部分木の順に要素を訪問する方法であり、これをnextメソッドによって実装することで、ツリー内の要素を効率的かつ直感的に取得することができます。
このように、RustではIteratorトレイトを使用して反復処理を行います。RubyのEnumerableモジュールやKotlinのIterableインターフェースと同様に、Iteratorトレイトも様々な便利なメソッドを提供し、ツリー構造の反復処理を実装する際に役立ちます。
JavaScript
[編集]JavaScriptのIteratorプロトコルは、Symbol.iteratorメソッドを含むオブジェクトに対して使用され、反復処理を行うためのプロトコルです。これにより、オブジェクトがIteratorプロトコルを実装すると、for...ofループなどの便利な機能を利用することができます。
ツリー構造の場合、Iteratorプロトコルを実装し、[Symbol.iterator]() メソッドを中間順序探索（inorder traversal）として実装することで、簡単にツリーを反復処理することができます。中間順序探索は、左部分木、ルート、右部分木の順に要素を訪問する方法であり、これを[Symbol.iterator]() メソッドによって実装することで、ツリー内の要素を効率的かつ直感的に取得することができます。
このように、JavaScriptではIteratorプロトコルを使用して反復処理を行います。Iteratorプロトコルは、Symbol.iteratorメソッドを含むオブジェクトに適用され、反復処理を可能にします。これにより、for...ofループなどの便利な機能を使用して、ツリー構造の要素を効率的に処理することができます。
Python
[編集]Pythonのイテレータプロトコルは、__iter__() と __next__() メソッドを持つオブジェクトに対して使用され、反復処理を行うためのプロトコルです。これにより、オブジェクトがイテレータプロトコルを実装すると、forループなどの便利な機能を利用することができます。
ツリー構造の場合、イテレータプロトコルを実装し、__iter__() メソッドを中間順序探索（inorder traversal）として実装することで、簡単にツリーを反復処理することができます。中間順序探索は、左部分木、ルート、右部分木の順に要素を訪問する方法であり、これを__iter__() メソッドによって実装することで、ツリー内の要素を効率的かつ直感的に取得することができます。
このように、Pythonではイテレータプロトコルを使用して反復処理を行います。イテレータプロトコルは、__iter__() メソッドと __next__() メソッドを持つオブジェクトに適用され、反復処理を可能にします。これにより、forループなどの便利な機能を使用して、ツリー構造の要素を効率的に処理することができます。
Go
[編集]Goでの反復処理の実装は、イテレータパターンで実現するのが一般的です。
ツリー構造の反復にイテレータパターンを適用する際には、各ノードを訪れるための方法と、必要に応じてノードを追加する方法を定義する必要があります。以下は、イテレータパターンを使用してツリー構造を反復処理する基本的な手順です。
- イテレータインターフェースの定義: ツリーの要素を反復するためのインターフェースを定義します。このインターフェースには、次のノードを返すメソッドや、反復が終了したかどうかを示すメソッドが含まれる場合があります。
- ツリーのノードを表すクラスの作成: ツリーのノードを表すクラスを作成します。このクラスには、ノードの値や子ノードへの参照が含まれます。
- イテレータの実装: ツリーの反復を実装する具象イテレータクラスを作成します。このクラスは、定義したイテレータインターフェースを実装し、ツリーの要素を反復します。
- 反復処理の実行: クライアントコードで、イテレータを使用してツリーを反復処理します。通常は、
forループや他の反復構造を使用して、ツリー内の要素を順番に処理します。
Goでは、イテレータパターンをより一般化・抽象化する取り組みが2024年２月時点で行われており、標準ライブラリやフレームワークとして実装されるかもしれません。
Java
[編集]Javaでは、Iterable インターフェースと Iterator インターフェースが反復処理を一般化するために使用されます。Iterable インターフェースは、反復子を提供する iterator() メソッドを定義し、Iterator インターフェースは、hasNext() メソッドと next() メソッドを定義しています。
C#
[編集]C#では、IEnumerable インターフェースと IEnumerator インターフェースが反復処理を一般化するために使用されます。IEnumerable インターフェースは、GetEnumerator() メソッドを定義し、IEnumerator インターフェースは、MoveNext() メソッドと Current プロパティを定義しています。
C++
[編集]C++でも反復処理を一般化するための機能がいくつかあります。
- 範囲ベースのforループ: C++11以降、範囲ベースのforループが導入され、これにより範囲内のすべての要素を簡潔に反復できるようになりました。
- STLイテレータ: C++の標準テンプレートライブラリ（STL）では、反復処理をサポートするためにイテレータが使用されます。STLの多くのコンテナやアルゴリズムは、イテレータを介して反復処理を行います。
- イテレータパターンの実装: ユーザー定義のクラスやデータ構造に対して、イテレータパターンを実装することも可能です。これにより、クラスの内部構造を隠蔽しつつ、外部から反復処理を行うことができます。
これらの方法を使用して、C++でさまざまな種類のデータ構造やコンテナに対して反復処理を行うことができます。
二分木
[編集]二分木（Binary Tree）は、各ノードが最大で2つの子ノードを持つ木構造のデータ構造です。各ノードは通常、親ノードと子ノードへのリンクを持ち、また特定のデータを保持します。二分木では、左の子ノードと右の子ノードがあり、それぞれの子ノードは親ノードよりも小さい（または同じ）値を持つ場合（左の子ノード）と大きい値を持つ場合（右の子ノード）に配置されます。
二分木は多くの場面で使用されます。例えば、データの探索や挿入、削除などの操作を効率的に行うために利用されます。また、再帰的なアルゴリズムやデータ構造を理解するための基本的な概念としても役立ちます。
Ruby
[編集]- bt.rb
# frozen_string_literal: true # 二分木クラス class BinaryTree include Enumerable # Enumerableモジュールを含める # 二分木のノード TreeNode = Struct.new(:value, :left, :right) def self.new_node(*args) = TreeNode.new(*args) # 新しいツリーを作成 def initialize(*_args) @root = nil end attr_accessor :root def height(node = @root) = node.nil? ? 0 : 1 + [height(node.left), height(node.right)].max def search(key, _node = @root) raise TypeError, "Invalid value: #{key.inspect}" unless key.respond_to?(:<) raise TypeError, "Invalid value: #{key.inspect}" if key.is_a?(Numeric) && !key.finite? any? { |i| i == key } end # 深さ優先探索（DFS; depth-first search）; # 先行順序（preorder）で木を走査し、各ノードの値をブロックに渡します。 # # @yieldparam value [Object] 各ノードの値 def preorder_traversal(node = @root, &block) return to_enum(__method__, node) unless block def core(node, &block) return if node.nil? yield node.value core(node.left, &block) core(node.right, &block) end core(node, &block) self end alias dfs preorder_traversal def preorder_traversal_iterative(node = @root, &block) return to_enum(__method__, node) unless block stack = [node] until stack.empty? node = stack.pop yield node.value stack.push node.right if node.right stack.push node.left if node.left end self end # 中間順序（inorder）で木を走査し、各ノードの値をブロックに渡します。 # # @yieldparam value [Object] 各ノードの値 def inorder_traversal(node = @root, &block) return to_enum(__method__, node) unless block def core(node, &block) return if node.nil? core(node.left, &block) yield node.value core(node.right, &block) end core(node, &block) self end alias each inorder_traversal def inorder_traversal_iterative(node = @root, &block) return to_enum(__method__, node) unless block stack = [] loop do if node stack.push(node) node = node.left elsif !stack.empty? node = stack.pop yield node.value node = node.right else break end end self end # 後行順序（postorder）で木を走査し、各ノードの値をブロックに渡します。 # # @yieldparam value [Object] 各ノードの値 def postorder_traversal(node = @root, &block) return to_enum(__method__, node) unless block def core(node, &block) return if node.nil? core(node.left, &block) core(node.right, &block) yield node.value end core(node, &block) self end def postorder_traversal_iterative(node = @root, &block) return to_enum(__method__, node) unless block stack = [node] values = [] until stack.empty? node = stack.pop values << node.value stack.push node.left if node.left stack.push node.right if node.right end yield values.pop until values.empty? self end # 幅優先探索（Breadth-First Search）を行い、各ノードの値をブロックに渡します。 # # @yieldparam value [Object] 各ノードの値 def bfs return to_enum(__method__) unless block_given? return unless @root queue = [@root] until queue.empty? node = queue.shift yield node.value queue.push(node.left) if node.left queue.push(node.right) if node.right end self end # ツリーの文字列表現を返します。 # # Returns ツリーを表す文字列。 def to_s = "(#{to_a.join ' '})" # ツリーのデバッグ用表現を返します。 # # Returns デバッグ用表現を表す文字列。 def inspect ="#{self.class}(#{to_a.join ', '})" # ノードの値をインデントで深さを表現して文字列化します。 # # @param node [Node] ノード # @param level [Integer] ノードの深さ # @param indent [String] インデント文字列 # @return [String] ノードの値をインデントで深さを表現した文字列 def to_indented_s(node = @root, level = 0, indent = ' ') return '' if node.nil? to_indented_s(node.left, level + 1, indent) + "#{indent * level}#{node.value}\n" + to_indented_s(node.right, level + 1, indent) end end require 'minitest/autorun' describe BinaryTree do before do # 二分木の構造を作成 # 5 # / \ # 3 7 # / \ \ # 2 4 8 @tree = BinaryTree.new @tree.root = BinaryTree.new_node(5) @tree.root.left = BinaryTree.new_node(3) @tree.root.left.left = BinaryTree.new_node(2) @tree.root.left.right = BinaryTree.new_node(4) @tree.root.right = BinaryTree.new_node(7) @tree.root.right.right = BinaryTree.new_node(8) end describe '#height' do it 'should calculate the height correctly' do _((@tree.height)).must_equal 3 _((@tree.height(@tree.root.left))).must_equal 2 _((@tree.height(@tree.root.right))).must_equal 2 end end describe '#search' do it 'should find the value in the tree' do _((@tree.search(5))).must_equal true _((@tree.search(2))).must_equal true _((@tree.search(8))).must_equal true end it 'should not find the value not in the tree' do _((@tree.search(10))).must_equal false end end describe '#preorder_traversal' do it 'should traverse the tree in preorder' do _((@tree.preorder_traversal.to_a)).must_equal [5, 3, 2, 4, 7, 8] end end describe '#inorder_traversal' do it 'should traverse the tree in inorder' do _((@tree.inorder_traversal.to_a)).must_equal [2, 3, 4, 5, 7, 8] end end describe '#postorder_traversal' do it 'should traverse the tree in postorder' do _((@tree.postorder_traversal.to_a)).must_equal [2, 4, 3, 8, 7, 5] end end describe '#bfs' do it 'should traverse the tree in breadth-first order' do _((@tree.bfs.to_a)).must_equal [5, 3, 7, 2, 4, 8] end end describe '#to_s' do it 'should return a string representation of the tree' do _((@tree.to_s)).must_equal '(2 3 4 5 7 8)' end end describe '#inspect' do it 'should return a debug representation of the tree' do _((@tree.inspect)).must_equal 'BinaryTree(2, 3, 4, 5, 7, 8)' end end describe '#to_indented_s' do it 'should return an indented string representation of the tree' do expected = <<~INDENTED 2 3 4 5 7 8 INDENTED _((@tree.to_indented_s.chomp)).must_equal expected.chomp end end end
二分探索木
[編集]二分探索木（Binary Search Tree、BST）は、データ構造の一種です。
二分探索木は、各ノードが以下の性質を満たす木構造です。
- 各ノードには、1つのキーがあります。
- 左部分木に含まれるすべてのノードのキーは、そのノードのキーよりも小さくなります。
- 右部分木に含まれるすべてのノードのキーは、そのノードのキーよりも大きくなります。
- 同じキーを持つノードは存在しません。
この性質により、二分探索木は効率的な探索、挿入、削除が可能になります。探索を行う場合、目的のキーと比較しながら、木の構造を辿っていくことで、目的のキーを持つノードを見つけることができます。挿入や削除を行う場合も、二分探索木の性質を保ちつつ操作を行うことで、木のバランスを保ちながら効率的な操作を実現します。 しかし、二分探索木の性能は挿入や削除の際に木のバランスが崩れる可能性があるため、バランスを保つアルゴリズム（例：AVL木や赤黒木）を使用することがあります。
Ruby
[編集]- bst.rb
# frozen_string_literal: true require_relative 'bt' # 二分探索木クラス class BinarySearchTree < BinaryTree # 新しい二分探索木を作成します。 # # @param args [Array<Object>] 挿入する要素の配列 # @yield [element] ブロックが与えられた場合、各要素に対してブロックを実行し、その結果を挿入します。 # @yieldparam element [Object] 要素 def initialize(*args, &block) @root = nil case [args, block] in [[Array => ary], nil] ary.each { insert _1 } in [[Array => ary], Proc] ary.each { insert block[_1] } in [[], nil] else raise ArgumentError, "#{self.class}#initialize: #{args.inspect}" end end # 二分探索木に新しい値を挿入します。 # # @param value [Object] 挿入する値 # @return [BinarySearchTree] 自身のインスタンス def insert(value, node = @root) raise TypeError, "Invalid value: #{value.inspect}" unless value.respond_to?(:<) raise TypeError, "Invalid value: #{value.inspect}" if value.is_a?(Numeric) && !value.finite? @root = insert_recursive(value, node) # @root = insert_iterative(value, node) self end # 指定されたキーを持つ要素が存在するかどうかを返します。 # # @param key [Object] 検索するキー # @return [Boolean] 指定されたキーを持つ要素が存在する場合はtrue、それ以外の場合はfalse def search(key, node = @root) raise TypeError, "Invalid value: #{key.inspect}" unless key.respond_to?(:<) raise TypeError, "Invalid value: #{key.inspect}" if key.is_a?(Numeric) && !key.finite? search_recursive(key, node) # search_iterative(key, node) end # 指定されたキーを持つ要素を削除します。 # # @param key [Object] 削除する要素のキー # @return [BinarySearchTree] 自身のインスタンス def delete(key, node = @root) raise TypeError, "Invalid value: #{key.inspect}" unless key.respond_to?(:<) raise TypeError, "Invalid value: #{key.inspect}" if key.is_a?(Numeric) && !key.finite? @root = delete_node(key, node) self end protected # 二分探索木に値を再帰的に挿入します。 # # @param node [Node, nil] 現在のノード # @param value [Object] 挿入する値 # @return [Node] 挿入後のノード def insert_recursive(value, node) return self.class.new_node(value) if node.nil? case value <=> node.value when -1 then node.left = insert_recursive(value, node.left) when 1 then node.right = insert_recursive(value, node.right) when 0 # sum value else raise TypeError, value.inspect end node end def insert_iterative(value, node) return Node.new(value) if node.nil? prev = nil temp = node until temp.nil? prev = temp temp = case value <=> temp.value when -1 then temp.left when +1 then temp.right when 0 then break else raise TypeError, value.inspect end end unless prev.nil? case value <=> prev.value when -1 then prev.left = Node.new(value) when +1 then prev.right = Node.new(value) when 0 # break else raise TypeError, value.inspect end end node end def search_recursive(key, node) return false if node.nil? case key <=> node.value when -1 then search_recursive(key, node.left) when +1 then search_recursive(key, node.right) when 0 then true else raise TypeError, "#{self.class}#search_recursive: #{key.inspect}" end end def search_iterative(key, node) until node.nil? node = case node.value <=> key when -1 then node.left when +1 then node.right when 0 then return true else raise TypeError, "#{self.class}#search_iterative: #{key.inspect}" end end false end def delete_node(key, node) return node if node.nil? case key <=> node.value when -1 node.left = delete_node(key, node.left) return node when 1 node.right = delete_node(key, node.right) return node when 0 # sum value else raise TypeError, value.inspect end if node.left.nil? return node.right elif node.right.nil? root.left else succParent = node succ = node.right while succ.left succParent = succ succ = succ.left end if succParent != node succParent.left = succ.right else succParent.right = succ.right end node.value = succ.value node end end end def BinarySearchTree(args) = BinarySearchTree.new(args) require 'minitest/autorun' describe BinarySearchTree do describe '#initialize' do it 'creates an empty tree when no arguments are given' do tree = BinarySearchTree.new _(tree.root).must_be_nil end it 'creates a tree with elements from an array' do tree = BinarySearchTree.new([5, 3, 7, 2, 4, 6, 8]) _(tree.inorder_traversal.to_a).must_equal [2, 3, 4, 5, 6, 7, 8] end it 'creates a tree with transformed elements from an array and a block' do tree = BinarySearchTree.new([1, 2, 3]) { |n| n * 2 } _(tree.inorder_traversal.to_a).must_equal [2, 4, 6] end it 'raises an ArgumentError when invalid arguments are given' do _(proc { BinarySearchTree.new(1, 2, 3) }).must_raise ArgumentError end end describe '#insert' do before do @tree = BinarySearchTree.new end it 'inserts a new value into the tree' do @tree.insert(5) @tree.insert(3) @tree.insert(7) _((@tree.inorder_traversal.to_a)).must_equal [3, 5, 7] end it 'raises a TypeError when trying to insert an invalid value' do _(proc { @tree.insert(nil) }).must_raise TypeError _(proc { @tree.insert(Float::INFINITY) }).must_raise TypeError end end describe '#search' do before do @tree = BinarySearchTree.new([5, 3, 7, 2, 4, 6, 8]) end it 'returns true if the value is present in the tree' do _((@tree.search(5))).must_equal true _((@tree.search(3))).must_equal true _((@tree.search(8))).must_equal true end it 'returns false if the value is not present in the tree' do _((@tree.search(1))).must_equal false _((@tree.search(9))).must_equal false end it 'raises a TypeError when trying to search for an invalid value' do _(proc { @tree.search(nil) }).must_raise TypeError _(proc { @tree.search(Float::INFINITY) }).must_raise TypeError end end describe '#delete' do before do @tree = BinarySearchTree.new([5, 3, 7, 2, 4, 6, 8]) end it 'deletes a value from the tree' do @tree.delete(3) _((@tree.inorder_traversal.to_a)).must_equal [2, 4, 5, 6, 7, 8] end it 'deletes the root node correctly' do @tree.delete(5) _((@tree.inorder_traversal.to_a)).must_equal [2, 3, 4, 6, 7, 8] end it 'raises a TypeError when trying to delete an invalid value' do _(proc { @tree.delete(nil) }).must_raise TypeError _(proc { @tree.delete(Float::INFINITY) }).must_raise TypeError end end end
AVL木
[編集]AVL木（Adelson-Velskii and Landis' Tree）は、自己バランス二分探索木（Self-Balancing Binary Search Tree）の一種であり、その名前は発明者であるゲオルク・アドルフ・アドルフ・ヘルツスとルドルフ・バイエルに由来します。AVL木は、挿入や削除などの操作によって木の形状が変化しても、常にバランスを保ちます。
バランスの保持は、各ノードの左部分木と右部分木の高さの差が1以下になるように調整されます。これにより、AVL木では最長経路と最短経路の高さの差が1以下になります。
AVL木のバランスを保つために、挿入や削除の際に自動的に回転操作が行われます。これによって、木のバランスが修正され、効率的な探索が可能になります。
AVL木の探索時間は、平均的にはO(log n)です。この効率的な探索時間は、データの追加や削除が頻繁に行われる場合でも一貫して維持されます。
Ruby
[編集]AVL木は二分木の一種なので、AVLTreeはBinaryTreeを継承し差分プログラミング（difference coding）を試みました。
- avlt.rb
# frozen_string_literal: true require_relative 'bt' # Ruby program for insertion in AVL Tree class Node attr_accessor :key, :height, :left, :right def initialize(d) @key = d @height = 1 @left = nil @right = nil end def value=(d) @key = d end def value @key end end class AVLTree < BinaryTree # 新しい二分探索木を作成します。 # # @param args [Array<Object>] 挿入する要素の配列 # @yield [element] ブロックが与えられた場合、各要素に対してブロックを実行し、その結果を挿入します。 # @yieldparam element [Object] 要素 def initialize(*args) @root = nil case args in [Array(*ary)] if block_given? ary.each { insert yield(_1) } else ary.each { insert _1 } end in [] else raise ArgumentError, "#{self.class}#initialize: #{args.inspect}" end end def insert(key, node = @root) = @root = insert_(key, node) def delete(key) = delete_node(@root, key) private # A utility function to right # rotate subtree rooted with y # See the diagram given above. def right_rotate(y) x = y.left t2 = x.right # Perform rotation x.right = y y.left = t2 # Update heights y.height = 1 + [height(y.left), height(y.right)].max x.height = 1 + [height(x.left), height(x.right)].max # Return new root x end # A utility function to left # rotate subtree rooted with x # See the diagram given above. def left_rotate(x) y = x.right t2 = y.left # Perform rotation y.left = x x.right = t2 # Update heights x.height = 1 + [height(x.left), height(x.right)].max y.height = 1 + [height(y.left), height(y.right)].max # Return new root y end # Get Balance factor of node N def get_balance(n) n.nil? ? 0 : height(n.left) - height(n.right) end def insert_(key, node = @root) # 1. Perform the normal BST insertion return Node.new(key) if node.nil? if key < node.key node.left = insert_(key, node.left) elsif key > node.key node.right = insert_(key, node.right) else return node # Duplicate keys not allowed end # 2. Update height of this ancestor node node.height = 1 + [height(node.left), height(node.right)].max # 3. Get the balance factor of this ancestor # node to check whether this node became # unbalanced balance = get_balance(node) # If this node becomes unbalanced, then there # are 4 cases # Left Left Case return right_rotate(node) if balance > 1 && key < node.left.key # Right Right Case return left_rotate(node) if balance < -1 && key > node.right.key # Left Right Case if balance > 1 && key > node.left.key node.left = left_rotate(node.left) return right_rotate(node) end # Right Left Case if balance < -1 && key < node.right.key node.right = right_rotate(node.right) return left_rotate(node) end # return the (unchanged) node pointer node end def min_value_node(node) current = node current = current.left until current.left.nil? current end def delete_node(root, key) return root if root.nil? if key < root.key root.left = delete_node(root.left, key) elsif key > root.key root.right = delete_node(root.right, key) elsif root.left.nil? || root.right.nil? temp = root.left.nil? ? root.right : root.left root = if temp.nil? nil else temp end else temp = min_value_node(root.right) root.key = temp.key root.right = delete_node(root.right, temp.key) end return root if root.nil? root.height = 1 + [height(root.left), height(root.right)].max balance = get_balance(root) return right_rotate(root) if balance > 1 && get_balance(root.left) >= 0 if balance > 1 && get_balance(root.left).negative? root.left = left_rotate(root.left) return right_rotate(root) end return left_rotate(root) if balance < -1 && get_balance(root.right) <= 0 if balance < -1 && get_balance(root.right).positive? root.right = right_rotate(root.right) return left_rotate(root) end root end end ############## require 'minitest' class AVLTreeTest < Minitest::Test def setup @tree = AVLTree.new end # 配列を使ってコンストラクタをテストします。 def test_constructor_with_array @tree = AVLTree.new([7, 5, 8]) assert_equal '(5 7 8)', @tree.to_s end def test_height [10, 5, 15, 3, 7, 12, 18].each { @tree.insert _1 } assert_equal '(3 5 7 10 12 15 18)', @tree.to_s assert_equal 'AVLTree(3, 5, 7, 10, 12, 15, 18)', @tree.inspect assert_equal 3, @tree.height @tree.insert 2 assert_equal 4, @tree.height @tree.insert 1 assert_equal 4, @tree.height @tree.insert 0 assert_equal 4, @tree.height @tree.insert(-1) assert_equal 4, @tree.height @tree.insert(-2) assert_equal 4, @tree.height assert_equal 'AVLTree(-2, -1, 0, 1, 2, 3, 5, 7, 10, 12, 15, 18)', @tree.inspect end def test_inorder_traversal [10, 5, 15, 3, 7, 12, 18].each { @tree.insert _1 } expected_output = '3 5 7 10 12 15 18 ' @tree.insert 10 actual_output = capture_stdout { @tree.inorder_traversal { |value| print "#{value} " } } assert_equal expected_output, actual_output end def test_to_indented_s [10, 5, 15, 3, 7, 12, 18].each { @tree.insert _1 } assert_equal(" 3\n 5\n 7\n10\n 12\n 15\n 18\n", @tree.to_indented_s) end def test_search # skip '未実装' [10, 5, 15, 3, 7, 12, 18].each { @tree.insert _1 } assert_equal(true, @tree.search(5)) end def test_delete # skip '未実装' [10, 5, 15, 3, 7, 12, 18].each { @tree.insert _1 } assert_equal 'AVLTree(3, 5, 7, 10, 12, 15, 18)', @tree.inspect @tree.delete(5) assert_equal 'AVLTree(3, 7, 10, 12, 15, 18)', @tree.inspect end # 巨大な木を作るテスト def test_build_large_tree i = 0 n = 1000 open('/usr/share/dict/words') do |f| while (s = f.gets) @tree.insert(s) i += 1 break if i >= n end end assert_equal 10, @tree.height assert_equal n, @tree.count end private # 標準出力をキャプチャして文字列として返す def capture_stdout original_stdout = $stdout $stdout = StringIO.new yield $stdout.string ensure $stdout = original_stdout end end Minitest.run if $PROGRAM_NAME == __FILE__
赤黒木
[編集]赤黒木（Red-Black Tree）は、バランス二分木の一種であり、各ノードが追加されたときに特定の条件を満たすように再構築されるデータ構造です。
赤黒木は、以下の性質を持つ木構造です：
- 各ノードは「赤」または「黒」の色を持ちます。
- 根（root）ノードは必ず黒である。
- すべての葉（NILノードまたはnullノード）は黒である。
- 赤のノードの子はすべて黒である。
- あるノードからその子孫へのあらゆる単純なパスには、黒いノードの数が同じでなければならない（これは「黒の高さが一定」とも呼ばれます）。
これらの性質により、赤黒木は追加、削除、検索などの操作において、平均的に効率的な性能を提供します。赤黒木は、データベースの索引や標準ライブラリのセットなど、さまざまなアプリケーションで広く使用されています。
Ruby
[編集]赤黒木（Red-Black Tree）は、BinaryTreeを拡張することで実装できます。赤黒木は、追加の要件として各ノードが「赤」または「黒」の色を持ち、特定の条件（赤の親と赤の子を持たないなど）が満たされる必要があります。以下に、BinaryTreeを継承し、赤黒木を実装する方法を示します。
赤黒木は二分木の一種なので、RedBlackTreeはBinaryTreeを継承し差分プログラミング（difference coding）を試みました。
- rbt.rb
# frozen_string_literal: true require_relative 'bt' class RedBlackTree < BinaryTree class Node attr_accessor :data, :left, :right, :colour, :parent def initialize(data) @data = data @left = nil @right = nil @colour = 'R' @parent = nil end def value @data end def value=(date) @data = date end end def initialize(*args) @root = nil @ll = false # Left-Left Rotation flag @rr = false # Right-Right Rotation flag @lr = false # Left-Right Rotation flag @rl = false # Right-Left Rotation flag case args in [Array(*ary)] if block_given? ary.each { insert yield(_1) } else ary.each { insert _1 } end in [] else raise ArgumentError, "#{self.class}##{__method__}: #{args.inspect}" end end # Public method to insert data into the tree def insert(data) if @root.nil? @root = Node.new(data) @root.colour = 'B' else @root = insert_help(@root, data) end end # ツリーの文字列表現を返します。 # # Returns ツリーを表す文字列。 def to_s = "(#{to_a.join ' '})" # ツリーのデバッグ用表現を返します。 # # Returns デバッグ用表現を表す文字列。 def inspect ="#{self.class}(#{to_a.join ', '})" private # Function to perform left rotation def rotate_left(node) x = node.right y = x.left x.left = node node.right = y node.parent = x y.parent = node unless y.nil? x end # Function to perform right rotation def rotate_right(node) x = node.left y = x.right x.right = node node.left = y node.parent = x y.parent = node unless y.nil? x end # Helper function for insertion def insert_help(root, data) f = false if root.nil? return Node.new(data) elsif data < root.data root.left = insert_help(root.left, data) root.left.parent = root f = true if root != @root && root.colour == 'R' && root.left.colour == 'R' elsif data > root.data root.right = insert_help(root.right, data) root.right.parent = root f = true if root != @root && root.colour == 'R' && root.right.colour == 'R' end # Rotate and recolor based on flags if @ll root = rotate_left(root) root.colour = 'B' root.left.colour = 'R' @ll = false elsif @rr root = rotate_right(root) root.colour = 'B' root.right.colour = 'R' @rr = false elsif @rl root.right = rotate_right(root.right) root.right.parent = root root = rotate_left(root) root.colour = 'B' root.left.colour = 'R' @rl = false elsif @lr root.left = rotate_left(root.left) root.left.parent = root root = rotate_right(root) root.colour = 'B' root.right.colour = 'R' @lr = false end # Handle RED-RED conflict if f if root.parent.right == root if root.parent.left.nil? || root.parent.left.colour == 'B' @rl = true if !root.left.nil? && root.left.colour == 'R' @ll = true if !root.right.nil? && root.right.colour == 'R' else root.parent.left.colour = 'B' root.colour = 'B' root.parent.colour = 'R' if root.parent != @root end elsif root.parent.right.nil? || root.parent.right.colour == 'B' @rr = true if !root.left.nil? && root.left.colour == 'R' @lr = true if !root.right.nil? && root.right.colour == 'R' else root.parent.right.colour = 'B' root.colour = 'B' root.parent.colour = 'R' if root.parent != @root end false end root end end require 'minitest' #:Minitest::Test class RedBlackTreeTest < BinaryTreeTest def initialize(*args) super(*args) @target_class = RedBlackTree end def setup @tree = @target_class.new end # 配列を使ってコンストラクタをテストします。 def test_constructor_with_string assert_raises(ArgumentError) { _ = RedBlackTree.new('abc') } end # 配列を使ってコンストラクタをテストします。 def test_constructor_with_array @tree = RedBlackTree.new([7, 5, 8]) assert_equal '(5 7 8)', @tree.to_s end def test_height [10, 5, 15, 3, 7, 12, 18].each { @tree.insert _1 } assert_equal 'RedBlackTree(3, 5, 7, 10, 12, 15, 18)', @tree.inspect assert_equal 3, @tree.height @tree.insert 2 assert_equal 4, @tree.height @tree.insert 1 assert_equal 4, @tree.height @tree.insert 0 assert_equal 4, @tree.height @tree.insert(-1) assert_equal 4, @tree.height @tree.insert(-2) assert_equal 5, @tree.height assert_equal 'RedBlackTree(-2, -1, 0, 1, 2, 3, 5, 7, 10, 12, 15, 18)', @tree.inspect end def test_inorder_traversal [10, 5, 15, 3, 7, 12, 18].each { @tree.insert _1 } expected_output = '3 5 7 10 12 15 18 ' @tree.insert 10 actual_output = capture_stdout { @tree.inorder_traversal { |value| print "#{value} " } } assert_equal expected_output, actual_output end # 巨大な木を作るテスト def test_build_large_tree srand(19) n = 100000 @tree = @target_class.new((0...n).to_a.shuffle) assert_equal 21, @tree.height assert_equal n, @tree.count end private # 標準出力をキャプチャして文字列として返す def capture_stdout original_stdout = $stdout $stdout = StringIO.new yield $stdout.string ensure $stdout = original_stdout end end Minitest.run if $PROGRAM_NAME == __FILE__
Splay木
[編集]Splay木（Splay Tree）は、平衡二分探索木の一種であり、特定のノードへのアクセスを行った際にそのノードを木の根に近づけることで、アクセスされたノードへのアクセス時間を短縮するデータ構造です。
Splay木は以下の特徴を持ちます:
- 動的な再構築 Splay木は平衡を保つために回転操作を行いますが、他の平衡二分探索木と異なり、特定のバランス条件を保つ必要はありません。代わりに、アクセスされたノードが常に根に来るように動的に再構築されます。
- 局所性の利用 アクセスされたノードを根に近づけることで、そのノードの近くのノードへのアクセスが高速化されます。これは、局所性を利用するため、Splay木は実際のデータにおいて効率的な振る舞いを示します。
- 単純な実装 他の平衡二分探索木と比較して、Splay木は実装が比較的単純です。回転操作が基本的な操作であり、特定のバランス条件を保つ必要がないため、実装が容易です。
Splay木は動的なデータ構造として、キャッシュやネットワークルーティング、文字列操作など、さまざまな応用で使用されています。
"Splay"という用語は、英語で「広げる」や「ひろげる」という意味を持ちます。Splay木の名称は、木の操作中に特定のノードを根に近づけるという動作を表現しています。この操作により、アクセスされたノードが木の根に近くなり、そのノードへのアクセスが高速化されるという特性があります。 Splay操作は、木の再構築を伴う動的な操作です。特定のノードがアクセスされると、そのノードを木の根に近づけるために、回転操作などの手法を使用して木の構造を変更します。この操作により、最近アクセスされたノードが高い位置に配置され、その後のアクセスが高速化されることが期待されます。
Ruby
[編集]Splay木を実装するには、二分探索木を継承して、木の操作中にノードを適切な位置まで「スプレー」する必要があります。これは、最後にアクセスされたノードを木の根に持ってくる操作です。以下に、Splay木を実装したコード例を示します。
- st.rb
# frozen_string_literal: true require_relative 'bst' class SplayTree < BinarySearchTree # 二分探索木に値を挿入し、挿入されたノードを根にスプレーします。 # # @param value [Object] 挿入する値 def insert(value) super(value) @root = splay(@root, value) self end # 二分探索木から指定されたキーのノードを検索し、検索されたノードを根にスプレーします。 # # @param key [Object] 検索するキー # @return [Boolean] ノードが見つかればtrue、見つからなければfalse def search(key) found = super(key) @root = splay(@root, key) found end private # ノードを根にスプレーする操作を行います。 # # @param node [Node, nil] 現在のノード # @param key [Object] スプレーする対象のキー # @return [Node] スプレー後の木の根 def splay(node, value) return node if node.nil? || node.value == value if node.value > value return node if node.left.nil? if node.left.value > value node.left.left = splay(node.left.left, value) node = right_rotate(node) elsif node.left.value < value node.left.right = splay(node.left.right, value) node.left = left_rotate(node.left) if node.left.right end node.left.nil? ? node : right_rotate(node) else return node if node.right.nil? if node.right.value > value node.right.left = splay(node.right.left, value) node.right = right_rotate(node.right) if node.right.left elsif node.right.value < value node.right.right = splay(node.right.right, value) node = left_rotate(node) end node.right.nil? ? node : left_rotate(node) end end # ノードを右に回転します。 # # @param node [Node] 回転の対象となるノード # @return [Node] 回転後のノード def right_rotate(x) y = x.left x.left = y.right y.right = x y end # ノードを左に回転します。 # # @param node [Node] 回転の対象となるノード # @return [Node] 回転後のノード def left_rotate(x) y = x.right x.right = y.left y.left = x y end end require 'minitest' #:Minitest::Test class SplayTreeTest < BinarySearchTreeTest def initialize(*args) super(*args) @target_class = SplayTree end def setup @tree = @target_class.new end # 配列を使ってコンストラクタをテストします。 def test_constructor_with_string assert_raises(ArgumentError) { _ = @target_class.new('abc') } end # 配列を使ってコンストラクタをテストします。 def test_constructor_with_array @tree = @target_class.new([7, 5, 8]) assert_equal '(5 7 8)', @tree.to_s end # 配列とブロックを使ってコンストラクタをテストします。 def test_constructor_with_array_with_block @list = @target_class.new([7, 5, 8]) { |i| 2 * i + 1 } assert_equal '(11 15 17)', @list.to_s assert_equal 'SplayTree(11, 15, 17)', @list.inspect end def test_height [10, 5, 15, 3, 7, 12, 18].each { @tree.insert _1 } assert_equal "#{@target_class}(3, 5, 7, 10, 12, 15, 18)", @tree.inspect assert_equal 7, @tree.height @tree.insert 2 assert_equal 6, @tree.height @tree.insert 1 assert_equal 7, @tree.height @tree.insert 0 assert_equal 8, @tree.height @tree.insert(-1) assert_equal 9, @tree.height @tree.insert(-2) assert_equal 10, @tree.height assert_equal "#{@target_class}(-2, -1, 0, 1, 2, 3, 5, 7, 10, 12, 15, 18)", @tree.inspect end def test_inorder_traversal [10, 5, 15, 3, 7, 12, 18].each { @tree.insert _1 } expected_output = '3 5 7 10 12 15 18 ' @tree.insert 10 actual_output = capture_stdout { @tree.inorder_traversal { |value| print "#{value} " } } assert_equal expected_output, actual_output end # 巨大な木を作るテスト def test_build_large_tree srand(19) n = 100000 @tree = @target_class.new((0...n).to_a.shuffle) assert_equal 45, @tree.height assert_equal n, @tree.count end ## Override def test_dfs [10, 5, 15, 3, 7, 12, 18].each { @tree.insert _1 } expected_output = '18 15 12 10 7 3 5 ' assert_equal(expected_output, capture_stdout { @tree.dfs { |value| print "#{value} " } }) assert_equal(expected_output, capture_stdout do enum = @tree.dfs enum.each do |value| print "#{value} " end end) end def test_bfs [10, 5, 15, 3, 7, 12, 18].each { @tree.insert _1 } expected_output = '18 15 12 10 7 3 5 ' assert_equal(expected_output, capture_stdout { @tree.bfs { |value| print "#{value} " } }) assert_equal(expected_output, capture_stdout do enum = @tree.bfs enum.each do |value| print "#{value} " end end) end def test_inspect @tree.insert(1) assert_equal "#{@target_class}(1)", @tree.inspect @tree.insert(3) assert_equal "#{@target_class}(1, 3)", @tree.inspect @tree.insert(2) assert_equal "#{@target_class}(1, 2, 3)", @tree.inspect @tree.insert(0) assert_equal "#{@target_class}(0, 1, 2, 3)", @tree.inspect end # insertメソッドが要素をツリーに追加することをテストします。 def test_insert_adds_element_to_end_of_list @tree.insert(1) assert_equal '(1)', @tree.to_s @tree.insert(2) assert_equal '(1 2)', @tree.to_s @tree.insert(-1) assert_equal '(-1 1 2)', @tree.to_s assert_equal false, @tree.search(0) assert_equal true, @tree.search(1) begin assert_equal 'NaN', @tree.search(0.0 / 0.0) rescue StandardError 'NaN' end @tree.delete 1 assert_equal '(-1 2)', @tree.to_s @tree.delete 0 assert_equal '(-1 2)', @tree.to_s @tree.delete(-2) assert_equal '(-1 2)', @tree.to_s @tree.delete 3 assert_equal '(-1 2)', @tree.to_s @tree.delete(-1) assert_equal '(2)', @tree.to_s @tree.delete 2 assert_equal '()', @tree.to_s end private # 標準出力をキャプチャして文字列として返す def capture_stdout original_stdout = $stdout $stdout = StringIO.new yield $stdout.string ensure $stdout = original_stdout end end Minitest.run if $PROGRAM_NAME == __FILE__
N分木
[編集]N分木（N-ary tree）は、各ノードが複数の子ノードを持つ木構造のデータ構造です。N分木では、各ノードが0個以上の子ノードを持つことができます。特に、2分木（binary tree）は、各ノードが最大2つの子ノードを持つN分木の特別なケースです。
N分木は、階層的なデータを表現するのに便利であり、グラフィカルなツリー構造やディレクトリ構造など多くの場面で使用されます。例えば、ファイルシステムのディレクトリ構造、組織図、XMLやHTMLのドキュメントツリーなどがあります。 N分木の特性は、探索や操作が容易であり、特定のノードに効率的にアクセスできることです。また、再帰的な性質を持つため、再帰的なアルゴリズムがしばしば使用されます。
Ruby
[編集]- NaryTree.rb
# frozen_string_literal: true class NaryTree include Enumerable class NaryTreeNode attr_accessor :value, :children def initialize(value) @value = value @children = [] end def add_child(child) = @children << child def each(&block) yield @value @children.each do |child| child.each(&block) end end end def initialize(root_value) @root = NaryTreeNode.new(root_value) end def each(&block) = @root.each(&block) def to_s = to_a.to_s def inspect = to_a.inspect def children = @root.children def value = @root.value def add_child(value, parent_value) parent_node = find_node(parent_value) parent_node.add_child(NaryTreeNode.new(value)) end def find_node(value, node = @root) return node if node.value == value node.children.each do |child| result = find_node(value, child) return result if result end nil end end require 'minitest' class NaryTreeTest < Minitest::Test def setup @tree = NaryTree.new(1) @tree.add_child(2, 1) @tree.add_child(3, 1) @tree.add_child(4, 2) @tree.add_child(5, 2) @tree.add_child(6, 3) end def test_node_value assert_equal 1, @tree.value end def test_node_children_count assert_equal 2, @tree.children.length assert_equal 2, @tree.children[0].children.length assert_equal 1, @tree.children[1].children.length end def test_node_add_child @tree.add_child(7, 2) assert_equal 3, @tree.children[0].children.length assert_equal 7, @tree.children[0].children.last.value end def test_find_node assert_equal 5, @tree.find_node(5)&.value assert_nil @tree.find_node(123)&.value end end Minitest.run if $PROGRAM_NAME == __FILE__
トライ木
[編集]トライ木（Trie tree）は、キーを格納するためのデータ構造であり、特に文字列の検索や辞書の実装に使用されます。各ノードは文字を表し、通常はルートから葉まで単語やキーの一部が並びます。トライ木は、キーの挿入、削除、検索などの操作を効率的に行うことができます。
Ruby
[編集]- Trie.rb
# frozen_string_literal: true class Trie include Enumerable class TrieNode attr_accessor :children, :is_end_of_word def initialize @children = {} @is_end_of_word = false end end def initialize @root = TrieNode.new end def insert(word) node = @root word.each_char do |char| node.children[char] ||= TrieNode.new node = node.children[char] end node.is_end_of_word = true end def search(word) node = search_node(word) node&.is_end_of_word end def starts_with(prefix) node = search_node(prefix) !!node end private def search_node(word) node = @root word.each_char do |char| return nil unless node.children[char] node = node.children[char] end node end end require 'minitest' class TrieTest < Minitest::Test def setup @trie = Trie.new @trie.insert('apple') @trie.insert('banana') @trie.insert('application') end def test_insert_and_search assert @trie.search('apple') assert @trie.search('banana') assert @trie.search('application') refute @trie.search('app') refute @trie.search('orange') end def test_starts_with assert @trie.starts_with('app') refute @trie.starts_with('or') end end Minitest.run if $PROGRAM_NAME == __FILE__
トピックス
[編集]ツリーに関連するトピックスには、バランス木、二分木、赤黒木、ヒープなどがあります。これらのトピックスは、ツリーを特定の目的や制約に合わせて最適化するための手法やアルゴリズムを提供します。
ユースケース
[編集]ツリーは、データベースやファイルシステム、グラフィカルユーザーインターフェース（GUI）など、さまざまな分野で幅広く利用されています。例えば、ファイルシステムではディレクトリやファイルの階層構造を表現し、データベースではインデックス構造やクエリ最適化に使用されます。
ベストプラクティス
[編集]ツリーを効果的に使用するためのベストプラクティスには、適切なツリーの選択、適切なアルゴリズムの適用、バランスの取れたツリーの維持などが含まれます。また、メモリ使用量や検索速度などのパフォーマンスにも配慮する必要があります。
イディオム
[編集]ツリーに関連するプログラミングのイディオムには、再帰的なアルゴリズムの使用や深さ優先探索、幅優先探索などがあります。これらのイディオムは、ツリーを操作する際の一般的なアプローチを示しています。