在一棵深度为h的具有n个元素的二叉排序树,查找所有元素的最长查找长度为?

2022-05-08 文化 248阅读

在一棵深度为h的具有n个元素的二叉排序树,查找所有元素的最长查找长度为h。

从具有n个结点的二叉搜索树中查找一个元素时,在平均情况下的时间复杂性大致为O(log2n)。

从具有n个结点的二叉搜索树中查找一个元素时,在最坏情况下的时间复杂性为O(n)。

扩展资料:

二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

(1)若左子树不空,则左子树上所有节点的值均小于它的根节点的值;

(2)若右子树不空,则右子树上所有节点的值均大于它的根节点的值;

(3)左、右子树也分别为二叉排序树;

(4)没有键值相等的节点。

参考资料来源:百度百科-二叉排序树

声明:你问我答网所有作品(图文、音视频)均由用户自行上传分享,仅供网友学习交流。若您的权利被侵害,请联系fangmu6661024@163.com