Zenn
🕌

【C＃によるコード付】2分探索木とは？ヒープの違いも解説

2024/06/28に公開
C#
データ構造
二分探索
コーディング
tech

はじめに

データ構造の一つである2分探索木 (Binary Search Tree, BST) は、多くのアルゴリズムやアプリケーションで重要な役割を果たします。本記事では、2分探索木の基本概念と、それに関連するヒープ（Heap）との違いについて解説します。また、C#での2分探索木の実装例も紹介します。

ヒープについては以下の記事で実装、説明を行っています。
https://zenn.dev/student_blog/articles/10f9a750afea2a

ヒープ (Heap) とは？

ヒープは、優先度付きキューを効率的に実現するためのデータ構造です。ヒープには以下の特性があります。

  1. 各ノードの値は、その子ノードの値よりも大きい（最大ヒープの場合）または小さい（最小ヒープの場合）。
  2. 完全二分木である。

ヒープは、特に最小値や最大値を迅速に取り出す操作に適しています。

最小ヒープの例

       1
      / \
     3   6
    / \ / \
   5  9 8 10

この木では、親ノードの値は常に子ノードの値よりも小さいです。

2分探索木とは？

2分探索木は、以下の特性を持つ二分木です。

  1. 各ノードには値があり、左部分木のすべてのノードの値は、そのノードの値よりも小さい。
  2. 右部分木のすべてのノードの値は、そのノードの値よりも大きい。

これにより、効率的な検索、挿入、削除操作が可能になります。

2分探索木の例

        8
       / \
      3   10
     / \    \
    1   6    14
       / \   /
      4   7 13

この木では、各ノードの左側の子ノードは常に小さく、右側の子ノードは常に大きくなっています。

2分探索木の操作

挿入

新しいノードを挿入する際、以下の手順を取ります。

  1. 根ノードからスタートし、新しいノードの値を比較します。
  2. 新しいノードの値が小さい場合は左部分木、大きい場合は右部分木に進みます。
  3. 空の位置に到達したら、そこに新しいノードを挿入します。

具体例:

例えば、要素5を以下の2分探索木に挿入する場合を考えます。

        3
       / \
      1   6
         / \
        4   7

要素5の挿入:
まず5 > 3であるため、最初は右に進んでいきます。次に5 < 6であるため、左側に進みます。最後に5 > 4であるため，4の右子ノードとしての位置が適切となります。

        3
       / \
      1   6
         / \
        4   7
         \
          5

削除

  1. 削除対象の要素を探します。
  2. 削除対象の要素の子ノードが一つの場合、削除する位置に子ノードをあてはめます。子ノードが二つの場合、右部分木のうち最小のノードをあてはめます。そして、そのノードは右部分木に存在しなくなる（移動する）ので、そのあてはめたノードを削除します。

具体例:

例えば、要素6を以下の2分探索木から削除する場合を考えます。

        3
       / \
      1   6
         / \
        4   7
         \
          5

要素6の削除:
まず6 > 3であるため、根ノードから見て右側を探します。すると6が見つかりました。右子ノードの最小値（または左子ノードの最大値）と置き換えられ、その後削除されます。

        3
       / \
      1   7
         /
        5
       /
      4

C#による実装

以下に、2分探索木の基本的な実装例を示します。

using System;

/// <summary>
/// 二分探索木を実装します．
/// ヒープではその構造を使用して配列で扱えます．
/// 二分探索木では一般にノードクラスを定義します．
/// </summary>
/// <typeparam name="T"></typeparam>
public class Node<T> where T : IComparable<T>
{
  public T Data;
  public Node<T> Left;
  public Node<T> Right;

  public Node(T _data)
  {
    Data = _data;
    Left = null;
    Right = null;
  }
}

/// <summary>
/// 探索木の実装クラスです．
/// </summary>
/// <typeparam name="T"></typeparam>
public class BinarySearchTree<T> where T : IComparable<T>
{
  public Node<T> Root;

  public BinarySearchTree()
  {
    Root = null;
  }

  /// <summary>
  /// 要素の挿入を行います
  /// </summary>
  /// <param name="_data"></param>
  public void Insert(T _data)
  {
    Root = InsertRec(Root, _data);
  }

  /// <summary>
  /// 挿入のために再帰的に行います．
  /// </summary>
  /// <param name="_node"></param>
  /// <param name="_data"></param>
  /// <returns></returns>
  private Node<T> InsertRec(Node<T> _node, T _data)
  {
    //nullならばその場所に要素を挿入する．
    //そのために，return _nodeを行う．
    if (_node == null)
    {
      _node = new Node<T>(_data);
      return _node;
    }

    //挿入ノードの値が比較ノードの値よりも小さいならば，Leftを探索
    if (_data.CompareTo(_node.Data) < 0)
    {
      _node.Left = InsertRec(_node.Left, _data);
    }
    //大きいならば，Rightを探索
    else
    {
      _node.Right = InsertRec(_node.Right, _data);
    }
    return _node;
  }

  /// <summary>
  /// 要素の削除を行う．
  /// </summary>
  /// <param name="_data"></param>
  public void Delete(T _data)
  {
    Root = DeleteRec(Root, _data);
  }

  /// <summary>
  /// 要素の削除を行うために再帰的に行う．
  /// まずは削除ノードを発見し，二つの子ノードを持っているならば
  /// 右木部分の最小値を削除ノードにあてはめる．
  /// </summary>
  /// <param name="_node"></param>
  /// <param name="_data"></param>
  /// <returns></returns>
  private Node<T> DeleteRec(Node<T> _node, T _data)
  {
    if (_node == null) { return null; }

    //削除ノードの値は比較ノードの値よりも小さいので，左木部分に存在する．
    if (_data.CompareTo(_node.Data) < 0)
    {
      _node.Left = DeleteRec(_node.Left, _data);
    }
    //大きいので右木部分に存在する．
    else if (_data.CompareTo(_node.Data) > 0)
    {
      _node.Right = DeleteRec(_node.Right, _data);
    }
    //同じならば削除ノードを消してその部分に子ノードを代入する．
    else
    {
      //子ノードが二つならば右木部分の最小値を削除ノードにあてはめる．
      //あてはめたノードも削除したと考えられるので，削除を行う．
      if (_node.Left != null && _node.Right != null)
      {
        Node<T> _minNode = GetMinNode(_node.Right);
        _node.Data = _minNode.Data;
        _minNode.Right = DeleteRec(_node.Right, _minNode.Data);
      }
      //子ノードが一つならば子ノードを親ノードにあてはめるのみ．
      else if (_node.Left != null)
      {
        return _node.Left;
      }
      else
      {
        return _node.Right;
      }
    }
    return _node;
  }

  /// <summary>
  /// 右子ノードのうち最小のものをとってくる．
  /// 最小のノード＝左子ノードがないノード
  /// </summary>
  /// <param name="_node"></param>
  private Node<T> GetMinNode(Node<T> _node)
  {
    if (_node.Left != null)
    {
      return GetMinNode(_node.Left);
    }
    return _node;
  }
}

public class Example
{
  public static void Main()
  {
    BinarySearchTree<int> _tree = new BinarySearchTree<int>();
    _tree.Insert(34);
    _tree.Insert(51);
    _tree.Insert(72);
    _tree.Insert(17);
    _tree.Insert(66);
    _tree.Insert(35);
    _tree.Insert(99);
    _tree.Insert(1);
    _tree.Delete(51);
    _tree.Delete(34);
    _tree.Delete(1);
  }
}

ヒープとの違い

2分探索木とヒープの主な違いは次の通りです。

  1. 構造の特性:

    • 2分探索木: 各ノードの左部分木は小さい値、右部分木は大きい値。
    • ヒープ: 各ノードは子ノードよりも大きい（最大ヒープ）または小さい（最小ヒープ）。

  2. 用途:

    • 2分探索木: 動的なデータセットでの効率的な検索、挿入、削除。
    • ヒープ: 優先度付きキューでの最小値・最大値の迅速な取り出し。指定の要素を取り出すことは苦手。

まとめ

2分探索木は、多くのアルゴリズムで効率的なデータ管理を可能にする基本的なデータ構造です。一方、ヒープは特に優先度付きキューでの利用に適しています。これらのデータ構造の理解と使い分けは、効率的なプログラミングにおいて重要です。C#での実装例を参考に、ぜひ自分でも試してみてください。

参考書籍

データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)
https://amzn.to/4bniLp4

Discussion