小さいものは左、大きいものは右

図の内容

1. 1根：すべての探索が最初に比べるキー
2. 2左の子：根より小さいので左に置かれる
3. 3右の子：根より大きいので右に置かれる
4. 4右部分木の葉：根より大きいが親より小さいので、親の左にぶら下がる

例

• 1から100までの数を当てるとき、毎回「もっと大きい」か「もっと小さい」と答えてもらうと、残りの半分ずつが消える
• 紙の辞書で単語を探すとき、真ん中を開いてから前か後ろへめくる

クイズ：小さいものは左、大きいものは右（17歳）

1. 1

   二分探索木で、キーが 50 のノードの左部分木のどこにでも置けるキーはどれですか？

   • ノードのすぐ下は 50 より小さいキー、それより深い所はどんなキーでもよい
   • 50 より小さいキーだけ
   • ノードの直接の左の子が 50 より小さければ、どんなキーでもよい
2. 2

   ある二分探索木の根は 50 で、根の右の子は 80 です。新しいキー 60 はどこに入りますか？

   • 右部分木の、80 の左
   • 右部分木の、80 の右
   • 左部分木、60 は 80 より小さいから
3. 3

   よくバランスの取れた二分探索木でキーを探すとき、だいたい何個のノードを調べますか？

   • 木のすべてのノード
   • 1 つのレベルのノードをすべて調べてから次のレベルへ下りる
   • 各レベルでおよそ 1 個のノード

答えと解説はアプリにあります。このレッスンは無料の1週間を過ぎたため、クイズは定期購入に含まれます。