AVLツリー

AVLツリー
AVLツリー
タイプ	木
発明された	1962
発明者	ゲオルギー・アデルソン＝ヴェルスキーとエフゲニー・ランディス
ビッグO記法の複雑さ
空間
空間の複雑さ
空間
時間計算量
関数
検索
入れる
消去

コンピュータサイエンスにおいて、AVL ツリー(発明者のA delson -velskyとL andis にちなんで名付けられた) は、自己バランス型二分探索ツリーです。AVL ツリーでは、どのノードの 2 つの子サブツリーの高さも、最大でも 1 しか異なりません。高さが 1 以上異なる場合はいつでも、この特性を復元するために再バランス調整が行われます。検索、挿入、削除はすべて、平均の場合も最悪の場合も $O (log n)時間がかかります。ここで、は操作前のツリー内のノードの数です。挿入と削除を行うと、1 回以上の$ ツリー回転によってツリーの再バランス調整が必要になる場合があります。 $n$

AVLツリーは、1962年に論文「情報の組織化のためのアルゴリズム」で発表したソ連の2人の発明者、ゲオルギー・アデルソン＝ヴェルスキーとエフゲニー・ランディスにちなんで名付けられました。 ^[2]これは、発明された最初の自己バランス型二分探索木データ構造です。 ^[3]

AVL木は、同じ操作セットをサポートし、基本的な操作に時間がかかることから、赤黒木とよく比較されます。検索集約型のアプリケーションでは、AVL木の方が厳密にバランスが取れているため、赤黒木よりも高速です。 ^[4]赤黒木と同様に、AVL木は高さバランスが取れています。一般的に、どちらも任意のに対して重みバランスもバランスも取れていません。^[5]つまり、兄弟ノードの子孫の数は非常に異なる場合があります。 ${\text{O}}(\log n)$ $\mu$ $\mu \leq {\tfrac {1}{2}}$

意味

バランス係数

二分木では、ノードXのバランス係数は高さの差として定義されます。

{\text{BF}}(X):={\text{高さ}}({\text{右サブツリー}}(X))-{\text{高さ}}({\text{左サブツリー}}(X))

^[6]^{: 459}

ノード X をルートとする 2 つの子サブツリー。

ノード X は「左重視」と呼ばれ、は「右重視」と呼ばれ、は単に「バランス型」と呼ばれることもあります。 ${\text{BF}}(X)<0$ ${\text{BF}}(X)>0$ ${\text{BF}}(X)=0$

プロパティ

バランス係数は、以前のバランス係数と高度の変化を知ることで最新の状態に保たれます。絶対高度を知る必要はありません。AVLバランス情報を保持するには、ノードごとに2ビットで十分です。^[7]

ノードを持つAVL木の高さ（最大レベル数として数える）は、次の間隔にある：^[6]^：460 $h$ $n$

\log _{2}(n+1)\leq h<\log _{\varphi }(n+2)+b

ここでは黄金比であり、これは高さのAVLツリーには少なくとものノードが含まれるためであり、ここではシード値を持つフィボナッチ数列である。 $\varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618$ $b:={\frac {\log _{2}5}{2\log _{2}\varphi }}-2\approx \;-0.3277.$ $h$ $F_{h+2}-1$ $\{F_{n}\}_{n\in \mathbb {N}}$ $F_{1}=F_{2}=1.$

オペレーション

AVL ツリーの読み取り専用操作では、不均衡なバイナリ検索ツリーで実行されるのと同じアクションが実行されますが、変更ではサブツリーの高さのバランスを観察して復元する必要があります。

検索中

AVL 木における特定のキーの検索は、任意のバランス型またはアンバランス型の二分探索木と同じ方法で実行できます。^[8]^{: ch. 8}検索を効果的に行うには、キーのセットに全順序(または少なくとも全事前順序) を確立する比較関数を使用する必要があります。 ^[9]^{: 23 検索を成功させるために必要な比較の回数は高さ} $h$ によって制限され、検索に失敗した場合に必要な比較の回数は $h$ に非常に近いため、どちらも $O(log n)$ です。^[10]^{: 216}

トラバーサル

読み取り専用操作として、AVL ツリーのトラバーサルは他のバイナリツリーと同じように機能します。ツリーの $n$ 個のノードすべてを探索すると、各リンクが正確に 2 回訪問されます。1 回目は下方向の訪問で、そのノードをルートとするサブツリーに入り、2 回目は上方向の訪問で、探索後にそのノードのサブツリーを離れます。

AVL ツリーでノードが見つかると、次のノードまたは前のノードに償却定数時間でアクセスできます。 ^[11]^{: 58}これらの「近くの」ノードを探索するインスタンスによっては、最大 $h \propto log(n)$ 個のリンクをたどる必要があります (特に、ルートの左サブツリーの右端のリーフからルートへ、またはルートからルートの右サブツリーの左端のリーフへ移動する場合。図 1 の AVL ツリーでは、ノード P から右から 2 番目のノード Q への移動には 3 ステップかかります)。どのツリーにも $n -1$ 個のリンクがあるため、償却コストは $2\times(n -1)/ n$ つまり約 2 です。

入れる

AVL ツリーにノードを挿入する場合、最初はバイナリ検索ツリーに挿入する場合と同じプロセスに従います。ツリーが空の場合、ノードはツリーのルートとして挿入されます。ツリーが空でない場合は、ルートを下り、ツリーを再帰的に下りて、新しいノードを挿入する場所を探します。このトラバーサルは比較関数によってガイドされます。この場合、ノードは常にツリー内の外部ノードの NULL 参照 (左または右) を置き換えます。つまり、ノードは外部ノードの左の子または右の子になります。

この挿入後、ツリーが不均衡になった場合、新しく挿入されたノードの祖先のみが不均衡になります。これは、それらのノードのみがサブツリーを変更されたためです。^[12]そのため、ノードの祖先ごとにAVLツリーの不変量との一貫性をチェックする必要があります。これは「リトレース」と呼ばれます。これは、各ノードのバランス係数を考慮することで実現されます。^[6]^{: 458–481} ^[11]^{: 108}

一度の挿入では AVL サブツリーの高さは 1 より大きくは増加できないため、挿入後のノードの一時的なバランス係数は[–2,+2] の範囲になります。チェックされた各ノードについて、一時的なバランス係数が –1 から +1 の範囲に留まる場合は、バランス係数の更新のみが必要で、回転は必要ありません。ただし、一時的なバランス係数が ±2 の場合は、このノードをルートとするサブツリーは AVL 不均衡であり、回転が必要です。^[9]^{: 52}以下のコードが示すように、挿入を行うと、適切な回転によってツリーのバランスが即座に完全に回復します。

図 1 では、新しいノード Z をノード X の子として挿入すると、そのサブツリー Z の高さが 0 から 1 に増加します。

挿入のための再トレースループの不変量

Z をルートとするサブツリーの高さが 1 増加しました。すでに AVL 形状になっています。

すべてのノードのバランス係数を更新するには、まず、修正が必要なすべてのノードが、挿入されたリーフのパスに沿って子から親まで配置されていることを確認します。上記の手順をリーフから始めて、このパスに沿ったノードに適用すると、ツリー内のすべてのノードのバランス係数は再び -1、0、または 1 になります。

バランス係数が 0 になり、そのサブツリーの高さが変更されないことを意味する場合、再トレースは停止できます。

バランス係数が ±1 になると、サブツリーの高さが 1 増加し、再トレースを続行する必要があります。

バランス係数が一時的に ±2 になった場合は、適切な回転によって修復する必要があり、その後、サブツリーは以前と同じ高さになります (ルートのバランス係数は 0 になります)。

必要な時間は検索に $O(log n)$ 、ルートに戻る途中で最大 $O(log n)$ レベルの再トレース（平均 $O(1) ）がかかるため、操作は$ $O(log n)$ 時間で完了します。^[9]^{: 53}

消去

ノードを削除するための準備手順については、二分探索木#削除のセクションで説明されています。そこでは、対象ノードまたは置換ノードの実際の削除により、そのノードに子がある場合は、対応する子ツリーの高さが 1 から 0 に、または 2 から 1 に減少します。

このサブツリーから始めて、それぞれの祖先が AVL ツリーの不変条件と一貫しているかどうかを確認する必要があります。これは「リトレース」と呼ばれます。

単一の削除では AVL サブツリーの高さは 1 より小さくなることはないため、ノードの一時的なバランス係数は -2 から +2 の範囲になります。バランス係数が -1 から +1 の範囲に留まる場合は、AVL ルールに従って調整できます。バランス係数が ±2 になった場合は、サブツリーはアンバランスであり、回転する必要があります。(回転によって常にツリーのバランスが取れる挿入とは異なり、削除後は BF(Z) ≠ 0 になる場合があります (図 2 および 3 を参照)。そのため、適切な単一または二重の回転の後、再バランス調整されたサブツリーの高さは 1 減少し、ツリーを次の上位レベルで再度再バランス調整する必要があります。) 回転のさまざまなケースについては、「再バランス調整」のセクションで説明します。

削除のための再トレースループの不変量

N をルートとするサブツリーの高さが 1 減少しました。すでに AVL 形状になっています。

バランス係数が ±1 (0 であったはず) になった場合、再トレースは停止します。これは、そのサブツリーの高さが変わらないことを意味します。

バランス係数が 0 になった場合 (±1 であったはずです)、サブツリーの高さは 1 減少し、再トレースを続行する必要があります。

バランス係数が一時的に ±2 になった場合、適切な回転によってこれを修復する必要があります。サブツリーの高さが 1 減少して再トレースが継続されるか、または変化せず (Z のバランス係数が 0 の場合)、ツリー全体が AVL 形状になるかは、兄弟 Z (図 2 の上位の子ツリー) のバランス係数によって決まります。

必要な時間は検索に $O(log n)$ 、ルートに戻る途中で最大 $O(log n)$ レベルの再トレース (平均 $O(1) ) がかかるため、操作は$ $O(log n)$ 時間で完了します。

セット操作と一括操作

単一要素の挿入、削除、検索操作に加えて、AVLツリーには、和集合、積集合、差集合といったいくつかの集合操作が定義されています。これらの集合関数に基づいて、挿入や削除の高速な一括操作を実装できます。これらの集合操作は、分割と結合という2つのヘルパー操作に依存しています。新しい操作により、AVLツリーの実装はより効率的で、並列化も容易になります。^[13]

関数Join を2 つの AVL ツリー $t 1$ と $t 2$ およびキー $kに対して実行すると、$ $t 1$ 、 $t 2$ および $k$ のすべての要素を含むツリーが返されます。 $k は$ $t 1$ のすべてのキーより大きく、 $t 2$ のすべてのキーより小さくなければなりません。 2 つのツリーの高さの差が最大でも 1 の場合、Join は左サブツリー $t 1$ 、ルート $k$ および右サブツリー $t 2$ を持つ新しいノードを単に作成します。それ以外の場合、 $t 1が$ $t 2$ より 1 以上高いと仮定します (その他の場合は対称です)。 Join は、 $t$ $2$ とバランスが取れているノード $cまで$ $t 1$ の右スパインをたどります。この時点で、左の子 $c$ 、ルート $k$ および右の子 $t$ $2$ を持つ新しいノードが作成され、 c が置き換えられます。新しいノードは AVL 不変条件を満たし、その高さは $c$ より 1 大きくなります。これは、親で無効な場合は二重回転で修正するか、ツリーの上位で無効な場合は単一の左回転で修正できます。どちらの場合も、それ以降の祖先ノードの高さが復元されます。したがって、結合には最大で 2 回の回転が必要です。この関数のコストは、2 つの入力ツリー間の高さの差です。

$AVL ツリーを、キーk$ より小さいツリーとキー $k$ より大きいツリーの2 つの小さいツリーに分割するには、まず、ルートからAVL に $k を挿入してパスを描画します。この挿入後、$ $k$ より小さいすべての値はパスの左側に、 $k$ より大きいすべての値は右側に見つかります。Join を適用すると、左側のすべてのサブツリーが、パス上のキーを下から上への中間ノードとして使用してボトムアップでマージされ、左側のツリーが形成され、右側の部分は非対称になります。Splitのコストは、ツリーの高さのオーダーで $O(log n)$ です。

$集合A$ と $B$ を表す2 つの AVL 木 $t 1$ と $t 2$ の和集合は、 $A$ $\cup$ $B を$ 表すAVL $t$ です。

交差または差異のアルゴリズムは似ていますが、Joinと同じだが中間キーがないJoin2ヘルパールーチンが必要です。結合、交差、差異の新しい関数に基づいて、1 つまたは複数のキーを AVL ツリーに挿入したり、AVL ツリーから削除したりできます。SplitはJoin を呼び出しますが、AVL ツリーのバランス基準を直接処理しないため、このような実装は通常、「結合ベース」の実装と呼ばれます。

サイズがおよびの AVL 木の場合、和集合、積集合、差集合のそれぞれの計算量はです。さらに重要なのは、和集合、積集合、差集合への再帰呼び出しは互いに独立しているため、並列深度で並列実行できることです。^[13]のとき、結合ベースの実装は単一要素の挿入および削除と同じ計算 DAG を持ちます。 ${\text{O}}\left(m\log \left({n \over m}+1\right)\right)$ $m$ $n\;(\geq m)$ ${\text{O}}(\log m\log n)$ $m=1$

バランス調整

修正操作中に 2 つの子サブツリー間の高さの差が変わった場合、その差が 2 未満であれば、親のバランス情報の適応によってそれが反映される可能性があります。挿入および削除操作中に (一時的な) 高さの差が 2 になる場合があり、これは親サブツリーを「再バランス」する必要があることを意味します。与えられた修復ツールは、いわゆるツリー回転です。これは、キーを「垂直」にのみ移動し、キーの (「水平」) 順序が完全に保持されるためです (これはバイナリ検索ツリーにとって不可欠です)。^[6]^{: 458–481} ^[11]^{: 33}

X を (一時的な) バランス係数が -2 または +2 であるノードとします。その左または右のサブツリーが変更されました。Z をより高いサブツリーを持つ子とします (図 2 および 3 を参照)。帰納仮説により、両方の子が AVL 形状になっていることに注意してください。

挿入の場合、この挿入は Z の子供の 1 人に起こったため、Z の身長は増加しました。削除の場合、この削除は Z の兄弟 t ₁に起こったため、すでに低い t ₁の身長はさらに減少しました。(これは、Z のバランス係数が 0 になる可能性がある唯一のケースです。)

違反には 4 つの種類が考えられます。

リバランスは異なる方法で実行されます。

これにより、状況はCBと表され、C (= 子の方向) とB (= バランス)は、 Right := − Leftの集合{ Left、Right }から取得されます。C == Bの場合のバランス違反は、単純な回転(− C ) によって修復されますが、C != Bの場合は、二重回転CBによって修復されます。rotate_rotate_

回転のコストは、単純回転でも二重回転でも一定です。

単純な回転

図 2 は Right Right 状況を示しています。上半分では、ノード X にバランス係数+2の 2 つの子ツリーがあります。さらに、 Z の内側の子 t ₂₃ (つまり、 Z が右の子の場合は左の子、 Z が左の子の場合は右の子) は、兄弟の t _{4よりも高くありません。これは、サブツリー t}₄の高さの増加、またはサブツリー t ₁の高さの減少によって発生する可能性があります。後者の場合、 t _{23 の}高さが t ₄と同じになる淡い状況も発生する可能性があります。

左回転の結果は図の下半分に示されています。3 つのリンク (図 2 の太いエッジ) と 2 つのバランス係数が更新されます。

図が示すように、挿入前はリーフレイヤーはレベル h+1 にあり、一時的にレベル h+2 になり、回転後は再びレベル h+1 になります。削除の場合、リーフレイヤーはレベル h+2 にあり、t ₂₃と t ₄が同じ高さのときは再び同じレベルになります。それ以外の場合は、リーフレイヤーはレベル h+1 に達するため、回転したツリーの高さは減少します。

単純な左回転のコードスニペット

ノード* rotate_Left (ノード* X 、ノード* Z ) {     
    // Z は兄弟より 2 大きい
    t23 = left_child ( Z ); // Z の内側の子   
    右の子( X ) = t23 ;  
    （t23 != null ）の場合   
        親（t23 ）= X ;  
    左の子( Z ) = X ;  
    親（X ）= Z ;  
    // 1番目のケース、BF(Z) == 0、
    // 挿入ではなく削除の場合にのみ発生します:
    if ( BF ( Z ) == 0 ) { // t23はt4と同じ高さになっている     
        BF ( X ) = + 1 ; // t23 が高くなった     
        BF ( Z ) = – 1 ; // t4 は X より低くなる     
    }それ以外 
    { // 2 番目のケースは挿入または削除で発生します: 
        BF ( X ) = 0 ;  
        BF ( Z ) = 0 ;  
    }
    return Z ; // 回転したサブツリーの新しいルートを返す  
}

二重回転

図 3 は、Right Left の状況を示しています。ノード X の上部 3 分の 1 には、バランス係数が+2の 2 つの子ツリーがあります。ただし、図 2 とは異なり、 Z の内側の子 Y は、その兄弟 t ₄よりも高くなっています。これは、 Y 自体の挿入、またはそのサブツリー t ₂または t ₃のいずれかの高さの増加(その結果、高さが異なります)、またはサブツリー t ₁の高さの減少によって発生する可能性があります。後者の場合、 t ₂と t ₃の高さが同じになることもあります。

最初の右回転の結果は、図の中央 3 分の 1 に示されています。(バランスファクターに関しては、この回転は他の AVL 単一回転と同じ種類のものではありません。Y と t ₄の高さの差は 1 しかないためです。) 最後の左回転の結果は、図の下 3 分の 1 に示されています。5 つのリンク (図 3 の太いエッジ) と 3 つのバランスファクターを更新する必要があります。

図が示すように、挿入前は、リーフレイヤーはレベル h+1 にあり、一時的にレベル h+2 にあり、二重回転後には再びレベル h+1 にあります。削除の場合、リーフレイヤーはレベル h+2 にあり、二重回転後にはレベル h+1 にあるため、回転したツリーの高さは低くなります。

右左二重回転のコードスニペット

ノード* rotate_RightLeft (ノード* X 、ノード* Z ) {     
    // Z は兄弟より 2 大きい
    Y = left_child ( Z ); // Z の内側の子   
    // Yは兄弟より1だけ大きい
    t3 =右の子( Y );  
    左の子( Z ) = t3 ;  
    t3 ! = nullの場合   
        親( t3 ) = Z ;  
    右の子( Y ) = Z ;  
    親（Z ）= Y ;  
    t2 =左の子( Y );  
    右の子( X ) = t2 ;  
    t2がnullの場合   
        親( t2 ) = X ;  
    左の子( Y ) = X ;  
    親（X ）= Y ;  
    // 1番目のケース、BF(Y) == 0
    BF ( Y ) == 0の場合    
        BF ( X ) = 0 ;  
        BF ( Z ) = 0 ;  
    }そうでない場合( BF ( Y ) > 0 ) {      
        // t3 の方が高かった
        BF ( X ) = – 1 ; // t1 が高くなった    
        BF ( Z ) = 0 ;  
    }それ以外{  
        // t2 の方が高かった
        BF ( X ) = 0 ;  
        BF ( Z ) = + 1 ; // t4 が高くなった    
    }
    BF ( Y ) = 0 ;  
    return Y ; // 回転したサブツリーの新しいルートを返す  
}

他の構造との比較

AVL 木と赤黒 (RB) 木はどちらも自己バランス型二分探索木であり、数学的に関連しています。実際、すべての AVL 木は赤黒に色付けできますが^[14]、AVL バランスではない RB 木もあります。AVL (または RB) 木の不変量を維持するために、回転が重要な役割を果たします。最悪の場合、回転がない場合でも、AVL または RB の挿入または削除には $O(log n)$ の検査および/または AVL バランス係数 (または RB 色) の更新が必要です。RB の挿入と削除および AVL の挿入には 0 から 3 回の末尾再帰回転が必要であり、償却 $O(1)$ 時間で実行されます^[15]^{: pp.165, 158} ^[16]したがって、平均して同様に一定です。最悪の場合に $O(log n) の回転を必要とする AVL 削除も平均で$ $O(1)$ です。 RB ツリーでは各ノードに 1 ビットの情報 (色) を格納する必要がありますが、AVL ツリーではバランス係数に主に 2 ビットを使用します。ただし、子に格納する場合は、「兄弟より低い」という意味を持つ 1 ビットで十分です。2 つのデータ構造の大きな違いは、高さの制限です。

$サイズn$ $\geq 1$ の木の場合

AVLツリーの高さは最大で
${\begin{array}{ll}h&\leqq \;c\log _{2}(n+d)+b\\&<\;c\log _{2}(n+2)+b\end{array}}$

ここで黄金比、および。

\varphi :={\tfrac {1+{\sqrt {5}}}{2}}\approx 1.618

c:={\tfrac {1}{\log _{2}\varphi }}\approx 1.440,

b:={\tfrac {c}{2}}\log _{2}5-2\approx \;-0.328,

d:=1+{\tfrac {1}{\varphi ^{4}{\sqrt {5}}}}\approx 1.065

RBツリーの高さは最大で
${\begin{array}{ll}h&\leqq \;2\log _{2}(n+1)\end{array}}$ ^[17 ]

AVLツリーはRBツリーよりも厳格にバランスが取れており、最大高さの漸近関係AVL/RB≈0.720です。挿入と削除については、ベン・パフは79の測定でAVL/RBが0.677から1.077の間、中央値が≈0.947、幾何平均が≈0.910の関係を示しています。^[4]

参照

参考文献

^ abcdef Eric Alexander. 「AVL Trees」。2019年7月31日時点のオリジナルよりアーカイブ。
^ Adelson-Velsky, Georgy; Landis, Evgenii (1962). 「情報の組織化のためのアルゴリズム」。USSR科学アカデミー紀要（ロシア語）。146 : 263–266。Myron J. Ricciによる英訳、Soviet Mathematics - Doklady、3:1259–1263、1962年。
^ セジウィック、ロバート(1983)。「バランスツリー」。アルゴリズム。アディソン・ウェズリー。p. 199。ISBN 0-201-06672-6。
^ ab Pfaff, Ben (2004 年 6 月). 「システムソフトウェアにおける BST のパフォーマンス分析」(PDF) .スタンフォード大学.
^ AVL木は重みバランスが取れていない？（つまり、AVL木はμバランスが取れていない？）
したがって、二分木は、すべてのノードに対して不等式が成り立つ場合、で -バランスが取れていると呼ばれます。 $\mu$ $0\leq \mu \leq {\tfrac {1}{2}}$ $N$
${\tfrac {1}{2}}-\mu \leq {\tfrac {|N_{l}|}{|N|+1}}\leq {\tfrac {1}{2}}+\mu$
が成り立ち、この性質により最小となります。は、をルートとするツリーの下のノードの数(ルートを含む) であり、はの左の子ノードです。 $\mu$ $|N|$ $N$ $N_{l}$ $N$
^ abcd Knuth, Donald E. (2000). Sorting and searching (第2版、第6刷、新たに更新および改訂された版). Boston [ua]: Addison-Wesley. ISBN 0-201-89685-0。
^ ただし、バランス情報は、親が 1 または 2 高いかどうかを示す 1 ビットとして子ノードに保持できます。そのため、両方の子が 2 高いという状況は発生しません。このように、AVL ツリーは、Haeupler、Sen、および Tarjan によって考案された「ランクバランス」ツリーです。
^ Dixit, JB (2010). 「C」言語によるデータ構造の習得。インド、ニューデリー：University Science Press、Laxmi Publications Pvt. Ltd.の出版物。ISBN 9789380386720. OCLC 939446542.
^ abc Brass, Peter (2008).高度なデータ構造ケンブリッジ: ケンブリッジ大学出版局. ISBN 9780511438202. OCLC 312435417.
^ Hubbard, John Rast (2000). Schaum の Java によるデータ構造の理論と問題の概要。ニューヨーク: McGraw- Hill。ISBN 0071378707. OCLC 48139308.
^ abc Pfaff, Ben (2004).二分探索木とバランス木入門. Free Software Foundation, Inc.
^ Weiss, Mark Allen (2006). C++ におけるデータ構造とアルゴリズム分析(第 3 版). ボストン: Pearson Addison-Wesley. p. 145. ISBN 0-321-37531-9. OCLC 61278554.
^ ab Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016)、「並列順序付きセットのための単なる結合」、並列アルゴリズムとアーキテクチャに関するシンポジウム、ACM、pp. 253–264、arXiv : 1602.02120、doi :10.1145/2935764.2935768、ISBN 978-1-4503-4210-0、S2CID 2897793。
^ Paul E. Black (2015-04-13). 「AVL ツリー」。アルゴリズムとデータ構造の辞書。米国国立標準技術研究所。2016年 7 月 2 日閲覧。
^ Mehlhorn, Kurt; Sanders, Peter (2008). アルゴリズムとデータ構造。ベルリン、ハイデルベルク: Springer Berlin Heidelberg。doi : 10.1007 / 978-3-540-77978-0。ISBN 978-3-540-77977-3。
^ Dinesh P. Mehta、 Sartaj Sahni編 (2017-12-15)。データ構造とアプリケーションのハンドブック（第2版）。ニューヨーク：Chapman and Hall/CRC。doi :10.1201 / 9781315119335。ISBN 978-1-315-11933-5。
^ 赤黒木#境界の証明

さらに読む

Donald Knuth . The Art of Computer Programming、第 3 巻:ソートと検索、第 3 版。Addison-Wesley、1997 年。ISBN 0-201-89685-0。セクション 6.2.3: Balanced Trees の 458 ～ 475 ページ。
Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2015)、「ランクバランスツリー」(PDF)、ACM Transactions on Algorithms、11 (4): Art. 30、26、doi :10.1145/2689412、MR 3361215、S2CID 1407290。

外部リンク

この記事には、 Paul E. Blackのパブリックドメインマテリアルが組み込まれています。「 AVLツリー」。アルゴリズムとデータ構造の辞書。NIST 。

[wiscurl-1] Eric Alexander. 「AVL Trees」。2019年7月31日時点のオリジナルよりアーカイブ。

[2] Adelson-Velsky, Georgy; Landis, Evgenii (1962). 「情報の組織化のためのアルゴリズム」。USSR科学アカデミー紀要（ロシア語）。146 : 263–266。Myron J. Ricciによる英訳、Soviet Mathematics - Doklady、3:1259–1263、1962年。

[3] セジウィック、ロバート(1983)。「バランスツリー」。アルゴリズム。アディソン・ウェズリー。p. 199。ISBN 0-201-06672-6。

[Pfaff1-4] Pfaff, Ben (2004 年 6 月). 「システムソフトウェアにおける BST のパフォーマンス分析」(PDF) .スタンフォード大学.

[5] AVL木は重みバランスが取れていない？（つまり、AVL木はμバランスが取れていない？）
したがって、二分木は、すべてのノードに対して不等式が成り立つ場合、で -バランスが取れていると呼ばれます。 $\mu$ $0\leq \mu \leq {\tfrac {1}{2}}$ $N$
${\tfrac {1}{2}}-\mu \leq {\tfrac {|N_{l}|}{|N|+1}}\leq {\tfrac {1}{2}}+\mu$
が成り立ち、この性質により最小となります。は、をルートとするツリーの下のノードの数(ルートを含む) であり、はの左の子ノードです。 $\mu$ $|N|$ $N$ $N_{l}$ $N$

[Knuth-6] Knuth, Donald E. (2000). Sorting and searching (第2版、第6刷、新たに更新および改訂された版). Boston [ua]: Addison-Wesley. ISBN 0-201-89685-0。

[7] ただし、バランス情報は、親が 1 または 2 高いかどうかを示す 1 ビットとして子ノードに保持できます。そのため、両方の子が 2 高いという状況は発生しません。このように、AVL ツリーは、Haeupler、Sen、および Tarjan によって考案された「ランクバランス」ツリーです。

[dixit-mastering-data-structures-8] Dixit, JB (2010). 「C」言語によるデータ構造の習得。インド、ニューデリー：University Science Press、Laxmi Publications Pvt. Ltd.の出版物。ISBN 9789380386720. OCLC 939446542.

[brass-advanced-data-structures-9] Brass, Peter (2008).高度なデータ構造ケンブリッジ: ケンブリッジ大学出版局. ISBN 9780511438202. OCLC 312435417.

[hubbard-outline-theory-problems-10] Hubbard, John Rast (2000). Schaum の Java によるデータ構造の理論と問題の概要。ニューヨーク: McGraw- Hill。ISBN 0071378707. OCLC 48139308.

[Pfaff-11] Pfaff, Ben (2004).二分探索木とバランス木入門. Free Software Foundation, Inc.

[12] Weiss, Mark Allen (2006). C++ におけるデータ構造とアルゴリズム分析(第 3 版). ボストン: Pearson Addison-Wesley. p. 145. ISBN 0-321-37531-9. OCLC 61278554.

[join-based-13] Blelloch, Guy E.; Ferizovic, Daniel; Sun, Yihan (2016)、「並列順序付きセットのための単なる結合」、並列アルゴリズムとアーキテクチャに関するシンポジウム、ACM、pp. 253–264、arXiv : 1602.02120、doi :10.1145/2935764.2935768、ISBN 978-1-4503-4210-0、S2CID 2897793。

[14] Paul E. Black (2015-04-13). 「AVL ツリー」。アルゴリズムとデータ構造の辞書。米国国立標準技術研究所。2016年 7 月 2 日閲覧。

[15] Mehlhorn, Kurt; Sanders, Peter (2008). アルゴリズムとデータ構造。ベルリン、ハイデルベルク: Springer Berlin Heidelberg。doi : 10.1007 / 978-3-540-77978-0。ISBN 978-3-540-77977-3。

[Dinesh-16] ^ Dinesh P. Mehta、 Sartaj Sahni編 (2017-12-15)。データ構造とアプリケーションのハンドブック（第2版）。ニューヨーク：Chapman and Hall/CRC。doi :10.1201 / 9781315119335。ISBN 978-1-315-11933-5。

[17] 赤黒木#境界の証明

意味