━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
データ構造・アルゴリズム論 第７回「2分木 2」の要点
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

オーダーの比較
        Ｏ(1) << Ｏ(log n) << Ｏ(n) << Ｏ(n log n) << Ｏ(n^2)

2分探索
        中央の値と比べて一致するまで，集合を2分割して一方だけを調べる
        ※解説スライド「配列の2分探索」を参照

2分探索木
        各頂点が「左の子孫 ＜ 頂点 ＜ 右の子孫」を満たす2分木
        辞書を表せる

2分探索木の操作手順
        所属判定        2分探索と同様に根から葉へ向けて探索
        挿入            挿入値を探索し，探索失敗位置に葉を追加
        削除            削除値の子が一つ以下なら，その位置に部分木を連結
                        削除値の子が二つなら，その次に大きい値で上書きし，
                        空いた位置に部分木を連結
        ※解説スライド「2分探索木の操作手順」を参照

━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
授業のホームページ

山田 俊行
https://www.cs.info.mie-u.ac.jp/~toshi/