有關線段樹的一些性質探讨（完全、平衡）

問題

1. 線段樹含有度為1的結點嗎？

   答：線段樹沒有度為1的結點。

   從遞歸的角度來看，區間長度為1時，度為0；區間長度為2時，度為2和0；而對于任意區間長度大于2的區間來說，總可以将其分解成更小的左右區間，對于被分的結點，它的度為2，不存在度為1的結點

   從另外一方面考慮，假設樹中存在度為1的結點A，由于線段樹的父結點區間等于左右兒子區間之和，那麼A的區間長度等于其兒子的區間長度，又由于線段樹中的區間長度至少是1（葉結點），那麼A的區間最小也為1。A的區間為1是不被允許的，因為A就是葉結點，不能再分；如果A的結點大于1，那麼一定可以分成左右兩個結點，是以A不可能度為1

2. 如果數組元素個數為N，那麼建立一顆線段樹總共構成（需要）多少個結點?

   答：2N-1

   對于線段樹，由于1的論證，不存在度為1的結點，由于線段樹的葉結點的 值和數組值是等價的，它們的個數相同，

   也就是 n0=N ，同時，我們有：

   n0+n1+n2=2n2+n1+1

   把 n1=0 帶入， n2=N−1

3. 線段樹是完全二叉樹嗎？

   答：某些情況下，不是完全二叉樹，例如區間[1,6]

4. 用數組儲存線段樹，1為根結點，2N個樹結點大小的空間夠了嗎？

   答：某些情況下，不夠，因為可能不是完全二叉樹，這意味着中間空了結點，大于2N，例如區間[1, 6]不是完全二叉樹，需要14個樹結點空間，而不是2×6=12個

5. 葉結點和樹結點區間長度有怎樣的關系

   答：某個樹結點的區間長度等于該結點構成的子樹的所有葉結點個數之和

6. 樹結點的左右子樹有怎樣的關系？

   左子樹和右子樹區間長度之差總是小于等于1，即葉結點個數之差總是小于等于1

7. 線段樹是平衡二叉樹嗎？

   答：是平衡二叉樹

   假設結點A為某失衡結點，那麼，它一定有左兒子和右兒子，線段樹每增加一層，子樹葉結點增加1，失衡時，左右高度之差為2，這意味着失衡結點的左右子樹葉結點之差為2，這是不可能的（即使是放在同一層也不可能）

8. 待續