二分探索木

二分探索木
二分探索木
タイプ	木
発明された	1960
発明者	PF ウィンドリー、AD ブース、AJT コリン、TN ヒバード
手術
ビッグ O 記法による時間計算量
手術	平均
検索	O(logn )は、
入れる	O(logn )は、
消去	O(logn )は、
空間の複雑さ
空間	の上）

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

二分探索木は、二分探索による高速なデータ項目の検索、追加、削除を可能にします。BST のノードは、各比較で残りの木の約半分をスキップするように配置されているため、検索のパフォーマンスは二分対数に比例します。BST は、ラベル付きデータの効率的な保存の問題に対処するために 1960 年代に考案され、Conway Berners-LeeとDavid Wheelerによって考案されました。

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

BST の複雑性分析によると、平均して、挿入、削除、検索にはノードの時間がかかります。最悪の場合、単方向リンクリストの複雑性まで低下します: 。任意の挿入と削除によるツリーの高さの際限のない増加に対処するために、 BST の自己バランス型バリアントが導入され、最悪の検索複雑性が 2 進対数の複雑性に制限されます。AVLツリーは、1962 年に Georgy Adelson-VelskyとEvgenii Landisによって発明された最初の自己バランス型 2 進探索ツリーです。 $O(\log n)$ $n$ $O(n)$

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

歴史

二分探索木アルゴリズムは、PF Windley、Andrew Donald Booth、Andrew Colin、Thomas N. Hibbardを含む複数の研究者によって独立して発見されました。^[1]^[2]このアルゴリズムは、 1960年に磁気テープにラベル付きデータを格納するために使用したConway Berners-LeeとDavid Wheelerによるものとされています。 ^[3]最も初期かつ人気のある二分探索木アルゴリズムの1つは、Hibbardのアルゴリズムです。^[1]

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

AVL木は、情報の効率的な整理のために、1962年にGeorgy Adelson-VelskyとEvgenii Landisによって発明されました。 ^[6]^[7]これは、発明された最初の自己バランス型二分探索木でした。^[8]

概要

二分探索木は、ノードが厳密な全順序で並べられた根付き二分木であり、特定のノードAより大きいキーを持つノードはそのノードAの右側のサブツリーに格納され、 A以下のキーを持つノードはAの左側のサブツリーに格納され、二分探索特性を満たします。^[9]^{: 298}^[10]^{: 287}

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

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

オペレーション

検索中

バイナリ検索ツリーで特定のキーを検索する操作は、再帰的または反復的にプログラムできます。

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

再帰検索

次の疑似コードは、再帰によるBST検索手順を実装しています。^[10]^{: 290}

再帰手順は、検索対象のまたはが見つかるまで続行されます。 ${\text{nil}}$ ${\text{キー}}$

反復検索

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

探索は何らかの葉ノードまで進む可能性があるため、BST 探索の実行時間計算量はとなる。ここでは木の高さである。しかし、BST 探索の最悪のケースはとなる。ここではBST 内のノードの総数である。これは、不均衡な BST がリンクリストに退化する可能性があるためである。しかし、BST が高さバランスが取れている場合、高さはとなる。^[10]^{: 290} $O(h)$ $h$ $O(n)$ $n$ $O(\log n)$

後継者と先代

特定の操作では、ノードが与えられた場合、の後続ノードまたは先行ノードを見つけることが極めて重要です。BST のすべてのキーが異なると仮定すると、BST 内のノードの後続ノードは、のキーよりも大きい最小のキーを持つノードです。一方、BST 内のノードの前続ノードは、のキーよりも小さい最大のキーを持つノードです。次の擬似コードは、BST 内のノードの後続ノードと先行ノードを見つけます。 ^[12]^[13]^[10]^{: 292–293} ${\text{x}}$ ${\text{x}}$ ${\text{x}}$ ${\text{x}}$ ${\text{x}}$ ${\text{x}}$ ${\text{x}}$

BST内のキーが最大値または最小値であるノードを見つけるなどの操作は、ノードの後続ノードと先行ノードを決定するなどの特定の操作において重要です。以下は、その操作の擬似コードです。^[10]^{: 291–292}

挿入

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

この手続きは、の親として「末尾のポインタ」を維持します。 2 行目の初期化後、 4 行目から 11 行目のwhileループによってポインタが更新されます。がの場合、BST は空なので、がバイナリ検索木のルートノードとして挿入されます。がでない場合は、のキーと 15 行目から 19 行目のキーを比較して挿入が進められ、それに応じてノードが挿入されます。^[10]^{: 295} ${\text{y}}$ ${\text{x}}$ ${\text{y}}$ ${\text{nil}}$ ${\text{z}}$ ${\text{T}}$ ${\text{nil}}$ ${\text{y}}$

削除

二分探索木からノード（例えば）を削除する場合、3つのケースがある：^[10]^{: 295-297} ${\text{Z}}$ ${\text{BST}}$

がリーフノードである場合、の親ノードはに置き換えられ、その結果、 (a) に示すようにはから削除されます。 ${\text{Z}}$ ${\text{Z}}$ ${\text{NIL}}$ ${\text{Z}}$ ${\text{BST}}$
に子が 1 つしかない場合、の親ノードを子ノードを指すように変更することでの子ノードが昇格され、結果的に(b) および (c) に示すように、ツリー内での位置を占めるようになります。 ${\text{Z}}$ ${\text{Z}}$ ${\text{Z}}$ ${\text{Z}}$
に左と右の両方の子がある場合、の後継、たとえばは、次の 2 つのケースに従って置き換えられます。 ${\text{Z}}$ ${\text{Z}}$ ${\text{Z}}$ ${\text{Z}}$ ${\text{Y}}$ ${\text{Y}}$ ${\text{Z}}$ ${\text{Z}}$
1. がの右の子である場合、(d) に示すように、はを置き換え、の右の子は変更されません。 ${\text{Y}}$ ${\text{Z}}$ ${\text{Y}}$ ${\text{Z}}$ ${\text{Y}}$
2. (e) に示すように、がの右サブツリー内にあるがの右の子ではない場合は、まずが自身の右の子に置き換えられ、次にがツリー内での位置を置き換えます。 ${\text{Y}}$ ${\text{Z}}$ ${\text{Z}}$ ${\text{Y}}$ ${\text{Z}}$

次の疑似コードは二分探索木における削除操作を実装している。^[10]^{: 296-298}

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

トラバーサル

BSTは、インオーダー、プレオーダー、ポストオーダーの3つの基本アルゴリズムで走査することができる。^[10]^{: 287}

順方向ツリーウォーク: 最初に左のサブツリーのノードが訪問され、次にルートノードと右のサブツリーが訪問されます。このようなトラバーサルでは、キーの順序が減少せずにすべてのノードを訪問します。
事前順序ツリーウォーク: ルートノードが最初に訪問され、次に左と右のサブツリーが訪問されます。
後順序ツリーウォーク: 最初に左のサブツリーのノードが訪問され、次に右のサブツリー、最後にルートが訪問されます。

以下はツリーウォークの再帰的な実装である。^[10]^{: 287–289}

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

再バランス調整を行わないと、二分探索木における挿入や削除によって退化が起こり、木の高さが（木内の項目数）になり、検索性能が線形探索の性能まで低下する可能性がある。^[14]探索木のバランスを保ち、高さを一定に保つことが二分探索木の有用性の鍵である。これは、木の高さを二分対数複雑度に維持するように設計された木の更新操作中に「自己バランス調整」メカニズムによって達成できる。^[4]^[15]^{: 50} $n$ $n$ $O(\log n)$

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

ツリーの左サブツリーと右サブツリーの高さが定数倍で関係していることが保証されている場合、ツリーは高さバランスが取れている。この特性はAVL ツリーによって導入され、赤黒ツリーに引き継がれた。^[15]^{: 50–51}ルートから変更されたリーフノードまでのパス上にあるすべてのノードの高さは、ツリーへの挿入および削除操作ごとに観察され、場合によっては修正される必要がある。^[15]^{: 52}

重量バランスの取れた木

重みバランスのとれた木では、バランスのとれた木の基準は、サブツリーの葉の数です。左と右のサブツリーの重みは最大でだけ異なります。^[16]^[15]^{: 61}しかし、挿入および削除操作中の再バランス作業ではの強いバランス条件を維持できないため、この差は重みの比率によって制限されます。 -重みバランスのとれた木は、左右のサブツリーのそれぞれがサブツリーの総重みの少なくともの割合を持つバランス条件の完全なファミリーを提供します。 ^[15]^{: 62} $1$ $\alpha$ $1$ $O(\log n)$ $\alpha$ $\alpha$

種類

自己バランス型二分探索木には、T木^[17] 、treap ^{[18] 、} 赤黒木^[19] 、B木^[20] 、2-3木^[21]、スプレイ木^[22]などがある。

アプリケーションの例

選別

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

優先キュー操作

二分探索木は、ノードのキーを優先順位として利用して、優先キューを実装するために使用される。キューに新しい要素を追加することは通常のBST挿入操作に従うが、削除操作は優先キューの種類に依存する：^[25]

昇順の優先度キューの場合、優先度が最も低い要素の削除は、BST の左方向のトラバーサルによって行われます。
降順優先度キューの場合、最も優先度の高い要素の削除は、BST の右方向のトラバーサルによって行われます。

参照

参考文献

^ ab Culberson, J.; Munro, JI (1989年1月1日). 「長時間更新下における二分探索木の動作の説明: モデルとシミュレーション」.コンピュータジャーナル. 32 (1): 68–69. doi : 10.1093/comjnl/32.1.68 .
^ Culberson, J.; Munro, JI (1986 年 7 月 28 日). 「完全適合ドメインバイナリ検索ツリーにおける標準削除アルゴリズムの分析」. Algorithmica . 5 (1–4). Springer Publishing , University of Waterloo : 297. doi :10.1007/BF01840390. S2CID 971813.
^ PF Windley (1960 年 1 月 1 日). 「木、森、そして再配置」.コンピュータジャーナル. 3 (2): 84. doi : 10.1093/comjnl/3.2.84 .
^ ab Knuth, Donald (1998). 「セクション 6.2.3: バランスツリー」. The Art of Computer Programming (PDF) . 第 3 巻 (第 2 版). Addison-Wesley . pp. 458–481. ISBN 978-02018968552022年10月9日にオリジナルからアーカイブ（PDF）されました。
^ Paul E. Black、「赤黒木」、Dictionary of Algorithms and Data Structures [online]、Paul E. Black 編、2019 年 11 月 12 日。(2022 年 5 月 19 日にアクセス) https://www.nist.gov/dads/HTML/redblack.html より
^ マイヤーズ、アンドリュー。「CS 312 講義: AVL ツリー」。コーネル大学、コンピューターサイエンス学部。2021年4月27日時点のオリジナルよりアーカイブ。2022年5月19日閲覧。
^ Adelson-Velsky, Georgy; Landis, Evgenii (1962). 「情報の組織化のためのアルゴリズム」。USSR科学アカデミー紀要（ロシア語）。146 : 263–266。Myron J. Ricciによる英訳、Soviet Mathematics - Doklady、3:1259–1263、1962年。
^ Pitassi, Toniann (2015). 「CSC263: Balanced BSTs, AVL tree」（PDF）。トロント大学、コンピュータサイエンス学部。p. 6。2019年2月14日時点のオリジナルよりアーカイブ（PDF）。 2022年5月19日閲覧。
^ ab Thareja, Reema (2018年10月13日). 「ハッシュと衝突」. Cを使用したデータ構造（第2版）. Oxford University Press . ISBN 9780198099307。
^ abcdefghijklmno コーメン、トーマス H. ;チャールズ・E・ライザーソン;ロナルド・L・リベスト;スタイン、クリフォード(2001)。アルゴリズム入門 (第 2 版)。MIT を押します。ISBN 0-262-03293-7。
^ RA Frost、MM Peterson (1982 年 2 月 1 日)。 「バイナリ検索木に関する短いメモ」。コンピュータジャーナル。25 (1)。オックスフォード大学出版局: 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」ロヨラ・メリーマウント大学、コンピューターサイエンス学部。 2022年5月17日閲覧。
^ Thornton, Alex (2021). 「ICS 46: Binary Search Trees」.カリフォルニア大学アーバイン校. 2021年7月4日時点のオリジナルよりアーカイブ。 2021年10月21日閲覧。
^ abcde Brass, Peter (2011年1月). 高度なデータ構造.ケンブリッジ大学出版局. doi :10.1017/CBO9780511800191. ISBN 9780511800191。
^ Blum, Norbert; Mehlhorn, Kurt (1978). 「重みバランスのとれた木における再バランス操作の平均回数について」(PDF) .理論計算機科学. 11 (3): 303–320. doi :10.1016/0304-3975(80)90018-3. 2022-10-09 にオリジナルからアーカイブ(PDF)されました。
^ Lehman, Tobin J.; Carey, Michael 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-1、 2022年10月9日にオリジナルからアーカイブ（PDF）
^ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001)。「Red–Black Trees」。アルゴリズム入門(第 2 版)。MIT プレス。pp. 273–301。ISBN 978-0-262-03293-3。
^ Comer, Douglas (1979 年 6 月)、「The Ubiquitous B-Tree」、Computing Surveys、11 (2): 123–137、doi : 10.1145/356770.356776、ISSN 0360-0300、S2CID 101673
^ Knuth, Donald M (1998). 「6.2.4」.コンピュータプログラミングの芸術. 第3巻 (第2版). Addison Wesley. ISBN 9780201896855セクション6.2.3の終わりに定義された2-3ツリーは、順序3のBツリーと同等です。
^ Sleator, Daniel D. ; Tarjan, Robert E. (1985). 「自己調整型バイナリ検索木」(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日閲覧。
^ マイヤーズ、アンドリュー。「CS 2112 講義および暗唱ノート: 優先キューとヒープ」。コーネル大学、コンピューターサイエンス学部。2021年10月21日時点のオリジナルよりアーカイブ。2021年10月21日閲覧。

さらに読む

この記事には、 Paul E. Blackのパブリックドメイン資料が組み込まれています。「Binary Search Tree」。アルゴリズムとデータ構造の辞書。NIST 。
Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001)。「12: バイナリサーチツリー、15.5: 最適バイナリサーチツリー」。アルゴリズム入門 (第 2 版)。MITプレス。pp . 253–272、356–363。ISBN 0-262-03293-7。
Jarc, Duane J. (2005 年 12 月 3 日)。「バイナリツリートラバーサル」。インタラクティブなデータ構造の視覚化。メリーランド大学。2014 年 2 月 27 日時点のオリジナルからアーカイブ。2006年4 月 30 日閲覧。
Knuth, Donald (1997)。「6.2.2: バイナリツリー検索」。The Art of Computer Programming。第 3 巻:「ソートと検索」(第 3 版)。Addison-Wesley。pp. 426–458。ISBN 0-201-89685-0。
Long, Sean。「バイナリ検索ツリー」( PPT )。データ構造とアルゴリズムの視覚化 - PowerPoint スライドベースのアプローチ。SUNY Oneonta。
Parlante, Nick (2001). 「バイナリツリー」. CS教育ライブラリ.スタンフォード大学. 2022-01-30時点のオリジナルよりアーカイブ。

外部リンク

Ben Pfaff: バイナリ検索木とバランス木の紹介。(PDF; 1675 kB) 2004 年。
バイナリツリービジュアライザー (さまざまな BT ベースのデータ構造の JavaScript アニメーション)

[computer_journal89-1] Culberson, J.; Munro, JI (1989年1月1日). 「長時間更新下における二分探索木の動作の説明: モデルとシミュレーション」.コンピュータジャーナル. 32 (1): 68–69. doi : 10.1093/comjnl/32.1.68 .

[2] Culberson, J.; Munro, JI (1986 年 7 月 28 日). 「完全適合ドメインバイナリ検索ツリーにおける標準削除アルゴリズムの分析」. Algorithmica . 5 (1–4). Springer Publishing , University of Waterloo : 297. doi :10.1007/BF01840390. S2CID 971813.

[windley60-3] PF Windley (1960 年 1 月 1 日). 「木、森、そして再配置」.コンピュータジャーナル. 3 (2): 84. doi : 10.1093/comjnl/3.2.84 .

[Knuth98-4] Knuth, Donald (1998). 「セクション 6.2.3: バランスツリー」. The Art of Computer Programming (PDF) . 第 3 巻 (第 2 版). Addison-Wesley . pp. 458–481. ISBN 978-02018968552022年10月9日にオリジナルからアーカイブ（PDF）されました。

[5] Paul E. Black、「赤黒木」、Dictionary of Algorithms and Data Structures [online]、Paul E. Black 編、2019 年 11 月 12 日。(2022 年 5 月 19 日にアクセス) https://www.nist.gov/dads/HTML/redblack.html より

[6] マイヤーズ、アンドリュー。「CS 312 講義: AVL ツリー」。コーネル大学、コンピューターサイエンス学部。2021年4月27日時点のオリジナルよりアーカイブ。2022年5月19日閲覧。

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

[8] Pitassi, Toniann (2015). 「CSC263: Balanced BSTs, AVL tree」（PDF）。トロント大学、コンピュータサイエンス学部。p. 6。2019年2月14日時点のオリジナルよりアーカイブ（PDF）。 2022年5月19日閲覧。

[reema18-9] Thareja, Reema (2018年10月13日). 「ハッシュと衝突」. Cを使用したデータ構造（第2版）. Oxford University Press . ISBN 9780198099307。

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

[11] ^ RA Frost、MM Peterson (1982 年 2 月 1 日)。 「バイナリ検索木に関する短いメモ」。コンピュータジャーナル。25 (1)。オックスフォード大学出版局: 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」ロヨラ・メリーマウント大学、コンピューターサイエンス学部。 2022年5月17日閲覧。

[14] Thornton, Alex (2021). 「ICS 46: Binary Search Trees」.カリフォルニア大学アーバイン校. 2021年7月4日時点のオリジナルよりアーカイブ。 2021年10月21日閲覧。

[peter11-15] Brass, Peter (2011年1月). 高度なデータ構造.ケンブリッジ大学出版局. doi :10.1017/CBO9780511800191. ISBN 9780511800191。

[16] Blum, Norbert; Mehlhorn, Kurt (1978). 「重みバランスのとれた木における再バランス操作の平均回数について」(PDF) .理論計算機科学. 11 (3): 303–320. doi :10.1016/0304-3975(80)90018-3. 2022-10-09 にオリジナルからアーカイブ(PDF)されました。

[17] Lehman, Tobin J.; Carey, Michael 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-1、 2022年10月9日にオリジナルからアーカイブ（PDF）

[Cormen2001-19] Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001)。「Red–Black Trees」。アルゴリズム入門(第 2 版)。MIT プレス。pp. 273–301。ISBN 978-0-262-03293-3。

[20] Comer, Douglas (1979 年 6 月)、「The Ubiquitous B-Tree」、Computing Surveys、11 (2): 123–137、doi : 10.1145/356770.356776、ISSN 0360-0300、S2CID 101673

[21] Knuth, Donald M (1998). 「6.2.4」.コンピュータプログラミングの芸術. 第3巻 (第2版). Addison Wesley. ISBN 9780201896855セクション6.2.3の終わりに定義された2-3ツリーは、順序3のBツリーと同等です。

[22] Sleator, Daniel D. ; Tarjan, Robert E. (1985). 「自己調整型バイナリ検索木」(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] マイヤーズ、アンドリュー。「CS 2112 講義および暗唱ノート: 優先キューとヒープ」。コーネル大学、コンピューターサイエンス学部。2021年10月21日時点のオリジナルよりアーカイブ。2021年10月21日閲覧。