レベルリンク（2,4）-データ構造内のツリー

このセクションでは、レベルリンクを導入することにより、（2,4）ツリーが効率的な指検索をサポートする方法について説明します。このセクションで説明するアイデアは、b≥2aの場合、（a、b）-treesで示されるより一般的なクラスの高さバランスの取れたツリーにも実装されます。

（2,4）ツリーは、すべての葉が同じ深さを持ち、すべての内部ノードが2、3、または4次である高さバランスのとれた探索木として定義されます。要素はリーフに保存され、内部ノードは検索をガイドするための検索キーのみを保存します。各内部ノードの次数は少なくとも2であるため、（2,4）ツリーの高さはO（log n）であり、O（log n）時間での検索をサポートします。 （2,4）-treesの重要な特性は、指によって提供される挿入と削除に償却O（1）時間がかかることです（この特性は（2、3）-treesによって共有されません。ここでは、m個の挿入のシーケンスが存在します。 Θ（mlog m）時間を必要とする削除）。さらに、m枚の葉を持つ（2,4）ツリーは、償却されたO（log min（m1、m2））時間でサイズm1とm2の2つのツリーに分割できます。同様に、サイズm1とm2の2つの（2,4）ツリーは、償却されたO（log min（m1、m2））時間で結合（連結）できます。

指検索をサポートするために、（2,4）-ツリーはレベルリンクで拡張され、同じ深さのすべてのノードが二重リンクリストで一緒にリンクされます。次の図は、レベルリンクで拡張された（2,4）ツリーを示しています。すべてのエッジが双方向リンクを表すことを忘れないでください。追加のレベルリンクは、（2,4）ツリーの挿入、削除、分割、および結合中に簡単に保持できます。

XからYへの指検索を実行するには、最初にYがXの左側にあるか右側にあるかを確認します。一般性を失うことなく、YがXの右側にあると仮定します。次に、Xからルートに向かうパスにアクセスしてYがVまたはVの右隣をルートとするサブツリー内に含まれることが確立されるまで、パス上のノードVとその右隣。次に、上向きの検索が終了し、最大で2つの下向きのyの検索が、それぞれVおよび/またはVの右隣で開始されます。図1では、jからtへの指の検索中にたどるポインターは太い線で示されています。

O（log d）の検索時間は、ノードVの親に上向きの検索を進めると、YはVの右隣の左端のサブツリーの右側にある、つまりdは少なくとも指数関数的であるという観察結果に基づいています。これまでに高さに達しました。

図1では、「ln」というラベルの付いた内部ノードから「h」というラベルの付いたノードに進みます。これは、「s」から、Yがノード「qr」のサブツリーの右側にあることがわかっているためです。

レベルリンク（2,4）ツリーの構築は、外部メモリに実装できるレベルリンク（a、b）ツリーに直接一般化されます。内部ノードが外部メモリのブロックに収まるようにa=2bとbを選択することにより、O（1）メモリ転送での挿入と削除をサポートする外部メモリフィンガーサーチツリーと、O（logb n）メモリ転送でのフィンガーサーチを実現します。 。