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

2色木
        2分木と色情報による 2-3-4 木の表現
        色情報を無視すると2分探索木

2色木の基本操作の手順
        所属判定        色情報を無視して2分探索
        挿入            根から葉へ探索しながら分割(色替え)をし，赤辺と葉を追加
                        分割や追加で赤辺が続いたら，そのつど修正(平坦化)
        削除            (本講義では扱わない)

2分木の回転
        2分木の基本操作のひとつで，右回転と左回転がある
        2分探索木の大小順を保ったまま木を変形
        2色木の平坦化の実現に使える

2分木の走査
        各要素を処理しながら2分木全体をたどる
        先行順，中間順，後行順，がある

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

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