LASSIC Media らしくメディア

2026.10.06 らしくコラム

二分探索木の仕組み|探索・挿入・削除と偏りが出たときの対処

監修・編集責任者:牛尾 昭昌(株式会社LASSIC 執行役員)

エディタ画面に入れ子になったHTMLのdivタグが階段状に並び、木のような階層構造が見えるコードの写真。

この記事の結論

  • 二分探索木は、左に小さい値、右に大きい値を置いて並べる木の形のデータ構造です。
  • 速さは木の高さで決まり、順番どおりのデータをそのまま入れると一列に偏って遅くなります。
  • 実務では偏りを自動で直す平衡木を使い、多くは言語に付いている標準の部品で足ります。

※ 本記事は2026年10月時点の公式情報(省庁・公的機関、および製品やサービスを提供する事業者が公開している資料)に基づきます。

二分探索木は、データ構造の教科書の定番で、Javaなどのプログラミング言語に付いている部品の説明にも出てきます。ただ、ハッシュ表と何が違うのか、どんなときに選ぶのかを聞かれると、すぐに答えられない方もいるのではないでしょうか。

本記事では、二分探索木の基本、探す・入れる・消すの仕組み、木が偏る問題と平衡木、ハッシュ表やB木との違いを、図と表で順に整理します。開発を外部に頼むときに確かめておきたい点も取り上げます。

二分探索木とは

二分探索木は、データ(キー)を1つずつ持つ箱(ノード)を、木の枝のようにつないだ構造です。各ノードの左側には自分より小さいキー、右側には自分より大きいキーだけを置く決まりがあります。*1

  • 根:木のいちばん上にあるノード。探すときはここから始める
  • 子:各ノードの下につながるノード。左右に1つずつまで
  • 高さ:根からいちばん深いノードまでの段数

この決まりのおかげで、左から順にたどるとキーが小さい順に並んで出てきます。「この日付より前で最も新しい記録」や「範囲に入るデータの一覧」を取り出す処理が得意です。処理の速さを件数との関係で表す書き方は「計算量とオーダー記法の読み方」で扱っています。

探す・入れる・消すの仕組み

3つの操作は、どれも根から順に大小を比べて進むだけです。

  • 探す:探す値がノードより小さければ左、大きければ右へ進む。行き止まりに着いたら、その値は入っていない
  • 入れる:探すのと同じ手順でたどり、行き止まりの場所に新しいノードをつなぐ
  • 消す:子が無ければ外し、子が1つならその子を親につなぐ。子が2つなら、右側でいちばん小さいノードと置き換える

1回比べるごとに、片側の枝を丸ごと調べずに済むのが速さの理由です。教科書は、これらの操作には最悪の場合、木の高さに比例した時間がかかるとしています。*1 同じ件数でも、背の低い木なら速く、背の高い木なら遅くなります。

偏りの問題と平衡木

同じ1から7のキーを持つ2つの二分探索木を並べた図。左は4, 2, 6, 1, 3, 5, 7の順に入れた木で、根の4の下に2と6、その下に1・3・5・7が並ぶ高さ3段の形。右は1から7を昇順に入れた木で、右の子だけが一列に7段続き、7を探すと比較が7回かかる。

図の左右は、同じ1から7のキーを持つ二分探索木です。入れる順番が違うだけで、左は3段、右は7段になります。会員番号や受付日時のように、業務のデータは小さい順に近い順番で届くことが少なくありません。そのまま入れると右の形に近づき、探すたびに全件を比べるのと変わらなくなります。

この弱点を補うのが「平衡木」です。入れたり消したりするたびに枝を付け替え、高さを低く保ちます。

  • AVL木:どのノードでも、左右の枝の高さの差を1以内に保つ*3
  • 赤黒木:各ノードに赤か黒の印を付けて形を整える。高さはおよそ件数の対数の2倍以下に収まる*2

Linuxカーネルの文書は、赤黒木はAVL木に比べて、入れる・消す処理の最悪の時間が短いと説明しています。*5

ハッシュ表・B木との違い

似た目的で使われるデータ構造との違いは、次のとおりです。

二分探索木・B木・ハッシュ表の違い
観点 二分探索木(平衡木) B木 ハッシュ表
主な置き場所 メモリ データベースの索引 メモリ
1件を探す速さ 速い 速い うまく散らせば最も速い
小さい順にたどる できる できる できない
範囲の取り出し 得意 得意 不向き

JavaのHashMapの説明書は、要素の順序について何も保証しないと明記しています。*6 一致する値を引くだけならハッシュ表で足り、順序や範囲が要るなら平衡した二分探索木を選びます。データベースの索引で使われる構造は「B木の仕組み」で扱っています。

業務で二分探索木を一から書くことは多くありません。JavaのTreeMapは赤黒木をもとにした部品で、探す・入れる・消すの処理を件数の対数に比例する時間で行うと保証しています。*4 期限が近い順にタスクを取り出す処理や、得点順のランキングなどが使いどころです。

外部に委託するときに確認しておきたい点

順番を保ったデータを扱う開発を外部に頼むときは、次の点を事前に確かめておくと、本番のデータで急に遅くなる事態を防ぎやすくなります。

  • 標準の部品で足りるか:自前で作る提案なら、その理由と偏りの防ぎ方を説明してもらえるか
  • 試験のデータ:小さい順・大きい順・同じ値の連続・件数の多いデータで試しているか
  • 比べ方の決まり:大文字と小文字、日時のタイムゾーンなど、大小の比べ方が設計書にあるか
  • データベースとの分担:メモリに載せる件数と、データベースの索引で代わりが利かないかを検討したか

まとめ:二分探索木で確かめておきたい3つの点

二分探索木で確かめておきたい点は3つです。第一に、左に小さい値、右に大きい値を置く決まりで、探す・入れる・消すの速さは木の高さで決まること。第二に、順番どおりのデータをそのまま入れると一列に偏るため、実務ではAVL木や赤黒木などの平衡木を使い、多くは標準の部品で足りること。第三に、一致する値を引くだけならハッシュ表、順序や範囲が要るなら平衡した二分探索木と、用途で使い分けることです。

LASSICに相談するメリット

LASSICは2006年の創業以来、システムの運用・保守に特化したプライム(一次請け)のシステムインテグレーターとして、企業のシステム開発と保守・運用を受託してきました。Rubyアソシエーション認定システムインテグレータ、日本ニアショア開発推進機構の認定ベンダーとして、全国のリモート人材による開発・運用の体制を整えています。

順序付きのデータを扱う処理では、JavaのTreeMapとConcurrentSkipListMap、C++のstd::map、PostgreSQLのB-tree索引などから、データ量と更新の頻度に合う置き場所を選びます。設計の段階では、完全一致の検索だけか範囲も要るか、メモリに持つかデータベースに任せるか、キーの比較の決まりとロックの取り方を発注者と決めます。検証では、PythonのHypothesisやJavaのjqwikで偏ったデータを自動で作って試験し、JMHで測った性能をCI/CDで毎回確かめます。

よくある質問

二分探索木と二分木は何が違いますか

二分木は、各ノードの子が2つまでの木を広く指す言葉です。二分探索木はそのうち、左側のキーはすべて小さく、右側のキーはすべて大きいという決まりを満たすものを指します。

AVL木と赤黒木はどちらを選べばよいですか

自分で選ぶ場面は多くありません。言語に付いている部品が、すでに方式を決めていることがほとんどです。自前で作るなら、入れる・消すが多い場合は赤黒木が候補になります。

同じキーを複数入れたいときはどうしますか

1つのキーに値の一覧を結びつける方法と、同じキーを許す部品を使う方法があります。同じキーのデータを取り出す順番を決めておきたいかどうかで選びます。

データ構造の選定と性能改善のご相談

元請(プライムベンダー)として、データ構造の選定や性能の検証から、システムの開発と保守・運用までご提案します。

2006年の創業以来、一次請けのシステムインテグレーターとして、企業のシステム開発と保守・運用を受託してきました。

無料相談はこちら

出典

  1. *1 参考:Robert Sedgewick, Kevin Wayne『Algorithms, 4th Edition』公式サイト「3.2 Binary Search Trees」(https://algs4.cs.princeton.edu/32bst/)。出典:二分探索木の定義、操作の時間が木の高さに比例するという命題を参照(2026年10月確認)
  2. *2 参考:Robert Sedgewick, Kevin Wayne『Algorithms, 4th Edition』公式サイト「3.3 Balanced Search Trees」(https://algs4.cs.princeton.edu/33balanced/)。出典:赤黒木の高さが2 lg N以下であることを参照(2026年10月確認)
  3. *3 参考:Leo J. Guibas, Robert Sedgewick「A Dichromatic Framework for Balanced Trees」(第19回 IEEE Symposium on Foundations of Computer Science、1978年)(https://sedgewick.io/wp-content/themes/sedgewick/papers/1978Dichromatic.pdf)。出典:AVL木の平衡条件(左右の部分木の高さの差が1以内)を参照(2026年10月確認)
  4. *4 参考:Oracle「TreeMap (Java SE 21 & JDK 21)」API仕様(https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/TreeMap.html)。出典:赤黒木をもとにした実装であること、containsKey・get・put・removeのlog(n)の保証を参照(2026年10月確認)
  5. *5 参考:The Linux Kernel documentation「Red-black Trees (rbtree) in Linux」(https://docs.kernel.org/core-api/rbtree.html)。出典:赤黒木とAVL木の違い(挿入と削除の最悪の時間)の記述を参照(2026年10月確認)
  6. *6 参考:Oracle「HashMap (Java SE 21 & JDK 21)」API仕様(https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/HashMap.html)。出典:順序を保証しないことの記述を参照(2026年10月確認)




View