🦔

【C#データ構造】2-3木/B木とは？

2024/07/19に公開

 はじめに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版] (新・情報/通信システム工学)

https://amzn.to/3YtOnpz

はじめに

2-3木(B木)とは？

2-3木(B木)の例

2-3木の操作

挿入

削除

C#による実装

2分探索木との違い

まとめ

参考書籍

Discussion