テクノロジ
二分探索木とは
読み方：にぶんたんさくぎ
ひとことで言うと：左に小さい値、右に大きい値を配置して探索を効率化する二分木。
意味をわかりやすく解説
二分探索木は、各ノードについて左部分木に小さい値、右部分木に大きい値を置く規則を持つ二分木です。規則により探索時に片側の部分木を捨てられます。
木がバランス良く保たれていれば探索・挿入・削除はおおむねO(log n)ですが、片側に偏ると連結リストのようになりO(n)まで悪化します。
具体例
根が50なら、30を探すときは左へ、70を探すときは右へ進みます。
似た用語との違い
覚え方
左は小、右は大。比較するたびに探索範囲を片側へ絞ります。
基本情報技術者試験の試験ポイント
平衡時と最悪時の計算量、挿入順によって木が偏ることを理解します。
CHECK QUESTION
1,2,3,4,5の順に単純な二分探索木へ挿入すると、探索効率が悪化しやすいのはなぜですか。
答えを見る
右側だけに偏った木になり、高さがnに近づいて探索がO(n)になり得るからです。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。