読み方のヒント
矢印ボタン(または ← → キー)でページを移動できます。
木は、親と子の関係でデータをつなぐ構造です。いちばん上を根、子を持たない要素を葉と呼びます。各要素の子が2つまでの木を2分木と呼びます。
2分探索木は、どの要素についても「左の子の側の値<その要素の値<右の子の側の値」となるように並べた2分木です。
50
/ \
30 70
/ \ /
20 40 60
60を探すときは、根の50と比べて大きいので右へ、70と比べて小さいので左へ進み、2回の比較で見つかります。木の形が偏らなければ、要素の数が増えても、比較の回数は少なく済みます。
スタック:取り出す順は 2、4、3 で、最後は3です。
キュー:取り出す順は 1、2、3 で、最後は3です。
どちらも最後は3ですが、途中の順番が違います。表に入っている値を書きながら追うと、間違えにくくなります。
19 / 30