ツリー構造

計算機科学における「ツリー」とは、階層的なデータ構造を表現するための重要な概念です。ツリーは、一つ以上のノードが親子関係で接続された、木構造のデータを表します。一般的には、根ノード（ルート）から始まり、それに子ノードが接続され、さらにその子ノードにも同様の接続が行われる形態を取ります。

ツリー構造は、階層的な関係や親子関係を表現するのに非常に有用であり、データの組織化や効率的な検索、操作を可能にします。ツリーは、データベースのインデックス、ファイルシステムの階層、コンピュータネットワークの階層的な構造など、さまざまな領域で広く利用されています。

ツリーの種類

ツリーにはいくつかの種類があります。代表的なものを以下に挙げます。

1. 二分木（Binary Tree） 二分木は、各ノードが最大で2つの子ノードを持つツリーです。各ノードは左の子ノードと右の子ノードを持ち、特定の順序でデータが格納されます。
2. 二分探索木（Binary Search Tree） 二分探索木は、二分木の一種であり、各ノードが高々2つの子ノードを持つ木構造です。左部分木の全てのノードの値が、親ノードの値よりも小さく、右部分木の全てのノードの値が親ノードの値よりも大きい性質を持ちます。この性質により、データの挿入、削除、検索などの操作を効率的に行うことができます。
3. 平衡二分探索木（Self-balancing Binary Search Tree） 平衡二分探索木は、ツリー内のノードの高さの差が1より大きくならないように調整された二分木です。これにより、ツリーの高さが大幅に増加することを防ぎ、検索や挿入などの操作の効率を向上させます。代表的な平衡二分探索木には、AVL木や赤黒木などがあります。
4. N分木（N-ary Tree） N分木は、各ノードが最大でN個の子ノードを持つツリーです。二分木は特別な場合であり、Nが2であるN分木と言えます。N分木は、特にファイルシステムやデータ構造の表現など、複数の子ノードが必要な場面で使用されます。
5. トライ木（Trie Tree） トライ木は、文字列の集合を格納するために使用される特殊なデータ構造です。各ノードは通常、アルファベットの1文字を表し、ツリーの根から葉までの経路は文字列を表します。トライ木は、文字列の検索や辞書の実装などに効率的です。
6. セグメント木（Segment Tree） セグメント木は、数値の区間に関するクエリを高速に処理するためのデータ構造です。各ノードは、区間内のデータの要約を保持し、ツリーの根には全体の区間の情報が格納されます。セグメント木は、範囲クエリの処理や区間更新などの操作を効率的に行うことができます。

これらは代表的なツリーの種類ですが、他にも様々な種類が存在します。適切なツリーの種類を選択することは、特定の問題やアプリケーションにおいて効率的なデータ操作を行うために重要です。

平衡二分探索木

平衡二分探索木には、以下のようなものがあります:

1. AVL木（Adelson-Velskii and Landis' Tree） AVL木は、各ノードの高さの差が1以下であるというバランス条件を満たします。これにより、木の高さが常にO(log n)となり、挿入や削除操作においても効率的な検索が可能となります。ノードの挿入や削除後に、回転操作を行ってバランスを修復します。
2. 赤黒木（Red-black_tree） 赤黒木は、各ノードに赤または黒の色を付け、一定の条件を満たすことでバランスを保つ木構造です。条件は以下の通りです：
   1. ルートは黒である。
   2. 赤のノードの子ノードは全て黒である。
   3. 各ノードから葉ノードまでの黒のノード数は同じである（黒の高さが一定）。

   これにより、挿入、削除、検索操作を効率的に行うことができます。

3. Splay木 Splay木は、最近アクセスされたノードをルートに移動させることによって操作を効率化する平衡二分探索木です。挿入、削除、検索の操作において、最近アクセスされたノードがより高い位置に移動し、アクセスされたノードがより頻繁にアクセスされるようになります。
4. Treap Treapは、二分探索木とランダムヒープの両方の性質を持つデータ構造です。各ノードにはキーと優先度があり、キーは二分探索木の性質を満たし、優先度はヒープの性質を満たします。ランダムな優先度に基づいて平衡が保たれるため、Treapは単純で効率的な平衡二分探索木として知られています。
5. アバランチ木（AVL-Trie） アバランチ木は、AVL木とトライ（Trie）の特性を組み合わせたデータ構造です。キーのビットごとのプレフィックスを使ってノードを構築し、各ノードは平衡されたAVL木を保持します。この組み合わせにより、高速な挿入、削除、検索が可能となります。
6. AA木 AA木は、アドレス総和（Address-Adjusted）木として知られており、赤黒木のような平衡二分探索木です。しかし、AA木では赤黒木とは異なるバランス条件が使用されています。AA木は、比較的シンプルな操作に基づいて平衡が保たれます。

これらの平衡二分探索木は、それぞれ異なるアプローチを使用して平衡を実現し、異なる利点とトレードオフを持っています。どのデータ構造を選択するかは、特定のアプリケーションの要件や性能目標に依存します。

ツリーの操作

ツリーには、さまざまな操作があります。代表的なものを以下に説明します。

1. 挿入（Insertion）: ツリーに新しいノードを挿入する操作です。挿入されたノードは、適切な位置に配置され、ツリーの構造が保持されます。例えば、二分探索木では、新しいノードは適切な位置に挿入され、ツリーが二分探索木の性質を維持します。
2. 削除（Deletion）: ツリーから特定のノードを削除する操作です。削除されたノードの子ノードや親ノードの接続が適切に調整され、ツリーの構造が保持されます。削除操作は、ノードの種類やツリーの種類に応じてさまざまな場合があります。
3. 検索（Search）: ツリー内で特定の値を持つノードを見つける操作です。一般的な検索操作は、再帰的な深さ優先探索や幅優先探索などのアルゴリズムを使用して行われます。特に、二分探索木では、効率的な二分探索アルゴリズムが使用されます。
4. 走査（Traversal）: ツリー内のすべてのノードを訪問する操作です。一般的な走査方法には、前順走査（Preorder traversal）、中順走査（Inorder traversal）、後順走査（Postorder traversal）などがあります。これらの走査方法は、ツリー内のノードを特定の順序で訪問するために使用されます。
5. 更新（Update）: ツリー内の特定のノードの値を変更する操作です。更新操作は、ツリーが特定の属性や状態を持つ場合に有用です。更新操作は、検索操作と組み合わせて使用されることがあります。

これらはツリーの基本的な操作ですが、特定のアプリケーションや問題に応じて、さらに多くの操作が必要になる場合があります。ツリーの操作は、データの効率的な管理や操作を可能にし、多くのアルゴリズムやデータ構造の基礎となります。

反復処理

ツリーにおける反復処理は、ツリー内のすべての要素を訪問する操作です。主な方法には、深さ優先探索（Depth-First Search, DFS）と幅優先探索（Breadth-First Search, BFS）の2つがあります。それぞれの方法について説明します。

1. 深さ優先探索（Depth-First Search, DFS）:

   深さ優先探索は、ツリーの最大深さまで進んでから次の子ノードに移動する方法です。典型的には再帰的な手法で実装されますが、明示的なスタック（Stack）を使用することもあります。深さ優先探索は、更に以下の３種類に分類されます。

   1. 先行順序探索（preorder_traversal）:

      ルート、左部分木、右部分木の順に探索する。

   2. 中間順序探索（inorder_traversal）:

      左部分木、ルート、右部分木の順に探索する。

   3. 後行順序探索（postorder_traversal）:

      左部分木、右部分木、ルートの順に探索する。

2. 幅優先探索（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での反復処理の実装は、イテレータパターンで実現するのが一般的です。

ツリー構造の反復にイテレータパターンを適用する際には、各ノードを訪れるための方法と、必要に応じてノードを追加する方法を定義する必要があります。以下は、イテレータパターンを使用してツリー構造を反復処理する基本的な手順です。

1. イテレータインターフェースの定義: ツリーの要素を反復するためのインターフェースを定義します。このインターフェースには、次のノードを返すメソッドや、反復が終了したかどうかを示すメソッドが含まれる場合があります。
2. ツリーのノードを表すクラスの作成: ツリーのノードを表すクラスを作成します。このクラスには、ノードの値や子ノードへの参照が含まれます。
3. イテレータの実装: ツリーの反復を実装する具象イテレータクラスを作成します。このクラスは、定義したイテレータインターフェースを実装し、ツリーの要素を反復します。
4. 反復処理の実行: クライアントコードで、イテレータを使用してツリーを反復処理します。通常は、for ループや他の反復構造を使用して、ツリー内の要素を順番に処理します。

Goでは、イテレータパターンをより一般化・抽象化する取り組みが2024年２月時点で行われており、標準ライブラリやフレームワークとして実装されるかもしれません。

Java

Javaでは、Iterable インターフェースと Iterator インターフェースが反復処理を一般化するために使用されます。Iterable インターフェースは、反復子を提供する iterator() メソッドを定義し、Iterator インターフェースは、hasNext() メソッドと next() メソッドを定義しています。

C#

C#では、IEnumerable インターフェースと IEnumerator インターフェースが反復処理を一般化するために使用されます。IEnumerable インターフェースは、GetEnumerator() メソッドを定義し、IEnumerator インターフェースは、MoveNext() メソッドと Current プロパティを定義しています。

C++

C++でも反復処理を一般化するための機能がいくつかあります。

1. 範囲ベースのforループ: C++11以降、範囲ベースのforループが導入され、これにより範囲内のすべての要素を簡潔に反復できるようになりました。
2. STLイテレータ: C++の標準テンプレートライブラリ（STL）では、反復処理をサポートするためにイテレータが使用されます。STLの多くのコンテナやアルゴリズムは、イテレータを介して反復処理を行います。
3. イテレータパターンの実装: ユーザー定義のクラスやデータ構造に対して、イテレータパターンを実装することも可能です。これにより、クラスの内部構造を隠蔽しつつ、外部から反復処理を行うことができます。

これらの方法を使用して、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. 各ノードには、1つのキーがあります。
2. 左部分木に含まれるすべてのノードのキーは、そのノードのキーよりも小さくなります。
3. 右部分木に含まれるすべてのノードのキーは、そのノードのキーよりも大きくなります。
4. 同じキーを持つノードは存在しません。

この性質により、二分探索木は効率的な探索、挿入、削除が可能になります。探索を行う場合、目的のキーと比較しながら、木の構造を辿っていくことで、目的のキーを持つノードを見つけることができます。挿入や削除を行う場合も、二分探索木の性質を保ちつつ操作を行うことで、木のバランスを保ちながら効率的な操作を実現します。 しかし、二分探索木の性能は挿入や削除の際に木のバランスが崩れる可能性があるため、バランスを保つアルゴリズム（例：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）は、バランス二分木の一種であり、各ノードが追加されたときに特定の条件を満たすように再構築されるデータ構造です。

赤黒木は、以下の性質を持つ木構造です：

1. 各ノードは「赤」または「黒」の色を持ちます。
2. 根（root）ノードは必ず黒である。
3. すべての葉（NILノードまたはnullノード）は黒である。
4. 赤のノードの子はすべて黒である。
5. あるノードからその子孫へのあらゆる単純なパスには、黒いノードの数が同じでなければならない（これは「黒の高さが一定」とも呼ばれます）。

これらの性質により、赤黒木は追加、削除、検索などの操作において、平均的に効率的な性能を提供します。赤黒木は、データベースの索引や標準ライブラリのセットなど、さまざまなアプリケーションで広く使用されています。

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木は以下の特徴を持ちます:

1. 動的な再構築 Splay木は平衡を保つために回転操作を行いますが、他の平衡二分探索木と異なり、特定のバランス条件を保つ必要はありません。代わりに、アクセスされたノードが常に根に来るように動的に再構築されます。
2. 局所性の利用 アクセスされたノードを根に近づけることで、そのノードの近くのノードへのアクセスが高速化されます。これは、局所性を利用するため、Splay木は実際のデータにおいて効率的な振る舞いを示します。
3. 単純な実装 他の平衡二分探索木と比較して、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）など、さまざまな分野で幅広く利用されています。例えば、ファイルシステムではディレクトリやファイルの階層構造を表現し、データベースではインデックス構造やクエリ最適化に使用されます。

ベストプラクティス

ツリーを効果的に使用するためのベストプラクティスには、適切なツリーの選択、適切なアルゴリズムの適用、バランスの取れたツリーの維持などが含まれます。また、メモリ使用量や検索速度などのパフォーマンスにも配慮する必要があります。

イディオム

ツリーに関連するプログラミングのイディオムには、再帰的なアルゴリズムの使用や深さ優先探索、幅優先探索などがあります。これらのイディオムは、ツリーを操作する際の一般的なアプローチを示しています。