二叉查找树的平均查找次数为n/2吗?

Question

如题所述

Answer 1

平均次数是(n+1)/2，不是n/2。

被查找的数是第1个数，则需用第1个数和被查找的数比较，要比较1次。

被查找的数是第2个数，则需用第1个数、第2个数和被查找的数比较，要比较2次。

...

被查找的数是第n个数，则需用第1个数、第2个数、...、第n个数和被查找的数比较，要比较n次。

平均次数为(1+2+...+n)/n=(n+1)/2。

扩展资料：

顺序查找过程：从表中的最后一个记录开始，逐个进行记录的关键字与给定值进行比较，若某个记录的关键字与给定值相等，则查找成功，找到所查的记录；反之，若直到第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查的记录，查找失败。

算法描述为

int Search(int d,int a[],int n)

{/*在数组a[]中查找等于D元素，若找到，则函数返回d在数组中的位置，否则为0。其中n为数组长度*/

int i ；

/*从后往前查找*/

for(i=n-1;a!=d;--i)

return i ;

/*如果找不到，则i为0*/

}

参考资料来源：百度百科-查找算法

Answer 2

二叉查找树的平均查找次数并不是n/2。
二叉查找树是一种特殊的二叉树，其中每个节点都有一个可以比较的键和关联的值，并且每个节点的左子树中的所有节点的键都小于该节点的键，而右子树中的所有节点的键都大于该节点的键。对于二叉查找树，平均查找次数取决于树的平衡性以及其他因素。
对于完全平衡的二叉查找树（例如AVL树或红黑树），平均查找次数是O(log n)，其中n是树中节点的数量。这是因为在最坏情况下，每个节点都需要旋转两次才能达到平衡，因此在高度为O(log n)的情况下完成查找。
然而，对于非平衡的二叉查找树（例如链表），平均查找次数可能会更高。在这种情况下，平均查找次数取决于链表中元素的分布情况，并且可能需要比较多次才能找到目标元素。在这种情况下，平均查找次数可能是O(n)或更高。
因此，二叉查找树的平均查找次数取决于树的平衡性以及其他因素，而不是简单的n/2。