c++二叉排序树平均查找长度

### C++ 中二叉排序树的平均查找长度计算方法

对于二叉排序树（BST），其性能取决于树的高度。理想情况下，一棵平衡良好的二叉排序树可以提供接近 O(log n) 的时间复杂度；然而，在最坏的情况下（例如当输入序列已经有序时），这棵树可能会退化成链表形式，导致查找的时间复杂度变为 O(n)[^1]。

#### 平均查找长度 ASL 定义

平均查找长度（Average Search Length, ASL）是指在一个给定的关键码集合上执行成功或不成功的查找所需的比较次数之期望值。具体来说：

- 成功查找的 ASL 是指在已存在的节点中找到目标所需经过路径上的边的数量加一；
- 不成功查找的 ASL 则是在未命中情况下的预期访问节点数目。

#### 影响因素

影响 BST 上 ASL 主要的因素有两点：一是树形结构本身的好坏程度，二是待查元素分布特性。通常而言，随机构建出来的 BST 更倾向于保持较好的形态从而拥有较低的 ASL 值[^2]。

#### 计算公式

设 T 表示一颗含有 N 个内部结点的二叉搜索树，则该树的成功查找 ASL 可表示为如下公式:

\[ \text{ASL}_{\text{success}}=\frac{\sum_{i=0}^{N}\left(d_i+1\right)}{N}, d_i \]

其中 \(d_i\) 表示第 i 个记录所在位置到根的距离（即深度）。而不成功查找 ASL 的表达式略有不同：

\[ \text{ASL}_{\text{unsuccessful}}=\frac{(E_0+E_N)+2(E_1+\cdots + E_{N-1})}{N+1} \]

这里的 \(E_k\) 指的是从空子树 k 出发到达最近外部节点所经历过的内部分支总数加上一次额外探测操作[^3]。

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    double depthSum; // 存储以当前节点为根的所有节点深度总和
    int nodeCount;   // 统计以当前节点为根的子树内的节点数量
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int v):val(v),depthSum(0),nodeCount(1),left(nullptr),right(nullptr){}
};

// 更新整棵二叉树的信息
void updateTreeInfo(TreeNode*& root){
    if (!root || (!root->left && !root->right)) return ;
    updateTreeInfo(root->left);
    updateTreeInfo(root->right);

    int lDepth = root->left ? root->left->depthSum : 0;
    int rDepth = root->right ? root->right->depthSum : 0;
    int lNodes = root->left ? root->left->nodeCount : 0;
    int rNodes = root->right ? root->right->nodeCount : 0;

    root->depthSum += (lDepth + lNodes + rDepth + rNodes + 1); // 加入自己这一层贡献
    root->nodeCount += lNodes + rNodes;
}

double calculateASLSuccessfulSearch(const TreeNode* root){
    if(!root)return 0.;
    return root->depthSum / static_cast<double>(root->nodeCount);
}