二分探索木

コンピュータサイエンスにおいて、二分探索木（BST）は、順序付き二分木またはソート済み二分木とも呼ばれ、各内部ノードのキーがそのノードの左部分木内のすべてのキーよりも大きく、右部分木内のすべてのキーよりも小さい、根付き二分木データ構造です。二分探索木に対する操作の時間計算量は、木の高さに対して線形です。

二分探索木は、データの高速な検索、追加、削除を可能にする二分探索を可能にします。二分探索木のノードは、各比較で残りの木の約半分をスキップするように配置されているため、検索性能は二進対数に比例します。二分探索木は、ラベル付きデータの効率的な保存という問題のために1960年代に考案され、コンウェイ・バーナーズ＝リーとデビッド・ウィーラーに帰属します。

二分探索木のパフォーマンスは、ノードを木に挿入する順序に依存します。任意の挿入は縮退を引き起こす可能性があるためです。二分探索木には、最悪の場合のパフォーマンスが保証されるいくつかのバリエーションがあります。基本的な操作には、検索、走査、挿入、削除があります。最悪の場合の複雑さが保証された二分探索木は、線形検索時間を必要とするソートされていない配列よりも優れたパフォーマンスを発揮します。

BSTの複雑性分析によると、平均して挿入、削除、検索には時間がかかります。 $\Theta (\log n)$ のために $n$ ノード。最悪の場合、単方向連結リストに劣化する。 $O(n)$ 任意の挿入と削除による木の高さの際限のない増加に対処するため、最悪の検索複雑度を二進対数に制限する自己平衡二分探索木の変種が導入された。AVL 木は、1962 年に Georgy Adelson-VelskyとEvgenii Landisによって発明された最初の自己平衡二分探索木である。^{[ 1 ]}^{[ 2 ]}^{[ 3 ]}

二分探索木は、動的セット、ルックアップテーブル、優先度キューなどの抽象データ型を実装するために使用でき、ツリーソートなどのソートアルゴリズムにも使用できます。

歴史

二分探索木アルゴリズムは、PF ウィンドリー、アンドリュードナルドブース、アンドリューコリン、トーマス N. ヒバードなど、複数の研究者によって独立して発見されました。^{[ 4 ]}^{[ 5 ]}このアルゴリズムは、 1960 年に磁気テープにラベル付きデータを格納するために使用したコンウェイバーナーズ＝リーとデビッドウィーラーに帰属します。 ^[⁶^]最も初期の人気のある二分探索木アルゴリズムの 1 つは、ヒバードのものです。^[⁴^]

二分探索木の時間計算量は、ノードが任意の順序で挿入される場合、木の高さとともに際限なく増加するため、木の高さを制限するために自己平衡二分探索木が導入されました。 $O(\log n)$ ^{[ 7 ]}木の高さを制限するために、 AVL木、Treaps、赤黒木など、さまざまな高さバランスの取れた二分探索木が導入されました。^[⁸^]

概要

二分探索木は、根付き二分木であり、ノードは厳密な全順序で配置され、特定のノードAよりも大きいキーを持つノードはノードAの右部分木に格納され、 A以下のキーを持つノードはAの左部分木に格納され、二分探索特性を満たす。^[⁹^]^:²⁹⁸^[¹⁰^]^:²⁸⁷

二分探索木は、ソートや検索アルゴリズムにも有効です。ただし、二分探索木の探索複雑度は、ノードの挿入と削除の順序に依存します。最悪の場合、二分探索木での連続操作は縮退を引き起こし、単方向連結リスト（または「不均衡な木」）のような構造を形成する可能性があるため、連結リストと同じ最悪の場合の複雑度になります。^{[ 11 ]}^{[ 9 ]}^{: 299-302}

二分探索木は、集合、多重集合、連想配列などの抽象データ構造の構築に使用される基本的なデータ構造でもあります。

業務

検索中

二分探索木で特定のキーを検索する処理は、再帰的または反復的にプログラムすることができます。

検索はルートノードの調査から始まります。ツリーが $nil$ の場合、検索対象のキーはツリー内に存在しません。それ以外の場合、キーがルートのキーと等しい場合は、検索は成功し、ノードが返されます。キーがルートのキーより小さい場合は、左サブツリーの調査に進みます。同様に、キーがルートのキーより大きい場合は、右サブツリーの調査に進みます。このプロセスは、キーが見つかるか、残りのサブツリーが空になるまで繰り返されます。 ${\text{nil}}$ 検索したキーが見つからない場合 ${\text{nil}}$ 部分木に到達した場合、そのキーは木の中に存在しない。^{[ 10 ]}^{： 290-291}

再帰的検索

以下の擬似コードは、再帰によってBST探索手順を実装する。^{[ 10 ]}^{: 290}

再帰的な手順は、 ${\text{nil}}$ または ${\text{key}}$ 捜索対象に遭遇する。

反復探索

再帰的な検索はwhileループに「展開」できる。ほとんどのマシンでは、反復的なバージョンの方が効率的であることがわかっている。^{[ 10 ]}^{： 291}

検索は葉ノードまで進む可能性があるため、BST検索の実行時間計算量は $O(h)$ どこ $h$ は木の高さです。ただし、BST検索の最悪のケースは $O(n)$ どこ $n$ BST のノードの総数は、不均衡な BST がリンクリストに退化する可能性があるためです。ただし、BST が高さ的に均衡している場合、高さは $O(\log n)$ [ ¹⁰^]^:²⁹⁰

後継者と前任者

特定の操作では、ノードが与えられた場合 ${\text{x}}$ 後継者または前任者を見つける ${\text{x}}$ が重要です。BST のすべてのキーが互いに異なると仮定すると、ノードの後継ノードは ${\text{x}}$ BSTでは、最小のキーを持つノードは、 ${\text{x}}$ のキー。一方、ノードの先行ノードは ${\text{x}}$ BSTでは、キーが小さいノードは ${\text{x}}$ のキー。以下の擬似コードは、ノードの後継ノードと前継ノードを見つけます。 ${\text{x}}$ BSTにおいて。^{[ 12 ]}^{[ 13 ]}^{[ 10 ]}^{： 292-293}

二分探索木（BST）において、キーが最大値または最小値であるノードを見つけるといった操作は、ノードの後継ノードや先行ノードを決定するなどの特定の操作において重要である。以下に、これらの操作の擬似コードを示す。^{[ 10 ]}^{： 291-292}

挿入

挿入や削除などの操作によって、BST表現は動的に変化します。BSTの特性が維持されるようにデータ構造を変更する必要があります。新しいノードはBSTの葉ノードとして挿入されます。 ^{[ 10 ]}^{: 294–295}以下は挿入操作の反復実装です。^{[ 10 ]}^{: 294}

この手順では「末尾ポインタ」が保持されます。 ${\text{y}}$ 親として ${\text{x}}$ 2行目の初期化後、 4～11行目のwhileループによってポインタが更新されます。 ${\text{y}}$ は ${\text{nil}}$ 、BSTは空なので、 ${\text{z}}$ 二分探索木のルートノードとして挿入される ${\text{T}}$ もしそうでないなら ${\text{nil}}$ 挿入は、キーをキーと比較することによって行われます。 ${\text{y}}$ 15～19行目にノードを挿入する。^{[ 10 ]}^{： 295}

削除

ノードの削除、例えば ${\text{Z}}$ 二分探索木から ${\text{BST}}$ 3つの事例がある：^{[ 10 ]}^{： 295-297}

もし ${\text{Z}}$ はリーフノードであり、 ${\text{NIL}}$ (a)に示すように。
もし ${\text{Z}}$ 子ノードは 1 つだけであり、 ${\text{Z}}$ 親ノードを変更することで昇格する ${\text{Z}}$ 子ノードを指し示すため、結果として ${\text{Z}}$ ツリー内でのの位置は、（b）と（c）に示されている。
もし ${\text{Z}}$ ${\text{Z}}$ 左と右の子供の両方を持ち、 ${\text{Z}}$ ${\text{Z}}$ 、言う ${\text{Y}}$ ${\text{Y}}$ 、移動させる ${\text{Z}}$ ${\text{Z}}$ 以下の2つのケースに従うことで、
1. もし ${\text{Y}}$ は ${\text{Z}}$ (d)に示すように、の右の子、 ${\text{Y}}$ 移動させる ${\text{Z}}$ そして ${\text{Y}}$ 右の子供は変化なし。
2. もし ${\text{Y}}$ 中にある ${\text{Z}}$ の右サブツリーですが、 ${\text{Z}}$ (e)に示すように、の右の子、 ${\text{Y}}$ まず、自身の右の子に置き換えられ、次に ${\text{Z}}$ ツリー内での位置。
あるいは、順序通りの先行要素を使用することもできます。

以下の擬似コードは、二分探索木における削除操作を実装したものである。^{[ 10 ]}^{： 296-298}

の ${\text{BST削除}}$ この手順は、上記の 3 つの特殊ケースを処理します。2 ～ 3 行目はケース 1 を、4 ～ 5 行目はケース 2 を、6 ～ 16 行目はケース 3 を処理します。ヘルパー関数 ${\text{シフトノード}}$ ノードを置き換える目的で削除アルゴリズム内で使用される ${\text{u}}$ と ${\text{v}}$ 二分探索木において ${\text{BST}}$ ^{[ 10 ]}^{: 298}この手順では、削除（および置換）を処理します。 ${\text{u}}$ から ${\text{BST}}$ 。

トラバーサル

BSTは、中順、前順、後順の3つの基本的なアルゴリズムで走査できます。^[¹⁰^]^:²⁸⁷

順序通りのツリーウォーク：左サブツリーのノードが最初に訪問され、次にルートノード、そして右サブツリーが訪問されます。このような走査では、キーシーケンスの非減少順にすべてのノードが訪問されます。
先行順ツリーウォーク：ルートノードが最初に訪問され、次に左サブツリーと右サブツリーが訪問されます。
後順木探索：左部分木のノードが最初に訪問され、次に右部分木、最後にルートが訪問されます。

以下に、ツリーウォークの再帰的な実装を示す。^{[ 10 ]}^{： 287-289}

バランスのとれた二分探索木

再バランスを行わないと、二分探索木への挿入や削除によって退化が生じ、高さが $n$ 木の（ $n$ はツリー内のアイテム数）であるため、検索パフォーマンスは線形検索と同程度に低下します。^{[ 14 ]}検索ツリーのバランスを保ち、高さを制限します。 $O(\log n)$ これは、二分探索木の有用性の鍵となる要素である。これは、木の更新操作中に、木の高さを二分対数複雑度に維持するように設計された「自己平衡」メカニズムによって実現できる。^{[ 7 ]}^{[ 15 ]}^{： 50}

高さバランスの取れた木々

左部分木と右部分木の高さが一定の係数で関連付けられることが保証されている場合、その木は高さバランスが取れていると言えます。この特性はAVL木で導入され、赤黒木で引き継がれました。^{[ 15 ]}^{: 50-51}ルートから変更された葉ノードまでのパス上のすべてのノードの高さは、木への挿入および削除操作のたびに監視され、必要に応じて修正される必要があります。^{[ 15 ]}^{: 52}

重量バランスの取れた木

重みバランスの取れた木では、バランスの取れた木の基準は部分木の葉の数です。左部分木と右部分木の重みの差は最大で $1$ [ ¹⁶^]^[¹⁵^]^:^{61しかし、その差}^は比率によって制限される $\alpha$ 重みの強いバランス条件 $1$ 維持できない $O(\log n)$ 挿入および削除操作中の再バランス処理。 $\alpha$ -重みバランス木は、各左サブツリーと右サブツリーがそれぞれ少なくとも $\alpha$ サブツリーの総重量の。^{[ 15 ]}^{： 62}

種類

自己平衡二分探索木には、T木^{[ 17 ]} 、treap ^{[ 18 ]} 、赤黒木^{[ 19 ]} 、B木^{[ 20 ]} 、2-3木^{[ 21} ] 、およびSplay木^[²²^]^などがある。

アプリケーションの例

選別

二分探索木は、すべての要素が一度に挿入され、木が順序通りに走査されるツリーソートなどのソートアルゴリズムで使用されます。 ^{[ 23 ]} BSTはクイックソートでも使用されます。^{[ 24 ]}

優先キュー操作

優先度キューの実装には二分探索木が使用され、ノードのキーが優先度として使用されます。キューへの新しい要素の追加は通常のBST挿入操作に従いますが、削除操作は優先度キューの種類によって異なります。^{[ 25 ]}

昇順優先度キューの場合、最も優先度の低い要素の削除は、二分探索木を左方向に走査することによって行われます。
優先度が降順のキューの場合、最も優先度の高い要素の削除は、二分探索木を右方向に走査することによって行われます。

参考文献

↑ Pitassi, Toniann (2015). "CSC263: Balanced BSTs, AVL tree" (PDF) .トロント大学、コンピュータサイエンス学部。p. 6. 2019年2月14日のオリジナルからアーカイブ(PDF) 。 2022年5月19日取得。
↑マイヤーズ、アンドリュー。「CS 312 講義: AVL ツリー」。コーネル大学、コンピュータサイエンス学部。2021年 4 月 27 日のオリジナルからアーカイブ済み。2022年5 月 19 日取得。
↑アデルソン＝ヴェルスキー、ゲオルギー；ランディス、エフゲニー（1962）。「情報整理のためのアルゴリズム」。ソ連科学アカデミー紀要（ロシア語）。146：263–266。Myron J. Ricciによる英語訳は、Soviet Mathematics - Doklady、3:1259–1263、1962年に掲載されている。
1 2 Culberson, J.; Munro, JI (1989 年 1 月 1 日). "長時間の更新下での二分探索木の挙動の説明: モデルとシミュレーション" . The Computer Journal . 32 (1): 68– 69. doi : 10.1093/comjnl/32.1.68 .
↑ Culberson, J.; Munro, JI (1986年7月28日). "Analysis of the standard deletion algorithms in exact fit domain binary search trees" . Algorithmica . 5 ( 1–4 ). Springer Publishing , University of Waterloo : 297. doi : 10.1007/BF01840390 . S2CID 971813 .
↑ PF Windley (1960 年 1 月 1 日). "ツリー、フォレスト、および再配置" . The Computer Journal . 3 (2): 84. doi : 10.1093/comjnl/3.2.84 .
1 2クヌース、ドナルド( 1998)。「セクション 6.2.3: バランスのとれた木」。コンピュータプログラミングの技法(PDF)。第3 巻 (第 2版)。アディソン・ウェスリー。pp. 458–481。ISBN 978-02018968552022年10月9日にオリジナルからアーカイブされた（PDF）。
↑ Paul E. Black、「赤黒木」、アルゴリズムとデータ構造の辞典[オンライン]、Paul E. Black編、2019年11月12日。（2022年5月19日アクセス）出典： https://www.nist.gov/dads/HTML/redblack.html
1 2 Thareja, Reema (2018年10月13日). 「ハッシュと衝突」.データ構造 C言語版(第2版).オックスフォード大学出版局. ISBN 9780198099307。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 コーメン、トーマスH.チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2001)。アルゴリズム入門(第 2版)。MIT を押します。ISBN 0-262-03293-7。
↑ RA Frost; MM Peterson (1982年2月1日) 「二分探索木に関する短いメモ」 The Computer Journal . 25 (1). Oxford University Press : 158. doi : 10.1093/comjnl/25.1.158 .
↑ Junzhou Huang. "アルゴリズムの設計と分析" (PDF) .テキサス大学アーリントン校. p. 12. 2021年4月13日のオリジナルからアーカイブ(PDF) . 2021年5月17日取得.
↑ Ray, Ray. "Binary Search Tree" . Loyola Marymount University , Department of Computer Science . 2022年5月17日取得。
↑ Thornton, Alex (2021). "ICS 46: 二分探索木" .カリフォルニア大学アーバイン校. 2021年7月4日のオリジナルからアーカイブ済み. 2021年10月21日取得.
1 2 3 4 5 Brass, Peter (2011年1月). Advanced Data Structure . Cambridge University Press . doi : 10.1017/CBO9780511800191 . ISBN 9780511800191。
↑ Blum, Norbert; Mehlhorn, Kurt (1978). "On the Average Number of Rebalancing Operations in Weight-Balanced Trees" (PDF) . Theoretical Computer Science . 11 (3): 303– 320. doi : 10.1016/0304-3975(80)90018-3 . 2022年10月9日にオリジナルからアーカイブされた(PDF) 。
↑リーマン、トービン J.、キャリー、マイケル J. (1986年8月25日～28日)。メインメモリデータベース管理システムのインデックス構造に関する研究。第12回超大規模データベース国際会議 (VLDB 1986)。京都。ISBN 0-934613-18-4。
↑ Aragon, Cecilia R.; Seidel, Raimund (1989)、「ランダム化探索木」(PDF)、第30回コンピュータサイエンス基礎に関する年次シンポジウム、ワシントンDC：IEEEコンピュータソサエティプレス、pp. 540–545、doi：10.1109/SFCS.1989.63531、ISBN 0-8186-1982-12022年10月9日にオリジナルからアーカイブされた（PDF）。
↑Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). 「赤黒木」.アルゴリズム入門（第2 版）. MIT Press. pp. 273 –301. ISBN 978-0-262-03293-3。
↑ Comer, Douglas (1979年6月)、「ユビキタスBツリー」、Computing Surveys、11 (2): 123–137、doi : 10.1145/356770.356776、ISSN 0360-0300、S2CID 101673
↑クヌース、ドナルド・E. (1998). "6.2.4".コンピュータプログラミングの技法第3巻(第2版). アディソン・ウェスリー. ISBN 9780201896855セクション 6.2.3 の最後に定義されている 2〜3 ツリーは、次数 3 の B ツリーと同等です。
↑ Sleator, Daniel D. ; Tarjan, Robert E. (1985). "Self-Adjusting Binary Search Trees" (PDF) . Journal of the ACM . 32 (3): 652– 686. doi : 10.1145/3828.3835 . S2CID 1165848 .
↑ Narayanan, Arvind (2019). "COS226: 二分探索木" .プリンストン大学工学部応用科学科. 2021年3月22日のオリジナルからアーカイブ済み. 2021年10月21日取得– cs.princeton.edu経由。
↑ Xiong, Li. 「二分探索木とクイックソートの関連性」。エモリー大学オックスフォード・カレッジ、数学・コンピュータ科学科。2021年2月26日時点のオリジナルよりアーカイブ。 2022年6月4日取得。
↑ Myers, Andrew. "CS 2112 講義および演習ノート: 優先度付きキューとヒープ" .コーネル大学、コンピュータサイエンス学部. 2021 年 10 月 21 日時点のオリジナルからアーカイブ済み. 2021 年10 月 21 日取得.

さらに読む

この記事は、ポール・E・ブラック著「二分探索木」、『アルゴリズムとデータ構造の辞典』、NIST のパブリックドメイン資料を組み込んでいます。
Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "12: 二分探索木、15.5: 最適二分探索木".アルゴリズム入門（第2 版）. MIT Press . pp. 253–272 , 356–363 . ISBN 0-262-03293-7。
Jarc, Duane J. (2005年12月3日). "二分木走査" .インタラクティブデータ構造可視化.メリーランド大学. 2014年2月27日のオリジナルからアーカイブ済み. 2006年4月30日取得.
クヌース、ドナルド（1997）。「6.2.2：二分木探索」。『コンピュータプログラミングの技法』第 3巻：「ソートと探索」（第3 版）。アディソン・ウェスリー。426 ～ 458ページ。ISBN 0-201-89685-0。
Long, Sean. 「二分探索木」( PPT )。データ構造とアルゴリズムの可視化 - PowerPoint スライドに基づくアプローチ。SUNY Oneonta。
Parlante, Nick (2001). "Binary Trees" . CS Education Library . Stanford University . 2022年1月30日時点のオリジナルよりアーカイブ。

外部リンク

Ben Pfaff:二分探索木と平衡木入門。（PDF; 1675 kB）2004年。
二分探索木の可視化

[1] Pitassi, Toniann (2015). "CSC263: Balanced BSTs, AVL tree" (PDF) .トロント大学、コンピュータサイエンス学部。p. 6. 2019年2月14日のオリジナルからアーカイブ(PDF) 。 2022年5月19日取得。

[2] マイヤーズ、アンドリュー。「CS 312 講義: AVL ツリー」。コーネル大学、コンピュータサイエンス学部。2021年 4 月 27 日のオリジナルからアーカイブ済み。2022年5 月 19 日取得。

[3] アデルソン＝ヴェルスキー、ゲオルギー；ランディス、エフゲニー（1962）。「情報整理のためのアルゴリズム」。ソ連科学アカデミー紀要（ロシア語）。146：263–266。Myron J. Ricciによる英語訳は、Soviet Mathematics - Doklady、3:1259–1263、1962年に掲載されている。

[computer_journal89-4] 1 2 Culberson, J.; Munro, JI (1989 年 1 月 1 日). "長時間の更新下での二分探索木の挙動の説明: モデルとシミュレーション" . The Computer Journal . 32 (1): 68– 69. doi : 10.1093/comjnl/32.1.68 .

[5] Culberson, J.; Munro, JI (1986年7月28日). "Analysis of the standard deletion algorithms in exact fit domain binary search trees" . Algorithmica . 5 ( 1–4 ). Springer Publishing , University of Waterloo : 297. doi : 10.1007/BF01840390 . S2CID 971813 .

[windley60-6] PF Windley (1960 年 1 月 1 日). "ツリー、フォレスト、および再配置" . The Computer Journal . 3 (2): 84. doi : 10.1093/comjnl/3.2.84 .

[Knuth98-7] 1 2クヌース、ドナルド( 1998)。「セクション 6.2.3: バランスのとれた木」。コンピュータプログラミングの技法(PDF)。第3 巻 (第 2版)。アディソン・ウェスリー。pp. 458–481。ISBN 978-02018968552022年10月9日にオリジナルからアーカイブされた（PDF）。

[8] Paul E. Black、「赤黒木」、アルゴリズムとデータ構造の辞典[オンライン]、Paul E. Black編、2019年11月12日。（2022年5月19日アクセス）出典： https://www.nist.gov/dads/HTML/redblack.html

[reema18-9] 1 2 Thareja, Reema (2018年10月13日). 「ハッシュと衝突」.データ構造 C言語版(第2版).オックスフォード大学出版局. ISBN 9780198099307。

[algo_cormen-10] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 コーメン、トーマスH.チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2001)。アルゴリズム入門(第 2版)。MIT を押します。ISBN 0-262-03293-7。

[11] RA Frost; MM Peterson (1982年2月1日) 「二分探索木に関する短いメモ」 The Computer Journal . 25 (1). Oxford University Press : 158. doi : 10.1093/comjnl/25.1.158 .

[12] Junzhou Huang. "アルゴリズムの設計と分析" (PDF) .テキサス大学アーリントン校. p. 12. 2021年4月13日のオリジナルからアーカイブ(PDF) . 2021年5月17日取得.

[13] Ray, Ray. "Binary Search Tree" . Loyola Marymount University , Department of Computer Science . 2022年5月17日取得。

[14] Thornton, Alex (2021). "ICS 46: 二分探索木" .カリフォルニア大学アーバイン校. 2021年7月4日のオリジナルからアーカイブ済み. 2021年10月21日取得.

[peter11-15] 1 2 3 4 5 Brass, Peter (2011年1月). Advanced Data Structure . Cambridge University Press . doi : 10.1017/CBO9780511800191 . ISBN 9780511800191。

[16] Blum, Norbert; Mehlhorn, Kurt (1978). "On the Average Number of Rebalancing Operations in Weight-Balanced Trees" (PDF) . Theoretical Computer Science . 11 (3): 303– 320. doi : 10.1016/0304-3975(80)90018-3 . 2022年10月9日にオリジナルからアーカイブされた(PDF) 。

[17] リーマン、トービン J.、キャリー、マイケル J. (1986年8月25日～28日)。メインメモリデータベース管理システムのインデックス構造に関する研究。第12回超大規模データベース国際会議 (VLDB 1986)。京都。ISBN 0-934613-18-4。

[18] Aragon, Cecilia R.; Seidel, Raimund (1989)、「ランダム化探索木」(PDF)、第30回コンピュータサイエンス基礎に関する年次シンポジウム、ワシントンDC：IEEEコンピュータソサエティプレス、pp. 540–545、doi：10.1109/SFCS.1989.63531、ISBN 0-8186-1982-12022年10月9日にオリジナルからアーカイブされた（PDF）。

[Cormen2001-19] Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). 「赤黒木」.アルゴリズム入門（第2 版）. MIT Press. pp. 273 –301. ISBN 978-0-262-03293-3。

[20] Comer, Douglas (1979年6月)、「ユビキタスBツリー」、Computing Surveys、11 (2): 123–137、doi : 10.1145/356770.356776、ISSN 0360-0300、S2CID 101673

[21] クヌース、ドナルド・E. (1998). "6.2.4".コンピュータプログラミングの技法第3巻(第2版). アディソン・ウェスリー. ISBN 9780201896855セクション 6.2.3 の最後に定義されている 2〜3 ツリーは、次数 3 の B ツリーと同等です。

[22] Sleator, Daniel D. ; Tarjan, Robert E. (1985). "Self-Adjusting Binary Search Trees" (PDF) . Journal of the ACM . 32 (3): 652– 686. doi : 10.1145/3828.3835 . S2CID 1165848 .

[23] Narayanan, Arvind (2019). "COS226: 二分探索木" .プリンストン大学工学部応用科学科. 2021年3月22日のオリジナルからアーカイブ済み. 2021年10月21日取得– cs.princeton.edu経由。

[24] Xiong, Li. 「二分探索木とクイックソートの関連性」。エモリー大学オックスフォード・カレッジ、数学・コンピュータ科学科。2021年2月26日時点のオリジナルよりアーカイブ。 2022年6月4日取得。

[25] Myers, Andrew. "CS 2112 講義および演習ノート: 優先度付きキューとヒープ" .コーネル大学、コンピュータサイエンス学部. 2021 年 10 月 21 日時点のオリジナルからアーカイブ済み. 2021 年10 月 21 日取得.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[

[ 7 ]

[

[

[

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

16

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21

[

[ 23 ]

[ 24 ]

[ 25 ]