インターリーブ下限

をLeft ( y )にある内のすべてのノードの最下位共通祖先と定義します。 内の任意の2 つのノードが与えられた場合、との最下位共通祖先 ( ) は次の不等式を満たします。したがって、はLeft(y)にあり、 はにおける最小深さの唯一のノードです。 同じ推論が 、 Right(y)にある 内のすべてのノードの最下位共通祖先にも適用できます。 さらに、 Left(y)とright(y)のすべてのポイントの最下位共通祖先も、これらのセットのいずれかにあります。 したがって、唯一の最小深さノードは、Left(y)とright(y)のノードの間でなければなりません。 より正確には、または のいずれかです。 が であると仮定します。その場合、は の祖先です。 したがって、 は、ルートから へのパスに が含まれるため、遷移ポイントです。さらに、のルートから のサブツリー内のノードへの任意のパスは、 がそのすべてのノードの祖先であるため、 を訪問する必要があります。また、 の右領域内のノードへの任意のパスは、right(y)のすべてのノードの最下位の共通祖先であるため、を訪問する必要があります。結論として、は におけるの唯一の遷移点です。 ${\displaystyle \ell }$${\displaystyle T_{i}}$${\displaystyle a<b}$${\displaystyle T_{i}}$${\displaystyle a}$${\displaystyle b}$${\displaystyle lca(a,b)}$${\displaystyle a\leq lca(a,b)\leq b}$${\displaystyle \ell }$${\displaystyle \ell }$${\displaystyle T_{i}}$${\displaystyle r}$${\displaystyle T_{i}}$${\displaystyle \ell }$${\displaystyle r}$${\displaystyle \ell }$${\displaystyle \ell }$${\displaystyle r}$${\displaystyle r}$${\displaystyle r}$${\displaystyle \ell }$${\displaystyle T_{i}}$${\displaystyle y}$${\displaystyle \ell }$${\displaystyle r}$${\displaystyle r}$${\displaystyle y}$${\displaystyle T_{i}}$

補題 1 と同じ、 との定義について考えます。一般性を失うことなく、 がBST における時刻の の祖先であり、 で示されると仮定します。結果として、はの遷移点になります。仮定により、 BST アルゴリズムは の全体にわたって、遷移点 (この場合 ) には触れません。したがって、 Right(y)のどのノードにも触れません。その結果、はRight(y)の任意の 2 つのノードの最下位共通祖先のままです。ただし、アクセス アルゴリズムはLeft(y)のノードに触れる可能性があります。より正確には、時刻 でLeft(y)のすべてのノードの最下位共通祖先に触れる可能性があります。これを で示します。それでも、 は次の理由での祖先のままです。まず、時刻 にをルートとするツリーの外側にあったLeft (y)のノードは、時刻でこのツリーに入ることはできません。これは、 がこの時間枠で触れられていないためです。次に、どの時刻 についても、をルートとするツリーの外側にあるLeft(y)のノードが少なくとも 1 つ存在します。これは、 が最初はのサブツリーの外側にあったためであり、この時間枠ではツリーの外側のノードは に入ることができません。ここで を考えてみましょう。は のサブツリー内にないため、 になることはできません。したがって、であるため、 はLeft(y)内になければなりません。したがって、 はの祖先でなければならず、結果として の時点での祖先でなければなりません。したがって、ルートから へのパス上には常にLeft(y)のノードが存在し、それが遷移点として残ります。 ${\displaystyle \ell }$${\displaystyle r}$${\displaystyle \ell }$${\displaystyle r}$${\displaystyle j}$${\displaystyle T_{j}}$${\displaystyle r}$${\displaystyle y}$${\displaystyle r}$${\displaystyle [j,k]}$${\displaystyle r}$${\displaystyle i}$${\displaystyle \ell _{i}}$${\displaystyle \ell _{i}}$${\displaystyle r}$${\displaystyle r}$${\displaystyle j}$${\displaystyle i\in [j,k]}$${\displaystyle r}$${\displaystyle \ell _{i}'}$${\displaystyle r}$${\displaystyle i\in [j,k]}$${\displaystyle \ell }$${\displaystyle r}$${\displaystyle a_{i}=lca(\ell _{i}',r)}$${\displaystyle a_{i}}$${\displaystyle r}$${\displaystyle \ell _{i}'}$${\displaystyle r}$${\displaystyle a_{i}}$${\displaystyle \ell _{i}'\leq a_{i}\leq r}$${\displaystyle \ell _{i}}$${\displaystyle a_{i}}$${\displaystyle r}$${\displaystyle i}$${\displaystyle r}$${\displaystyle r}$

2 つの異なるノード が与えられます。をそれぞれの最小共通祖先とします。補題 1 から、 の遷移点はの場合またはであることが分かります。ここで、考慮すべき主なケースが 2 つあります。 ${\displaystyle y_{1},y_{2}\in P}$${\displaystyle r_{1},\ell _{1},r_{2},\ell _{2}}$${\displaystyle Right(y_{1}),Left(y_{1}),Right(y_{2}),Left(y_{2})}$${\displaystyle y_{i}}$${\displaystyle \ell _{i}}$${\displaystyle r_{i}}$${\displaystyle i\in \{1,2\}}$

ケース 1:との間には祖先関係がありません。したがって、と はすべて互いに素です。したがって、、および遷移点は異なります。 ${\displaystyle y_{1}}$${\displaystyle y_{2}}$${\displaystyle P}$${\displaystyle Left(y_{1}),Left(y_{2}),Right(y_{1}),}$${\displaystyle Right(y_{2})}$${\displaystyle r_{1}\neq r_{2}\neq \ell _{1}\neq \ell _{2}}$

ケース 2:一般性を失うことなく、が のの祖先であると仮定します。 ${\displaystyle y_{1}}$${\displaystyle y_{2}}$${\displaystyle P}$

ケース 2.1:の遷移点が の をルートとする木にないとします。したがって、 はおよびとは異なり、結果として の遷移点は となります。 ${\displaystyle y_{1}}$${\displaystyle y_{2}}$${\displaystyle P}$${\displaystyle \ell _{2}}$${\displaystyle r_{2}}$${\displaystyle y_{2}}$

ケース 2.2: の遷移点は、 のをルートとするツリー内にあります。より正確には、これはとの最下位の共通祖先の 1 つです。言い換えると、これはまたは のいずれかです。 ${\displaystyle y_{1}}$${\displaystyle y_{2}}$${\displaystyle P}$${\displaystyle Left(y_{2})}$${\displaystyle right(y_{2})}$${\displaystyle \ell _{2}}$${\displaystyle r_{2}}$

がをルートとするサブツリーの最下位の共通祖先であり、が含まれていないとします。と のどちらかが遷移点であるため、 と は よりも深くなります。 が遷移点であるとします。すると、 はよりも深くありません。この場合、は の遷移点であり、は の遷移点です。が よりも深くない場合にも、同様の推論が適用されます。つまり、 の遷移点はとよりも深くなく、より深い方を遷移点として持っています。 ${\displaystyle a_{1}}$${\displaystyle y_{1}}$${\displaystyle y_{2}}$${\displaystyle \ell _{2}}$${\displaystyle r_{2}}$${\displaystyle a_{1}}$${\displaystyle \ell _{2}}$${\displaystyle \ell _{2}}$${\displaystyle r_{2}}$${\displaystyle \ell _{2}}$${\displaystyle y_{1}}$${\displaystyle r_{2}}$${\displaystyle y_{2}}$${\displaystyle r_{2}}$${\displaystyle \ell _{2}}$${\displaystyle y_{1}}$${\displaystyle \ell _{2}}$${\displaystyle r_{2}}$${\displaystyle y_{2}}$

結論として、遷移ポイントはすべてのケースで異なります。