Zip木は、ランダム二分探索木の変種としてRobert Tarjan、 Caleb Levy、 Stephen Timmelによって導入されました。 [1] Zip 木は最大木に似ていますが、ランクが幾何分布によって生成され、木の回転ではなく unzip と zip による挿入と削除中に最大ヒープ特性を維持する点が異なります。木のノードには、比較可能な個別のキーと数値ランクが含まれます。木はランクに関して最大ヒープ順序付けされ、同点の場合はより小さいキーを優先します。木のノードは、異なるキーを含まなければなりませんが、ランクの重複を許容します。小さいキーを優先するランク タイブレーカーにより、木ではより小さいノードを優先するバイアスが生じます。わずかに修正された Zip 木の変種である Zip-Zip 木は、第 2 ランクを持つ別のタイブレーカーを導入することでこのバイアスに対処しています。[2]
オペレーション
Zipツリーは二分探索木の演算をサポートします。実装上の主な違いは、Zipツリーのヒープ順序を維持するために、パスの解凍と圧縮を通じた挿入と削除の実装にあります。
ノードuの挿入または削除にかかる時間は、uの検索時間と解凍または圧縮にかかる時間の合計に等しい。解凍または圧縮にかかる時間は、解凍/圧縮されるパス上のノード数に1を加えた値に比例する。圧縮木における各ノードの期待される深さは最大1.5 log nであるため、挿入、削除、および検索操作の期待実行時間はすべてO( log n)となる。[1]
挿入
ノードx をzipツリーに挿入する際、まず幾何分布から成功確率1/2の新しいランクを生成します。x.keyをノードxのキー、x.rank をノードxのランクとします。
次に、ツリー内のxの検索パスをたどり、 u.rank <= x.rankかつu.key < x.keyとなるノードuを見つけます。 xの検索パスに沿って進み、通過するすべてのノードv を「解凍」し、v.key < x.keyの場合はパスPに、v.key > x.keyの場合はパスQに配置します。キーは一意である必要があるため、いずれかの時点でv.key = x.key になった時点で検索は停止し、新しいノードは追加されません。
xの検索が完了すると、ノード u の代わりにxが挿入されます。パスPのトップノードはxの左の子となり、パス Qのトップノードは右の子となります。uとu.parent間の親子ポインタはxに応じて更新され、u が以前にルートノードであった場合は、x が新しいルートになります。
削除
ノードxを削除する際は、まずツリーを検索してそのノードを見つけます。x.keyと同じキーを持つノードが見つからない場合、削除は行われません。
xが見つかったら、 xの左と右のサブツリーを2回ずつ探索し、左サブツリーの右のスパインと右サブツリーの左のスパインをランクの降順で1つのパスRに「ジッピング」します。このパスをトップダウンで作成する際、ノードはキーに基づいて、親ノードの左と右の子ノードとして追加されます。
パスRが完成すると、パスのルートがxに置き換わります。 xとx . parent間の親と子のポインタはそれに応じて更新され、x が以前のルートノードであった場合は、 Rの最上位ノードが新しいルートになります。
参考文献
- ^ ab Tarjan, Robert E.; Levy, Caleb C.; Timmel, Stephen (2021-10-31). 「Zip Trees」. ACM Transactions on Algorithms . 17 (4): 1– 12. arXiv : 1806.06726 . doi :10.1145/3476830. ISSN 1549-6325.
- ^ Gila, Ofek; Goodrich, Michael T.; Tarjan, Robert E. (2023). 「Zip-Zip Trees: Making Zip Trees More Balanced, Biased, Compact, or Persistent」. Morin, Pat; Suri, Subhash (eds.). Algorithms and Data Structures . Lecture Notes in Computer Science. Vol. 14079. Cham: Springer Nature Switzerland. pp. 474– 492. arXiv : 2307.07660 . doi :10.1007/978-3-031-38906-1_31. ISBN 978-3-031-38906-1。
