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

木の基本用語
        根，頂点（節），葉，親，子，兄弟
        頂点の深さ，木の高さ

2分木
        どの頂点も子の数が2以下，という条件を満たす木

完全2分木
        最下段以外の頂点のどの親も子の数が2で，
        最下段の頂点を左詰めにする2分木

ヒープ
        どの子の値もその親の値以上，という条件を満たす完全2分木
        順位付きキューを表せる

ヒープの操作手順
        挿入：最下段に左詰めで葉を追加し，葉から根へ向けて必要なら値を交換
        削除：最下段の最右の値を根に移し，根から葉へ向けて必要なら値を交換
        ※解説スライド「ヒープの操作手順」を参照

ヒープの実現
        ヒープを配列 a で表すと，根は a[1]，a[i] の子は a[2i] と a[2i+1]

完全2分木の性質
        要素数 n の完全2分木の高さは [log2 n]

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

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