證明內部節點的數量在樹上

我讀到關於壓縮嘗試和閱讀以下內容：證明內部節點的數量在樹上

後綴樹是有L個葉子和特里樹的每個內部節點至少有2名兒童一棵樹。

然後作者寫道，帶有L的樹離開，使得每個內部節點具有替代2個孩子，具有最內部L-1個內部節點。我真的很困惑，爲什麼這是真的。

有人可以提供一個歸納證明嗎？

來源

2012-01-16 Programmer

這真的很容易...你有沒有嘗試過自己？ – jpalecek 2012-01-16 12:49:57

另外，你的意思是「trie」還是「樹」？他們是不同的數據結構。 – Marcin 2012-01-16 12:55:57

@Marcin - 樹是一種特殊的樹，對於這個問題，差異並不重要。 – Ishtar 2012-01-16 12:58:37

歸納證明：
我們將通過歸納證明它L - 葉子在樹的數量。
基數： 1葉製成的樹實際上是一棵只有根的樹。它有0個內部節點，並且聲明是正確的。
假定對於具有L個葉子的壓縮樹，該聲明是正確的。
步驟：讓T是一棵有L + 1葉的樹。選擇一個任意的葉子，讓它爲l，並修剪它。
爲了再次壓縮樹 - 你需要讓我的父親成爲一片葉子[如果我的父親有兩個以上的兒子，包括l，跳過這一步]。我們通過給予它與兄弟的價值相同的價值，並修整這位兄弟。
現在你有一棵樹'T'與L葉。
歸納法：T'最多有L-1個內部節點。
所以，T最多有L-1 + 1 = L個內部節點，並且L + 1離開。 012.M.

另一個證明：
與L-樹葉的二進制樹具有L-1內部節點（1 + 2 + 4 + ... + L/2 = L-1）
由於在「最壞情況」你有一棵二叉樹[每個內部節點至少有兩個兒子！]，那麼你不能有更多的L-1內部節點！

來源

2012-01-16 13:04:36 amit

@Nemo：如果父親有兩個以上的兒子，包括l，那麼通過修剪l，並且什麼都不做，新樹中有L個葉子[讓它成爲T']，並且通過歸納假設，在T'中沒有更多的L-1內節點。我們沒有修剪任何內部節點，所以在T中沒有更多的L-1內部節點。這個案子很瑣碎而且沒有趣味，所以我跳過了它。關於替代證明：這是一個證明的指導原則。證明二進制情況是最糟糕的情況並不困難。 – amit 2012-01-16 16:43:02

是的，我的錯誤。在評論之前需要醒來。 – Nemo 2012-01-16 16:59:09

你能解釋一下：具有L葉的二叉樹有L-1個內節點（1 + 2 + 4 + ... + L/2 = L-1）嗎？ – crisron 2016-10-17 02:27:06

您應該嘗試繪製一個帶有L個內部節點的樹，其中每個節點有2個孩子並且有L個葉子。如果你明白爲什麼這是不可能的，那麼就不難搞清楚它爲什麼對L-1內部節點起作用。

來源

2012-01-16 13:03:18 Ishtar

好的，我會去的。

定義樹的一個開始：現在

T_0 = { Leaf } 

T_i = T_i-1 union { Node(c1, ..., cn) | n >= 1 && ci in T_i-1 } 

Trees = sum T_i

，在（素描）您結論的證明。

這是很容易檢查其T_0
對於T_i：如果t \in T_i它無論是在T_i-1或在新的元素。在前一種情況下，使用IH。在後一種情況下檢查斷言（如果ci s有L_i葉子，t有L = L_1 + ... + L_n葉子，它也不超過L_1 - 1 + L_2 - 1 + ... + L_n - 1 + 1內部節點（通過IH爲孩子，+1爲自己）因爲我們假設每個內部節點都有至少有兩個孩子（這是來自trie定義的事實），它不超過L_1 + l_2 + ... + L_n - 2 + 1 = L - 1）。
通過歸納法，如果所有i的主張均爲t in T_i，則它適用於t in Trees。

來源

2012-01-16 13:16:24 jpalecek

不要喂幫助吸血鬼！ – Marcin 2012-01-16 13:41:21

證明內部節點的數量在樹上

回答

相關問題