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

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" 术语来自于重复）。由于这棵树以及因此要分裂的根的选择是随机的，因此所有分裂的可能性都是一样的，因此您对所有 n 种可能的分裂进行平均以获得大小为 n 的树的预期总空指针深度，D_n = c (n)(n+1)（你仍然需要用总的空深度除以指针的数量来得到平均搜索深度）。

这些情况在递归中以数学方式表示：

检查 this similar question 的最佳答案，了解为什么当您解决此递归并将结果除以 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, '%'))

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

the average depth in an unsuccessful search in a Binary Search Tree

math

binary-search-tree

anomaly-detection

isolation-forest