JavaScript
 Computer >> コンピューター >  >> プログラミング >> JavaScript

JavaScriptで学ぶ二分探索木（Binary Search Tree）の基本と操作方法

二分探索木とは

二分探索木は、通常の木構造とは異なる特別な性質を持つデータ構造です。この性質により、データの検索・挿入・削除を効率的に行うことができます。

二分探索木では、各ノードが次のルールに従わなければなりません。

  • ノードの左の子は、必ず親ノードより小さい値を持つ
  • ノードの右の子は、必ず親ノードより大きい値を持つ

JavaScriptで学ぶ二分探索木（Binary Search Tree）の基本と操作方法

この規則が成り立つことで、値を探す際に「目的の値より小さければ左へ、大きければ右へ」と分岐をたどるだけで済み、探索範囲を毎回半分に絞り込めます。そのため、整列された配列に対する二分探索と同様の効率性が得られます。

本記事を含む木構造のセクションでは、主にこの二分探索木を中心に解説を進めていきます。

二分探索木に対する主な操作

JavaScriptで二分探索木を実装する際には、一般的に以下のような操作を定義します。

  • キーの挿入 … 木の中に新しい値を適切な位置に追加する
  • 中間順走査 … 左→根→右の順でノードを訪問する（昇順ソート結果が得られる）
  • 先行順走査 … 根→左→右の順でノードを訪問する
  • 後行順走査 … 左→右→根の順でノードを訪問する
  • 値の検索 … 特定の値が木に存在するかどうかを調べる
  • 最小値の検索 … 木の中で最も小さい値を見つける（常に左端のノード）
  • 最大値の検索 … 木の中で最も大きい値を見つける（常に右端のノード）
  • 葉ノードの削除 … 子を持たないノードを木から取り除く

これらの操作を理解することで、二分探索木の仕組みとその強力さを実感できるでしょう。以降のセクションでは、それぞれの操作をJavaScriptのコードとともに詳しく見ていきます。

  1. C++で二分木を二分探索木（BST）へ変換する方法を解説

    二分木（Binary Tree）とは二分木とは、木構造の各ノードが最大で2つの子ノードを持つことができる特別な木構造です。これらの子ノードは、それぞれ「左の子ノード」と「右の子ノード」と呼ばれます。シンプルな二分木の例は以下の通りです。二分探索木（BST）とは二分探索木（BST）は、以下のルールに従う特別な木構造です。左の子ノードの値は、常に親ノードの値より小さい右の子ノードの値は、常に親ノードの値より大きいすべてのノードが、それぞれ独立して二分探索木の性質を満たす二分探索木（BST）の例は以下の通りです。二分探索木は、検索や最小値・最大値の探索といった操作の計算量を削減するために用いられるデ

  2. C#で二分探索（バイナリサーチ）を実装する方法｜仕組みと計算量を解説

    二分探索とは二分探索（バイナリサーチ）は、ソート済みの配列を対象とした高速な検索アルゴリズムです。探索したい値を配列の中央にある要素と比較し、一致しなかった場合は、その値が存在し得ない側の半分の領域を丸ごと除外します。この操作を残りの半分に対して繰り返すことで、効率よく目的の値を見つけ出します。例えば、下図のような配列から「62」という値を探す場合を考えてみましょう。中央の要素との比較結果から、62が存在するのは右側の領域だけであることが分かるため、左半分は完全に除外され、以降は右半分のみが探索対象となります。二分探索の計算量二分探索における各ケースの計算量は以下の通りです。最悪時間計算量O(