math - 二叉搜索树中不成功搜索的平均深度

Question

对于一个研究项目，我正在使用隔离森林算法。该算法的开发者利用了二叉搜索树理论。他们指出，二叉搜索树 (c(n)) 中不成功搜索的平均深度定义为：

c(n)=2H(n-1)-(2(n-1)/n)

其中 H(n-1) 是谐波数，可以通过 ln(n-1)+0.5772156649（欧拉常数）估计，n 是树中的终端节点数。

有人可以（数学上）解释这些公式的来源吗？

Answer 1

请注意，这些公式仅适用于其键以相对于其自然顺序的随机顺序添加的树：除了可以从随机插入顺序中预期的之外，没有任何关于树的形状或平衡的假设（如果我们知道树是完全平衡的，数学会有所不同，而且更简单）。他们还假设每个不成功的搜索在树中的任何空指针处终止的可能性相同（因为没有任何关于树的形状或其值分布的先验知识，任何端点都有同样的可能性）。

我会注意到提供的平均深度成本公式对于 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 和积分关于 x 的 1/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, '%'))