Complete BSTで、欠けている数字を探す
限定的な状況でComplete BSTで問題解決する方法に関する記事です。
n = 2^k - 1とします。（kは1より大きい数）
Complete Binary Treeを考えます。このComplete BSTは、0,1,2,...nの数字のうち、一つを除いた全ての数字を保つことができます。所持できなかった数字をk回以下の比較で決定するにはどうしたらいいか？
例えばk = 3とすると n = 2^3 - 1 = 7となります。
この場合、0,1,2,3,4,5,6,7の数字を使って、Complete BSTをつくるわけですが、深さ2のComplete BSTの場合、1+2+4 = 7個の数字しか使わないので、一つあまります。
その数字はどうやって求めるかという問題です。問題の制約としては、必ず欠けている数字があることです。
以下の場合、0が欠けているとして、1~7を使ってComplete BSTを作りました。
問題にComplete BSTと書いてあるので、本末転倒なのですが、ソート済みかつ連続した数値を要素として持つことが想定された配列から欠損している数字を効率的に選び出したいとき、「ソート済み配列をComplete BSTのデータ構造を想定して探索する」ことが有効な手段となりえます。
Structogramは以下のようになります。
全体の構造としては、ある条件式に一致してReturn文に到達するまで、Whileループでごにょごにょしています。中身をみてみましょう。
今回の配列は[1,2,3,4,5,6,7]で、0が欠けているので0を求めたい状況です。
Complete BSTを想定するので、rootの位置を決めます。
連続した数字を持つ配列でのBSTでは、rootは配列の中間のindexの要素となります。
mid := [(l+r)/2]
のmidでその位置を計算しています。
今回の例だと、n=7なのでmid = 3、indexが3のものがrootにきます。
[1,2,3,4,5,6,7]では4がrootの値です。
最初の条件式は以下のように何かを判定しています。
A[mid] ≠ mid AND A[mid-1] = mid-1
これは rootにくる要素が欠損した数字ならばTrue となる条件です。具体的には、
A[3] ≠ 3 AND A[2] = 2
を判定しており、これがTrueの場合というのは、 A[2] = 2までは欠損してない一方、A[3] = 3でないことから、3が欠けていると判断できます。そのため、Trueの場合midが欠損した数字だとしてReturnします。
例えば、7が欠損している場合[0,1,2,3,4,5,6]では3がrootの値です。この場合はA[3] ≠ 3 AND A[2] = 2はA[3] ≠ 3の部分がFalseであるため全体としてFalseとなり、たしかにrootにくる要素3は欠損していないことが判定できています。
A[3] ≠ 3 AND A[2] = 2
がFalseの場合、root値が欠損してない場合の条件式を引き続き見てみます。
A[mid] ≠ mid
これがTrueの場合は、rootは正しい数字が入っていないということなので、root以前、つまりrootからみたleft subtreeで欠損がおこっていることを意味します。そのため次の探索はleft subtreeとなり、r = mid - 1として、探索範囲のindex上端となるrをr = mid - 1として更新しています。
Falseの場合は、rootまでは正しい数字が入っているということです。探索範囲のindex下端lをl = mid + 1として、次のループでright subtreeを探索します。
Discussion