對于一個研究專案，我正在使用隔離森林演算法。該演算法的開發者利用了二叉搜索樹理論。他們指出，二叉搜索樹 (c(n)) 中不成功搜索的平均深度定義為：
c(n)=2H(n-1)-(2(n-1)/n)
其中 H(n-1) 是諧波數，可以通過 ln(n-1) 0.5772156649（歐拉常數）來估計，n 是樹中終端節點的數量。
有人可以（數學上）解釋這些公式的來源嗎？
uj5u.com熱心網友回復：
請注意，這些公式僅適用于其鍵以相對于其自然順序的隨機順序添加的樹：除了可以從隨機插入順序中預期的之外，沒有任何關于樹的形狀或平衡的假設（如果我們知道這棵樹是完美平衡的，數學會有所不同，而且要簡單得多）。他們還假設每個不成功的搜索在樹中的任何空指標處終止的可能性都相等（因為在沒有關于樹的形狀或其值的分布的任何先驗知識的情況下，任何端點的可能性都相等）。
我會注意到，所提供的平均深度成本公式對于 n=1 是未定義的（似乎不必要地右移了 1）。我不知道他們使用的深度和成本的定義，但可以說單例樹探索的平均深度是 1，而不是未定義（因為在該節點上搜索不成功將檢查其空左指標或它的空右指標終止前，探索深度 1)。我會將他們的公式向左移動 1 以適應這種情況：
相對于我將使用的更簡單的公式（當 n 接近無窮大時等效于前一個公式，但對于較小的 n 更準確），該公式仍然略微低估了平均深度（對于 n<~50，在顯著程度上）：
話雖如此，您可以根據 T 中空指標的平均深度來確定在 n 個節點的隨機樹 T 中不成功搜索的平均成本（因為每個不成功的搜索都在某個空指標處終止，具有成本與該指標的深度成正比，我們假設到達所有空端點的可能性相同）。要獲得 T 的平均空深度，可以更容易地獲得總空深度 D，然后除以空指標的數量。
請注意，每棵樹的 n 個節點都有 n 1 個空指標。你可以用歸納法證明這一點，一棵由 1 個節點組成的樹有 2 個空指標，你添加到樹中的每個新節點都會替換一個空指標，但又添加了兩個，保留了空指標比節點多 1 個的不變性. 考慮到這一點，有一種遞回方法可以分析任何樹的總空深度：
基本情況：具有 1 個節點的樹的總空深度為 2。
遞回情況：具有 n 個節點的樹可以將其空指??針以 n 種不同的方式布置，具體取決于選擇哪個節點作為根：如果選擇最小節點 n_1 作為根，則將有 0 個節點，因此為 0 1 = 左子樹中的 1 個空指標，右子樹中的 n-1 個節點和 n 個空指標。如果選擇 n_2 作為根，則左子樹中將有 1 個節點和 2 個空指標，右側有 n-2 個節點和 n-1 個空指標，依此類推，直到您擁有所有節點和所有但是左子樹中有 1 個空指標，右子樹中只有 1 個空指標沒有節點。此外，無論您如何將 n 1 個空指標拆分為左子樹和右子樹，這些子樹中的所有 n 1 個空指標的深度都會增加 1，因為它們都被放置在選定的根下（這是“
這些情況在數學上用遞回表示：
檢查此類似問題的最佳答案，了解為什么當您解決此遞回并將結果除以 n 1 時，結果是 c(n) = 2(H(n 1) - 1)（只需在他們的數學中替換 m與 n 1，和 t 與 D)。
至于為什么自然對數近似于調和數，那是一個單獨的問題，但基本上歸結為 H(x) = 1/1, 1/2, ... 1/x，以及1/x 相對于 x 是 ln(x)。
這是一個實驗，使用精確的諧波數和近似數顯示匯出的公式是正確的：
import sys
import math
from random import random
from functools import cache
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BST:
def __init__(self, values):
self.root = None
self.num_nodes = len(values)
for value in values:
self.root = self.insert(value)
def insert(self, value):
def _insert(root, value):
if not root: return TreeNode(value)
if value < root.value:
root.left = _insert(root.left, value)
else:
root.right = _insert(root.right, value)
return root
return _insert(self.root, value)
# total depth of all None pointers
def total_external_depth(self):
if not self.root: return None
total = 0
def traverse(root, depth = 0):
nonlocal total
if root is None:
total = depth
return
traverse(root.left, depth 1)
traverse(root.right, depth 1)
traverse(self.root)
return total
# average depth of all None ptrs in tree
def average_external_depth(self):
if not self.root: return None
return self.total_external_depth() / (self.num_nodes 1)
max_tree_size = 10
trials = 1000
if len(sys.argv) > 1: max_tree_size = int(sys.argv[1])
if len(sys.argv) > 2: trials = int(sys.argv[2])
results = [0] * max_tree_size
for tree_size in range(1, max_tree_size 1):
for trial in range(trials):
T = BST([random() for i in range(tree_size)])
results[tree_size-1] = T.average_external_depth()
results[tree_size-1] /= trials
@cache # memoized harmonic numbers
def H(n):
if n == 1: return 1
return 1/n H(n-1)
# approximate harmonic numbers
def _H(n): return math.log(n) 0.5772156649
for i, x in enumerate(results):
n = i 1
expt = results[i]
derived = 2*(H(n 1) - 1)
approx = 2*(_H(n 1) - 1)
experimental_error = (expt - derived) / derived * 100
approximation_error = (approx - derived) / derived * 100
print('C({}):\texperimental: {:.3f}\tapprox: {:.3f}\tderived: {:.3f}'.format(i 1, expt, approx, derived))
print('\terror: expt: {:.2f}{}\tapprox: {:.2f}{}'.format(experimental_error, '%', approximation_error, '%'))
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/374655.html