四十三庵

蔀の雑記帳

2-3 Tree(2-3木)

データ構造とアルゴリズム (新・情報 通信システム工学)

ノート

  • balanced tree(平衡木)の例として2-3木が紹介されている
  • 二分探索木はあくまで平均の計算量がO(logN)となるだけで、操作の結果によっては最悪の計算量O(N)になりうる
    • そこでbalanced treeは常に計算量がO(logN)となるように要素を挿入・削除するたびにバランスをとる
  • Node(節)とLeaf(葉)を持つ
  • Nodeはインデックスである
  • Leafが実データ
  • Nodeに対して、葉は2つまたは3つしか持てない
    • insertの際に葉が4つになったら、2つずつに分割する
    • deleteの際に葉が1つになったら、隣の2要素しかないNodeに移す
  • 本で紹介されている擬似コードだと途中が省略されていた
  • Javaの実装例は見つけた  http://wwwa.pikara.ne.jp/okojisan/t23-java/index.html