テクノロジ
完全二分木とは
読み方：かんぜんにぶんぎ
ひとことで言うと：最下段以外が埋まり、最下段も左から詰めて配置された二分木。
意味をわかりやすく解説
完全二分木は、最下段より上の階層がすべて埋まり、最下段のノードも左から詰めて配置されている二分木です。
この形ではノードを配列に隙間なく格納しやすく、親子の位置を添字計算で求められるため、ヒープの実装に向いています。
具体例
1始まりの配列で完全二分木を格納すると、ノードiの左の子を2i、右の子を2i+1として表せます。
似た用語との違い
二分木
二分木は子が最大2個という条件だけです。完全二分木はさらに階層の埋まり方に条件があります。
ヒープ
ヒープは完全二分木の形を保ち、親子間に大小関係を持たせたデータ構造です。
覚え方
上から埋め、最後の段だけ左詰め。
基本情報技術者試験の試験ポイント
配列での親子添字とヒープとの関係を問われやすいです。
CHECK QUESTION
1始まりの配列で完全二分木を格納するとき、添字iの左の子の添字は一般に何ですか。
答えを見る
2iです。右の子は2i+1です。
この説明は分かりやすかったですか？
基本情報技術者試験を勉強中ですか？
この用語を含む重要用語を、単語帳や4択テストで学習できます。