浙江大學-數據結構-選講Complete Binary Search Tree-7.3.3

02-25

計算左子樹的規模

之前的solve函數裡面有一個GetLeftLength函數沒有實現，這個函數就是在計算左子樹的規模，所以最後來看一下左子樹的規模要怎麼樣計算，這就涉及到你需要對一個二叉樹的基本性質有非常熟練的了解，那首先我們來回顧一下這個二叉樹從上往下數它的層數跟它每一層的結點個數都是什麼樣的關係，最頂層我們把它定義為h=1,假設h是層數，那麼這一層的結點個數是等於1，實際上就是2^(1-1),2^0，第二層h=2,這一層的結點個數2^(2-1),以此類推，也就是對任一一層結點個數就是2^(h-1),對於一共有h層的完美二叉樹結點的總個數是多少呢？就要把這些數統統加起來

假設我們一共有大寫的H層的話，那麼它的總數加在一起就是 $2^H-1$ ,對於一個完全二叉樹來說，它的形狀實際上就是上面有一個H層的完美二叉樹，一共有這麼多個結點，然後最下面這一層有若干個結點，我們把這個結點的個數記成是X,於是我們就很容易得到一個公式，這個完全二叉樹的結點總個數。

完全二叉樹的結點總個數N就等於上面這棵完美二叉樹的結點總個數，也就是 $2^H-1$ ,然後加上它最底下這一層結點的個數X,那麼從這個式子裡頭，我就可以直接把H算出來了，就是把-1,X統統挪到等號的右邊，然後等號兩邊統統取一個以2為底的log,就得到了H的計算公式，通常你如果真的去算這個數字的話，這個數算出來不是一個整數，但是這個X是多少其實並不影響大局，總的來說這一項是N+1減去一個不影響大局的數字X,然後再以2為底求一個log,所以在真正計算H的時候，就可以把X忽略掉，然後最後再向下取整，這樣我就得到了一個H的值，這個H就應當是上面這個完美二叉樹的層數，得到了H的值以後，就可以從 $2^H - 1 + X = N$ 裡面反算出來了，重要的是我們需要知道左子樹到底有多少個結點，這個數要怎麼算呢？因為這棵樹也是一棵完全二叉樹(下圖紅色部分加上最下面3個結點)，所以它的結點個數也應該上面這棵完美二叉樹結點的總數加上下面這層X的個數

上面這層完美二叉樹的結點個數總數是多少呢？我們來看一下這個規律，當我們有H層的時候，這棵樹的結點總數是 $2^H-1$ ,那麼對於它的左子樹來說呢，這個層數就是減少了1層，所以它的總個數應該是什麼，就把這個H換成H-1就好了，於是我就很容易得到左子樹的元素個數應該是 $2^{H-1}-1$ ,這就是上面完美二叉樹的總個數，加上最後一層的X，我們說看上去很容易，到這裡就完了嗎？好像沒這麼簡單，這個X可以直接寫在這，那是因為這棵樹畫成了這棵樣子，如果我這棵樹再多幾個結點呢？這個X就不對了，什麼時候直接加X就不對了呢？把最下面這一層從中間分成左邊一半右邊一半，如果X的個數超過一半的話，那麼我就不能直接把這個X加上去了，那我應該加什麼呢？所以很重要的就是我們要知道最下面這一層X的最小值和最大值可以取多少，最小值要取多少呢？在這個公式裡面，X的最小值要取到0，這個看上去好像會有點疑問

為什麼它的最小值不是1，而是0呢？這個就跟我們H這個公式是直接相關的，這個細節問題呢，就留給大家自己去考慮(2333,在這就不解釋了),最大的可以放到這個公式裡面去的，這個X應該取多大呢，這個問題的答案應該是 $2^{H-1}$ ,為什麼是這個數字呢？你在看一下，我們最下面這一層最多會有多少個結點呢？也就是X在最下面這一層能夠取到多大呢？這個我們前面推算過了，如果這是第h層的話，那麼它的結點個數應該是 $2^{h-1}$ ,是這一層的結點個數，再往下加一層就是第h+1層，那麼它的結點個數就是 $2^{h+1-1}$ ,也就是 $2^h$ ,一共是這麼多個結點在最下面這一層，那麼寫在這個公式裡面正確的X在這種情況下應該是多少呢？應該只包括左子樹的，也就是說應該只包括一半的結點數，也就是 $2^Hdiv2$ ,也就是 $2^{H-1}$ ,綜上所述，我們的X應該取得是先從這個公式里算出一個X來( $2^H-1+X = N$ ),我把這個X跟 $2^{H-1}$ 比較一下，看哪個更小，如果X小於這個數，那麼直接把X加上去就好了，如果X比這個數要大的話，我們只取前面的這一部分(即 $2^{H-1}$ )

總結起來在實現那個GetLeftLength函數的時候，第一步要根據輸入的N,用這個式子去算一個H出來，知道這個H以後，帶到最開始的等式裡面( $2^H-1+X = N$ ），就把X解出來，然後把X跟 $2^{H-1}$ 比較一下，取小的那個數字，這是第二步，然後把第二步得到的正確的X帶到最後這個公式裡面去，返回計算出來的L就可以了。