2-3木
2-3
定義
-
子供 を2つもつノード。aより小 さいノードが p、大 きいノードが qになる。 -
子供 を3つもつノード。aより小 さいノードが p、aより大 きく bより小 さいノードが q、bより大 きいノードが r になる。
2-3
- すべての
内部 ノードは 2か3の子供 を持 つ（1つ、または4つ以上 の子供 を持 つ親 は存在 しない） 全 ての葉 は根 からの距離 が等 しい（平衡 木 ）内部 ノードは1つか2つのキーを持 つ。- 1つのキーを
持 つノードは2分 探索 木 と同様 に、そのキーより小 さい子供 を左 に大 きい子供 を右 に格納 している。 - 2つのキー（a, bで a < b とする）を
持 つノードは、a より小 さい子供 を左 に、a より大 きく b より小 さい子供 を真 ん中 に、b より大 きい子供 を右 に配置 する。
という
操作
検索
2-3
根 を対象 ノードとして検索 を開始 する検索 対象 のノードが葉 であり、検索 値 と一致 するなら検索 成功 として終了 、検索 値 と一致 しないなら木 に登録 されていないものとして終了 する検索 対象 の内部 ノードのキーが一 つの場合 、検索 値 がキーより小 さいなら左 へ大 きいなら右 のノードを次 の対象 とする。検索 対象 の内部 ノードのキーが二 つの場合 、検索 値 2つのキーどちらよりも小 さいなら左 へ、片方 のキーより大 きくもう片方 のキーより小 さいなら真 ん中 へ、どちらよりも大 きい場合 は右 のノードを次 の対象 とする- 2.
以下 を繰 り返 す。
BB
挿入
検索 と同様 の操作 を行 って葉 の一 つ上 の親 を検索 する。- その
親 に挿入 値 を挿入 する。 - もし、
挿入 値 を挿入 した場合 に、子供 が3つになった場合 は、親 のキーを変更 する。キーの値 は真 ん中 の子供 の値 と、一番 右 の子供 の値 になる。 - もし、
挿入 値 を挿入 して子供 が 4つになった場合 は、親 のノードを、子供 を二 つもつノード二 つに分割 する。分割 した親 ノードのキーおよび分割 の仕方 は挿入 値 とノードの状態 によって異 なる（右 図 参照 ） - 2
以降 の処理 を親 の分割 が行 われなくなるまで、繰 り返 す。
BB
削除
削除 する要素 を持 つ親 が3つの子供 を持 つ場合 は、その要素 を削除 して、親 のキーを更新 する。削除 値 が兄弟 の中 でもっとも大 きい場合 は、親 のキーから削除 値 と同 じキーを削除 する。削除 値 が兄弟 の中 で真 ん中 の場合 、親 のキーから自分 の値 を削除 して右 の兄弟 を真 ん中 に移動 する。一番 左 の場合 は真 ん中 の兄弟 のキーを削除 して真 ん中 を左 へ右 を真 ん中 へ移動 する。削除 する要素 を持 つ親 が2つの子供 を持 つ場合 、親 の兄弟 を検索 する。検索 した親 の兄弟 が2つの子供 を持 つ場合 は親 とその兄弟 を、3つの子供 を持 つ1つの親 に併合 する。- 3.の
操作 で併合 された場合 、親 のそのまた親 の子供 の数 が 2.か 3.であることを確認 し、1つである場合 は、2以降 の処理 を繰 り返 す。
BB
参考 文献
- A.エイホ・J.ホップクロフト・J.ウルマン
著 、『アルゴリズムの設計 と解析 I』、野崎 昭弘 ・野下 浩平 訳 、サイエンス社 、1977年 、ISBN 4-7819-0279-0 - N.ヴィルト
著 、『アルゴリズムとデータ構造 』、浦 昭二 ・国府 方 久史 訳 、近代 科学 社 、1990年 、ISBN 4-7649-0162-5
関連 項目
 | この |