二叉排序树原理_最佳二叉排序树定义

2024年 7月 27日下午3:12 • 激活谷笔记

数据结构之算法（二叉排序树的查找分析）　　在二叉排序树上查找其关键字等于给定值的结点的过程,恰是走了一条从根结点到该结点的路径的过程,和给定值比较的关键字个数等于路径长度加1(或结点所在层次数),因此,和折半查找类似,与给定值比较的关键字个数不超过树的深度。然而,折半查找长度为n的表的判定树是惟一的,而含有n个结点的二叉排序树却不惟一。图1中(a)和(b)的两棵二叉排序树中结点的值都相同,但前者由关键字序列(45,24,53,12,37,93)构成,而后者由关键字序列(12,24,37,45,53,93)构成。(a)树的深度为3,而(b)树的深度为6。再从平均查找长度来看,假设6个记录的查找概率相等,为1/6,则(a)树的平均查找长度为　　
$ASL_{（a）} =\frac{1}{6} [1 + 2 + 2 + 3 + 3 + 3] = 14/6$ 　　而(b)树的平均查找长度为：　　ASL_{(b)} = \frac{1}{6} [1 + 2 + 3 + 4 + 5 + 6] = 21/6

图1 不同形态的二叉查找树（a）关键字排序为（45,24,53,12,37,93）的二叉排序树（b）关键字排序为（12,24,37,45,53,93）的单支树　　因此,含有n个结点的二叉排序树的平均查找长度和树的形态有关。当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树。树的深度为n,其平均查找长度为
$\frac{n+1}{2}$ (和顺序查找相同),这是最差的情况。显然,最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和
$\log_2 n$ 成正比。那么,它的平均性能如何呢? 　　假设在含有n(n≥1)个关键字的序列中,i个关键字小于第一个关键字,n-i-1个关键字大于第个关键字,则由此构造而得的二叉排序树在n个记录的查找概率相等的情况下,其平均查找长度为　　P（n，i）=
$\frac{1}{n}$ [1 + i * (P(i) + 1) + (n – i -1 )(P(n – i – 1)+1)] (9-17) 　　其中P(i)为含有主个结点的二叉排序树的平均查找长度,则P(i)＋1为查找左子树中每个关键字时所用比较次数的平均值,P(n一i一1)＋1为查找右子树中每个关键字时所用比较次数的平均值。又假设表中n个关键字的排列是“随机”的,即任一个关键字在序列中将是第1个,或第2个……,或第n个的概率相同,则可对(9-17)式从主等于0至n-1取平均值

　　容易看出上式括弧中的第一项和第二项对称。又，i=0时iP(i)=o,则上式可改写为

　　由此可见,在随机的情况下,二叉排序树的平均查找长度和 logn是等数量级的。然而,在某些情况下(有人研究证明,这种情况出现的概率约为46.5%)0,尚需在构成二叉排序树的过程中进行“平衡化”处理,成为二叉平衡树。　　如果你想学编程，可以来小编的C/C++编程秃头俱乐部

二叉排序树原理_最佳二叉排序树定义

相关推荐