edubun
日本語
English한국어EspañolPortuguêsFrançaisDeutschItalianoРусский日本語
ホーム›プログラミング›データ構造

二分探索木

1,023個のキーのつり合った二分探索木なら、どのキーも最大10回の比較で見つかります。整列済みの入力から作ると、同じキーで1,023回かかることもあります。

形に組みこまれた二分探索

整列済みの配列で二分探索をすると、およそ log₂ n 回の確認でキーが見つかりますが、整列済みの配列に挿入すると値が動きます。ハッシュテーブルは挿入が速いものの、順序を忘れてしまいます。いちばん小さいキーや、40の次のキーをすぐには教えられません。二分探索木（BST）はその両方をめざします。連結リストと同じくノードでできていますが、各ノードは left と right の2つのポインターを持ちます。いちばん上のノードが根で、子を持たないノードは葉です。

探索木にするための決まりは1つです。どのノードでも、左の部分木のキーはすべて小さく、右の部分木のキーはすべて大きい。キーを探すには、根から始めて比べます。等しければ見つかりです。小さければ左へ、大きければ右へ進みます。二分探索がリストの半分を捨てるように、比較のたびに部分木がまるごと除かれます。木 50、30、70、20、40、60、80 で60を探すと、50、次に70、次に60と比べます。比較は3回です。

挿入も同じ道をたどります。必要なポインターが空になるまで左か右へ進み、そこに新しいノードをつなぎます。45を挿入すると、50（左へ）、30（右へ）、40（右へ）と比べ、40には右の子がないので45がその子になります。葉でないノードの削除には、もう1つ考えが必要です。MITの資料では、その項目を順序で次か前のキーと入れかえ、代わりにそちらを削除します。ラボの数え方は、道の途中のノード1つにつき比較1回です。

読み込み中

ドラッグで回転、スクロールまたはピンチで拡大・縮小。

二分探索木です。キーを選んで挿入や探索をしましょう。道が光り、カウンターが比較の回数を示します。はじめの木を「整列済みの入力」に変えると、同じ7個のキーが長い鎖になるのがわかります。

高さがすべて

探索では比較が何回必要になりうるでしょうか。1つの段につき最大1回なので、費用は木の高さ、つまり根から葉までのいちばん長い道にある辺の数で決まります。MITの資料はこれを、木の操作は O(h) 時間で動く、と表しています。木 50、30、70、20、40、60、80 の高さは2なので、どの探索も比較は3回までで済みます。1,023個のノードの完全につり合った木は高さ9で、最大10回です。

しかし形は挿入の順番で決まります。10、20、30、40、50、60、70 を整列した順に挿入すると、どのキーもそれまでのすべてより大きいので、新しいノードはいつも前のノードの右に入ります。木は高さ6の鎖になり、70を探すには7回の比較が必要です。ポインターが余分にある連結リストです。1,023個の整列済みのキーなら、最悪の探索は10回ではなく1,023回の比較になります。

つり合った木は、挿入や削除のたびに自分の形を整え直すことでこれを解決します。最初の方法はAVL木で、1962年にゲオルギー・アデルソン＝ヴェルスキーとエフゲニー・ランディスが考えたものです。MITの第7回講義で扱います。AVL木はどのノードでも2つの部分木の高さの差を1以内に保ち、くずれたときは回転と呼ばれる小さな局所的な操作で直します。これで高さは O(log n) に保たれ、キーがどんな順番で来ても、探索・挿入・削除は O(log n) のままです。

キーの順序はおまけでついてくる

BSTは、あるかないかより多くのことを覚えています。左の部分木、そのノード、右の部分木の順に再帰的に訪ねると、キーが整列した順に出てきます。この中間順の巡回（MITは巡回順序と呼びます）によって、BSTは「いちばん小さいキー」「いちばん大きいキー」「40の次のキー」に答えます。これらはMITのSetインターフェースの順序の操作で、ハッシュテーブルにはすばやくできません。

根と葉根はいちばん上のノード、葉は子を持たないノードです。
BSTの性質どのノードでも、左の部分木のキーは小さく、右の部分木のキーは大きい。
高さ根から葉までのいちばん長い道にある辺の数。探索の比較は最大で高さ + 1 回です。
AVL木つり合ったBST（1962年）。部分木の高さの差は最大1で、回転で直します。
中間順の巡回左、ノード、右の順。キーを整列した順に並べます。
  1. 二分探索木の性質を表しているのはどれですか？
    • どのノードもちょうど2つの子を持つ
    • どのノードでも、左の部分木のキーは小さく、右の部分木のキーは大きい
    • キーは挿入した順に保存される
    • 根はいちばん小さいキーである
  2. 50、30、70、20、40、60、80 から作った木です。60を探すと比較は何回ですか？
  3. 同じ木で、ない値45を探すと比較は何回ですか？
  4. その木に45を挿入します。どこに入りますか？
    • 50の左の子
    • 40の右の子
    • 60の左の子
    • 30の右の子
  5. 木 50、30、70、20、40、60、80 の高さはいくつですか？
  6. 10、20、30、40、50、60、70 をこの順に挿入します。70を探すと比較は何回ですか？
  7. 完全につり合ったBSTに1,023個のノードがあります（高さ9）。探索の比較は最大で何回ですか？
  8. 木 50、30、70、20、40 のキーを、中間順の巡回で訪ねる順に並べましょう。
  9. 最初のつり合った木の方法を考えたのはだれで、いつですか？
    • アデルソン＝ヴェルスキーとランディス、1962年
    • ルーン、1953年
    • バウアーとザメルソン、1957年
    • クヌース、1998年
  10. BSTならすばやく答えられて、ふつうのハッシュテーブルでは答えられない問いはどれですか？
    • 40は保存されているか
    • 40の次のキーは何か
    • バケットはいくつあるか
    • 40 mod 7 はいくつか
ポイント
  • BSTでは、どのノードでも小さいキーは左へ、大きいキーは右へ進みます。
  • 探索と挿入は1本の道をたどります。比較は最大で高さ + 1 回です。
  • 整列済みの入力では鎖になります（キー7個、高さ6）。AVL木（1962年）のようなつり合った木は高さを O(log n) に保ちます。
  • 中間順の巡回はキーを整列した順に並べます。
このコースの出典 (11)
  • MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
  • lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
  • 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
  • 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
  • MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
  • Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
  • ECMAScript 2025 Language Specification (tc39.es/ecma262)
  • 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
  • Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
  • D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
  • "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).

確認日: 2026-10-18