最大HBLTから任意のノードを削除する方法と計算量の解説

最大HBLTにおける任意のノード削除とは

最大HBLT（Height-Biased Leftist Tree：高さ偏り左木）や最小HBLTから任意のノードを削除することは、優先度付きキュー（プライオリティキュー）やHBLTにおける標準的な操作ではありません。しかし、特定の要件によっては、指定したノードKをHBLTから取り除く必要が生じる場合があります。その際は、以下のルールに従って削除を行います。

削除の基本ルール

• サブツリーの分離とmeld（併合）による置換： ノードKを根とする部分木を木全体から切り離し、その位置にノードKの左右の部分木をmeldした結果を配置します。

• s値の更新と部分木の交換： ノードKから根（ルート）に至る経路上のs値を更新し、HBLTの性質を維持できるよう、必要に応じて経路上の部分木を交換します。

s値更新の仕組み

Kから根へ向かってs値を更新するためには、各ノードが親ポインタを持っている必要があります。この更新操作は、途中でs値が変化しないノードに到達した時点で終了できます。

更新されるs値は必ず昇順の列を形成します。これは、各ノードのs値が直前のノードより必ず1大きくなければならないというHBLTの性質によるものです。s値の最大値はO(log n)であり、すべてのs値が正であることから、更新パス上で処理されるノード数は最大でもO(log n)個にとどまります。さらに、各ノードのs値更新には定数時間O(1)しかかかりません。

計算量のまとめ

以上の理由から、HBLTから任意のノードを削除する操作全体の計算量はO(log n)となります。これは、更新が必要なノード数が対数オーダーに抑えられるためであり、HBLTが効率的なデータ構造であることを示す重要な特性の一つです。