本文详细解析了二叉排序树的查找效率，包括查找成功和失败时的平均查找长度计算公式。通过具体实例，展示了如何计算不同层级的节点数量及其对整体查找效率的影响。
二叉排序树的平均查找长度
上图所示为二叉排序树
查找成功时的平均查找长度：
A S L = ∑ （本层高度 ∗ 本层元素结点个数） / 结点总数 = ( 1 ∗ 1 + 2 ∗ 2 + 3 ∗ 2 ) / 5 = 11 / 5 ASL=∑（本层高度*本层元素结点个数）/结点总数\\ =(1 * 1 +2 * 2+3 * 2)/5=11/5 ASL=∑（本层高度∗本层元素结点个数）/结点总数=(1∗1+2∗2+3∗2)/5=11/5
查找失败时的平均查找长度:
A S L = ∑ ( 本层高度 ∗ 本层补上的叶子结点数 ) / 补上的叶子节点总数 = ( 2 ∗ 2 + 3 ∗ 4 ) / 6 = 16 / 6 ASL=∑(本层高度*本层补上的叶子结点数)/补上的叶子节点总数\\ =(2 * 2+3 * 4)/6=16/6 ASL=∑(本层高度∗本层补上的叶子结点数)/补上的叶子节点总数=(2∗2+3∗4)/6=16/6
扫一扫
938
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
