【C#データ構造】2分探索木とは?ヒープの違いも解説
はじめに
データ構造の一つである2分探索木 (Binary Search Tree, BST) は、多くのアルゴリズムやアプリケーションで重要な役割を果たします。本記事では、2分探索木の基本概念と、それに関連するヒープ(Heap)との違いについて解説します。また、C#での2分探索木の実装例も紹介します。
ヒープについては以下の記事で実装、説明を行っています。
ヒープ (Heap) とは?
ヒープは、優先度付きキューを効率的に実現するためのデータ構造です。ヒープには以下の特性があります。
- 各ノードの値は、その子ノードの値よりも大きい(最大ヒープの場合)または小さい(最小ヒープの場合)。
- 完全二分木である。
ヒープは、特に最小値や最大値を迅速に取り出す操作に適しています。
最小ヒープの例
1
/ \
3 6
/ \ / \
5 9 8 10
この木では、親ノードの値は常に子ノードの値よりも小さいです。
2分探索木とは?
2分探索木は、以下の特性を持つ二分木です。
- 各ノードには値があり、左部分木のすべてのノードの値は、そのノードの値よりも小さい。
- 右部分木のすべてのノードの値は、そのノードの値よりも大きい。
これにより、効率的な検索、挿入、削除操作が可能になります。
2分探索木の例
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
この木では、各ノードの左側の子ノードは常に小さく、右側の子ノードは常に大きくなっています。
2分探索木の操作
挿入
新しいノードを挿入する際、以下の手順を取ります。
- 根ノードからスタートし、新しいノードの値を比較します。
- 新しいノードの値が小さい場合は左部分木、大きい場合は右部分木に進みます。
- 空の位置に到達したら、そこに新しいノードを挿入します。
具体例:
例えば、要素5
を以下の2分探索木に挿入する場合を考えます。
3
/ \
1 6
/ \
4 7
要素5
の挿入:
まず5 > 3
であるため、最初は右に進んでいきます。次に5 < 6
であるため、左側に進みます。最後に5 > 4
であるため,4の右子ノードとしての位置が適切となります。
3
/ \
1 6
/ \
4 7
\
5
削除
- 削除対象の要素を探します。
- 削除対象の要素の子ノードが一つの場合、削除する位置に子ノードをあてはめます。子ノードが二つの場合、右部分木のうち最小のノードをあてはめます。そして、そのノードは右部分木に存在しなくなる(移動する)ので、そのあてはめたノードを削除します。
具体例:
例えば、要素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分探索木とヒープの主な違いは次の通りです。
-
構造の特性:
- 2分探索木: 各ノードの左部分木は小さい値、右部分木は大きい値。
- ヒープ: 各ノードは子ノードよりも大きい(最大ヒープ)または小さい(最小ヒープ)。
-
用途:
- 2分探索木: 動的なデータセットでの効率的な検索、挿入、削除。
- ヒープ: 優先度付きキューでの最小値・最大値の迅速な取り出し。指定の要素を取り出すことは苦手。
まとめ
2分探索木は、多くのアルゴリズムで効率的なデータ管理を可能にする基本的なデータ構造です。一方、ヒープは特に優先度付きキューでの利用に適しています。これらのデータ構造の理解と使い分けは、効率的なプログラミングにおいて重要です。C#での実装例を参考に、ぜひ自分でも試してみてください。
参考書籍
データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)
Discussion