完全ニ分木探索
完全二分木に関する考察
◆作成ルール
「親ノードの値より小さなデータは左の子ノードに、大きなデータは右の子ノードに配置する。」
葉の数をnとした場合。
・節の数：2n乗-1 （葉のノードを抜いた数）
・葉の数：2n乗
・深さ： （根から葉のノード）-1
最良探索数 S = log2N
最悪探索数 S=N
完全二分木では，n回の探索で2^n個の要素に対応。
2回の探索では４つまでの要素数に対応でき 3回の探索では8つまでの要素に対応。7つの要素数の場合，2回では足りないため（4つまでしか対応できないため），3回探索する必要がある。
探索数は、四捨五入というよりは，切り上げる。
◆探索方法（巡回法）
・幅優先探索
分岐が多くなるように、根に近い節から順に探索する方法。同じ深さの節では左→右
・深さ優先探索
根からできるだけ分離せず、できるだけ深く探索する。葉に達したら、１つ前のふしに戻って他方を探索する
