🦔
【C＃によるコード付】2-3木/B木とは？
はじめに
2-3木（B木）は、バランスの取れた木構造であり、検索や挿入、削除の操作が効率的に行えるデータ構造です。データベースでよく利用されるデータ構造です。
2-3木(B木)とは？
2-3木は、全ての内部ノードが2つまたは3つの子ノードを持つ自己平衡木です。具体的には以下の特性を持ちます。
- すべての要素は葉に格納されます（末端にある）。
- 途中ノードは必ず2つまたは3つの子ノードを持ちます。索引情報として2番目の子の子孫と3番目の子の子孫の最小値を持ちます。
これにより、2-3木は挿入、削除、検索の操作が最悪でも O(log n) の時間複雑度で実行可能です。
2-3木(B木)の例
(79,x)
/ \
(61,63) (86,x)
/ | \ / \
35 61 63 79 86
（）内の左の数字が2番目の子孫の最小値を表しており、右の数字が3番目の子孫の最小値を表しています。3番目の子孫が存在しない場合にはxと記述しています。
2-3木の操作
挿入
新しいノードを挿入する際、以下の手順を取ります。
-
適切な位置に新しいキーを挿入します。
-
ノードがオーバーフローした場合は分割します。（これには以下の2パターンがあります。）
- もともとノードが2つの場合：3つの子になるだけなので問題ない。
- もともとノードが3つの場合：4つの子になるので新しい親を作って2つの子をその親へ移す。これにより、親ノードが4つの子になる可能性があるので根まで繰返し行う。
-
必要に応じて木の高さを調整します。
削除
キーを削除する際も同様に、以下の手順を取ります。
-
キーを削除します。
-
ノードがアンダーフローした場合は再結合や借用を行います。（これには以下の2パターンがあります。）
- もともとノードが2つの場合：1つの子になるので隣の親に子が3つあるならばそこから子を一つ移してくる。そうでないならば、1つしかない子をどちらかの親へ移し、親を削除する。これにより、親ノードが1つの子になる可能性があるので根まで繰返し行う。
- もともとノードが3つの場合：2つの子になるだけなので問題ない。
-
必要に応じて木の高さを調整します。
C#による実装
以下に、2-3木の基本的な実装例を示します。挿入コードのみ実装しました。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices.WindowsRuntime;
using System.Threading;
/// <summary>
/// 2 - 3木(B木)を実装します．
/// 2 - 3木(B木)では一般にノードクラスを定義します．
/// </summary>
/// <typeparam name="T"></typeparam>
public class TwoThreeNode<T> where T : IComparable<T>
{
public T LeafData;//葉であるならばデータを持つ
public T MinData;//1番目の子の子孫の最小値（索引情報ではない）
public T SecondMinKey;//2番目の子の子孫の最小値
public T ThirdMinKey;//3番目の子の子孫の最小値
public List<TwoThreeNode<T>> Children = new List<TwoThreeNode<T>>();
public bool IsLeaf => Children.Count == 0;//葉かどうか
}
/// <summary>
/// 2 - 3木(B木)の実装クラスです．
/// </summary>
/// <typeparam name="T"></typeparam>
public class TwoThreeTree<T> where T : IComparable<T>
{
public TwoThreeNode<T> Root = null;
/// <summary>
/// 要素の挿入を行います
/// </summary>
/// <param name="_key"></param>
public void Insert(T _key)
{
if (Root == null)
{
Root = new TwoThreeNode<T> { LeafData = _key };
}
else
{
TwoThreeNode<T> _child = InsertRec(Root, _key);
//親ノードを追加しなければならない
if (_child != null)
{
TwoThreeNode<T> _newRoot = new TwoThreeNode<T>();
_newRoot.Children.Add(Root);
_newRoot.Children.Add(_child);
SetParentKey(_newRoot);
Root = _newRoot;
}
}
}
/// <summary>
/// 挿入のために再帰的に行います．
/// 戻り値bool(_grow)は木の高さが変更された場合にtrueになります．
/// </summary>
/// <param name="_node"></param>
/// <param name="_key"></param>
/// <returns></returns>
private TwoThreeNode<T> InsertRec(TwoThreeNode<T> _node, T _key)
{
//ノードが葉であるならば
if (_node.IsLeaf)
{
//これも葉である．新しいノードを作って返す．
return new TwoThreeNode<T> { LeafData = _key };
}
//_nodeの子で_dataが属する部分木を求める．
TwoThreeNode<T> _child = FindChild(_node, _key);
//_childへ_keyを挿入する．
TwoThreeNode<T> _newChild = InsertRec(_child, _key);
if (_newChild == null) return null;//兄弟は増えなかった
//_newChildを追加し，並び替えを行い，索引情報(Key)をセットする．
_node.Children.Add(_newChild);
SetParentKey(_node);
//_nodeの子が4つになったならば
if (_node.Children.Count == 4)
{
return SplitNode(_node);
}
else
{
//既に要素は追加したので，新しい親ノードに追加する必要はない
return null;
}
}
/// <summary>
/// 親の索引情報(Key)をセットする．
/// 並び替えを行うことで実現する．
/// </summary>
/// <param name="_parent"></param>
private void SetParentKey(TwoThreeNode<T> _parent)
{
List<TwoThreeNode<T>> _children = _parent.Children;
//子が葉であるならば葉の値で比較する
if (_children[0].IsLeaf)
{
_children.Sort((x, y) => x.LeafData.CompareTo(y.LeafData));
_parent.MinData = _children[0].LeafData;
_parent.SecondMinKey = _children[1].LeafData;
_parent.ThirdMinKey = _children.Count == 3 ? _children[2].LeafData : default;
}
else
{
_parent.MinData = _children[0].MinData;
_parent.SecondMinKey = _children[1].MinData;
_parent.ThirdMinKey = _children.Count == 3 ? _children[2].MinData : default;
}
}
/// <summary>
/// 子が4つになった場合に分割を行う．
/// </summary>
/// <param name="_node"></param>
/// <returns></returns>
private TwoThreeNode<T> SplitNode(TwoThreeNode<T> _node)
{
TwoThreeNode<T> _rightChild = new TwoThreeNode<T>();
//右側2つの要素を追加して，並び替えを行い，索引情報(Key)をセットする．
_rightChild.Children.AddRange(_node.Children.GetRange(2, 2));
SetParentKey(_rightChild);
//左側2つの要素を削除して，並び替えを行い，索引情報(Key)をセットする．
_node.Children.RemoveRange(2, 2);
SetParentKey(_node);
return _rightChild;
}
/// <summary>
/// _keyが属するchildを求める
/// </summary>
/// <param name="_parent"></param>
/// <param name="_key"></param>
/// <returns></returns>
private TwoThreeNode<T> FindChild(TwoThreeNode<T> _parent, T _key)
{
//挿入されるデータの2番目の子の子孫の最小値より小さいならば，
if (_key.CompareTo(_parent.SecondMinKey) < 0)
{
//1番目の子孫に_keyは属する
return _parent.Children[0];
}
//子供が二つしかいないならば，または
//挿入されるデータの3番目の子の子孫の最小値より小さいならば，
else if (_parent.Children.Count == 2 || _key.CompareTo(_parent.ThirdMinKey) < 0)
{
//2番目の子孫に_keyは属する
return _parent.Children[1];
}
else
{
//3番目の子孫に_keyは属する
return _parent.Children[2];
}
}
}
public class Example
{
public static void Main()
{
TwoThreeTree<int> tree = new TwoThreeTree<int>();
tree.Insert(61);
tree.Insert(79);
tree.Insert(28);
tree.Insert(35);
tree.Insert(86);
tree.Insert(63);
tree.Insert(100);
tree.Insert(105);
}
}
2分探索木との違い
2-3木と2分探索木の主な違いは次の通りです。
-
構造の特性:
- 2分探索木: 各ノードの左部分木は小さい値、右部分木は大きい値。
- 2-3木: 各ノードは1つまたは2つのキーを持ち、0から2つの子ノードを持つ。
-
性能:
- 2分探索木: 平均的には効率的ですが、最悪の場合 O(n) の操作時間がかかる可能性があります。
- 2-3木: 最悪の場合でも O(log n) の操作時間を保証します。
まとめ
2-3木は、自己平衡性を保つことで、効率的な検索、挿入、削除操作を実現するデータ構造です。一方、標準の2分探索木は、特に平衡が保たれない場合に性能が低下する可能性があります。これらのデータ構造の理解と使い分けは、効率的なプログラミングにおいて重要です。C#での実装例を参考に、ぜひ自分でも試してみてください。
参考書籍
データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)
Discussion