; 当先后插入的关键字有序时，构成的二插排序树蜕变为单支树。树的深度为n,其平均查找长度为（n+1）/2.这是最差的情况。这种情况下比较关键字的最大次数为n次。
(2)最好的情况是：
建成的树是一棵平衡二叉树。在这种情况下，二插排序树的平均查找长度和log2(n)成正比。比较关键字的最大次数为：0.5logψ（5）＋logψ(n+1)-2次（其中ψ＝（1＋根号5）/2）。
(3)那么，平均情况下分析：
假设在含有n(n>=1)个关键字的序列中，i个关键字小于第一个关键字，n-i-1个关键字大于第一个关键字，则由此构造而得的二插排序树在n个记录的查找概率相等的情况下，其平均查找长度为
：p(n,i)=[1+i*(p(i)+1)+(n-i-1)(p(n-i-1)+1)]/n
其中p(i)为含有i个结点的二插排序树的平均查找长度，则p(i)+1为查找左子树中每个关键字时所用比较次数的平均值，p（n-i-1）+1为查找右子树中每个关键字时所用比较次数的平均值。又假设表中n个关键字的排列是“随机”的，即任一个关键字在序列中将是第1个，或第2个，…，或第n个的概率相同，则可对上式从i等于0至n-1取平均值。最终会推导出：
当n>=2时，p（n）<=2（1＋1/n）ln(n)
由此可见，在随机的情况下，二插排序树的平均查找长度和log（n）是等数量级的。
五、时间复杂度的分析
说明：对时间复杂度的分析，均指在最坏情况下的时间复杂度。
二插链表存储结构中：
（1） 查找函数最坏的情况是要找的点正好是二叉树的最深的叶子结点，此时时间复杂度＝o（n）。
（2） 插入函数最坏的情况是要插入的点正是二叉树的最深的那一支的叶子结点，此时时间复杂度＝
o（n）。
（3） 中序遍历函数，求平均查找长度的函数，删除函数以及判断二插排序树是否为平衡二叉树的函数，其时间复杂度均与以上情况类似，等于 o（n）。
一维
上一页 [1] [2] [3] [4] [5] [6] 下一页