BST はなぜ高速ですか？

平衡している場合、検索・挿入・削除がいずれも O(log n) です。各ノードで「左<自分<右」を満たすため、半分ずつ探索範囲が絞れます。ただし偏ると O(n) に劣化するため、実用では赤黒木・AVL 木のような自動平衡化された実装を使います。

in-order 走査で何が得られますか？

BST を in-order で巡回するとソート済みの順序で要素が得られます。これが BST と他のツリーの大きな違いで、ソート済みデータの逐次処理に向いています。範囲検索（lo 以上 hi 以下）も簡潔に書けます。

実装次第ですが、通常は「等しい場合は右に入れる」「カウントを持って同じノードに記録する」のいずれかです。重複が多いユースケースなら TreeMap のように出現数を値に持たせる方が探索効率が上がります。

BST を in-order で巡回するとソート済みの順序で要素が得られます。これが BST と他のツリーの大きな違いで、ソート済みデータの逐次処理に向いています。範囲検索（lo 以上 hi 以下）も簡潔に書けます。

実装次第ですが、通常は「等しい場合は右に入れる」「カウントを持って同じノードに記録する」のいずれかです。重複が多いユースケースなら TreeMap のように出現数を値に持たせる方が探索効率が上がります。

第2章まとめクイズ — 二分木

二分木 [1, 2, 3, null, 4] を in-order (左 → 根 → 右) で走査した結果として正しいものはどれですか。

未回答の問題は、不正解として正解と解説のみ表示します

ログインが必要です

クイズに回答するにはログインしてください。