外点の個数(データ構造)

アルゴリズム

外点

2分探索木に導入される架空の頂点． 元からある頂点を内点，架空の頂点を外点という． 要素は内点にのみ割り当てられる．

外点の個数

内点の個数をn個とすると，外点の個数はn+1個である．

これを数学的帰納法により証明する．

[i]n=1の場合，

外点の個数はn+1より

1+1=2

である． 内点が1個のみであるから，1個のみに対する架空の点は2個である．

従って，n=1の場合成立する．

[ii]n=kの場合成立すると仮定する．

外点の1個を内点に置き換えた時 内点の個数は1個減り， 外点の個数は置き換わった1つ分減り，新たな内点に対する外点が2つ増えるから外点の個数は

(k+1)-1+2=(k+1)+1

この式はn=k+1の場合に成立することを示す．

[i]，[ii]より外点の個数がn+1であることが数学的帰納法により示された．

一言

講義でやった内容の復習も兼ねて記事にしていきたいと思います． 間違いがあったら是非教えてください．