高度平衡的二叉树
时间：2025-04-23
这个课件是学数据结构的时候老师提供的,里面比较详细地讲解了平衡二叉树的原理以及应用,欢迎下载!
高度平衡的二叉搜索树AVL( Addison-Velski and Landis )树 伸展树 红黑树
这个课件是学数据结构的时候老师提供的,里面比较详细地讲解了平衡二叉树的原理以及应用,欢迎下载!
二叉搜索树性能分析
对于有 n 个关键码的集合，其关键码有 n! 种 不同排列，可构成不同二叉搜索树有 1 n C 2 n (棵)n 1
{2, 1, 3} {1, 2, 3} {1, 3, 2} {2, 3, 1} {3, 1, 2} {3, 2, 1}1 2 3 2 1 3 1 2 3 1
32
3
2
1
这个课件是学数据结构的时候老师提供的,里面比较详细地讲解了平衡二叉树的原理以及应用,欢迎下载!
同样 3 个数据{ 1, 2, 3 },输入顺序不同，建立 起来的二叉搜索树的形态也不同。这直接影响 到二叉搜索树的搜索性能。 如果输入序列选得不好，会建立起一棵单支树， 使得二叉搜索树的高度达到最大。 用树的搜索效率来评价这些二叉搜索树。 为此，在二叉搜索树中加入外结点，形成判定 树。外结点表示失败结点，内结点表示搜索树 中已有的数据。 这样的判定树即为扩充的二叉搜索树。
这个课件是学数据结构的时候老师提供的,里面比较详细地讲解了平衡二叉树的原理以及应用,欢迎下载!
举例说明。已知关键码集合 {a1, a2, a3} = {do, if, to},对应搜索概率p1, p2, p3, 在各搜索不成功 间隔内搜索概率分别为q0, q1, q2, q3。可能的二 叉搜索树如下所示。p3 if to q3 q2 q1 q0 if p2 p1
p2 do p1 q0
do
to
p3
q1
q2
q3
(a)
(b)
这个课件是学数据结构的时候老师提供的,里面比较详细地讲解了平衡二叉树的原理以及应用,欢迎下载!
do p1 if q0 p2 to q1 p3
p1 q0
p3 do
to q3 if p2
q2
q3q0
(c)
do p1 to p3 p2 if q3
q1
q2
(d)
判定树q1
q2
(e)
这个课件是学数据结构的时候老师提供的,里面比较详细地讲解了平衡二叉树的原理以及应用,欢迎下载!
在判定树中 ○表示内部结点，包含了关键码集合中的 某一个关键码； □表示外部结点，代表各关键码间隔中的 不在关键码集合中的关键码。 在每两个外部结点间必存在一个内部结点。 一棵判定树上的搜索成功的平均搜索长度 ASLsucc可以定义为该树所有内部结点上的搜 索概率p[i]与搜索该结点时所需的关键码比较 次数c[i] (= l[i], 即结点所在层次) 乘积之和：ASL succ p[ i ] * l [ i ].i 1 n
这个课件是学数据结构的时候老师提供的,里面比较详细地讲解了平衡二叉树的原理以及应用,欢迎下载!
设各关键码的搜索概率相等：p[i] = 1/nASL succ
l [ i ]. ni 1
1
n
搜索不成功的平均搜索长度ASLunsucc为树中所 有外部结点上搜索概率q[j]与到达外部结点所 需关键码比较次数c'[j](= l'[j])乘积之和：ASL unsucc q[ j ] * ( l ' [ j ] 1).j 0 n
设外部结点搜索概率相等：q[j] = 1/(n+1):ASL unsucc
( l' [ j ] 1). n 1j 0
1
n
这个课件是学数据结构的时候老师提供的,里面比较详细地讲解了平衡二叉树的原理以及应用,欢迎下载!
(1) 相等搜索概率的情形
设树中所有内、外部结点的搜索概率都相等： p[i] = 1/3, 1≤i≤3, q[j] = 1/4, 0≤ j≤3 图(a): ASLsucc = 1/3*3+1/3*2+1/3*1 = 6/3, ASLunsucc = 1/4*3*2+1/4*2+1/4*1 = 9/4。 图(b): ASLsucc = 1/3*2*2+1/3*1 = 5/3, ASLunsucc = 1/4*2*4 = 8/4。 图(c): ASLsucc = 1/3*1+1/3*2+1/3*3 = 6/3, ASLunsucc = 1/4*1+1/4*2+1/4*3*2 = 9/4。 图(d): ASLsucc = 1/3*2+1/3*3+1/3*1 = 6/3, ASLunsucc = 1/4*2+1/4*3*2+1/4*1 = 9/4。
这个课件是学数据结构的时候老师提供的,里面比较详细地讲解了平衡二叉树的原理以及应用,欢迎下载!
图(e): ASLsucc = 1/3*1+1/3*3+1/3*2 = 6/3,
ASLunsucc = 1/4*1+1/4*3*2+1/4*2 =9/4。
图(b)的情形所得的平均搜索长度最小。
这个课件是学数据结构的时候老师提供的,里面比较详细地讲解了平衡二叉树的原理以及应用,欢迎下载!
(2) 不相等搜索概率的情形
设二叉搜索树中所
有内、外部结点的搜索概率 互不相等。 p[1] = 0.5, p[2] = 0.1, p[3] = 0.05 q[0] = 0.15, q[1] = 0.1, q[2] = 0.05, q[3] = 0.05 分别计算各个可能的扩充二叉搜索树的搜索性 能，判断哪些扩充二叉搜索树的平均搜索长度 最小。
这个课件是学数据结构的时候老师提供的,里面比较详细地讲解了平衡二叉树的原理以及应用,欢迎下载!
to p3=0.05 if p2=0.1 do p1=0.5 q0=0.15 q3=0.05 if p1=0.5 do
p2=0.1
p3=0.05 to q3= q2=0.05 0.05 q1=0.1 q0=0.15 q1=0.1 q2=0.05
(a)
(b)
图(a): ASLsucc = 0.5*3+0.1*2+0.05*1 = 1.75, ASLunsucc = 0.15*3+0.1*3+0.05*2+ 0.05*1 = 0.9。 图(b): ASLsucc = 0.5*2+0.1*1+0.05*2 = 1.2, ASLunsucc = (0.15+0.1+0.05+0.05)*2 = 0.7。
这个课件是学数据结构的时候老师提供的,里面比较详细地讲解了平衡二叉树的原理以及应用,欢迎下载!
do p1=0.5 q0= if p2=0.1 0.15 to q1=0.1 p3=0.05
to p3=0.05 do p1=0.5 q0=0.15 q1=0.1
q3=0.05 if p2=0.1
q2=0.05
q3=0.05
(c)
(d)
q2=0.05
图(c): ASLsucc = 0.5*1+0.1*2+0.05*3 = 0.85, ASLunsucc = 0.15*1+0.1*2+0.05*3+0.05*3 = 0.75. 图(d) : ASLsucc = 0.5*2+0.1*3+0.05*1 = 1.35, ASLunsucc = 0.15*2+0.1*3+0.05*3+0.05*1 = 0.8.
高度平衡的二叉树.doc
将本文的Word文档下载到电脑
下一篇：YSD130煤矿用噪声检测仪
