Question

二叉排序树在最坏的情况下查找最小值的时间复杂度是多少？

Answer 1

二叉排序树在最坏的情况下查找最小值的时间复杂度是O(n)。

一棵空树，或者是具有下列性质的二叉树：若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于它的根结点的值；左、右子树也分别为二叉排序树；没有键值相等的结点。

首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。

扩展资料：

与次优二叉树相对，二叉排序树作为一种动态树表，特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。

新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

Answer 2

O(n)，最坏时二叉排序树退化为单枝树，只能从根开始一层一个查找，实质变为顺序查找

追问

不是应该直接找出它的最左的子树就是最小值吗？如果没左子树那就应该找它对我根结点呗。 这样不就是O1吗？

追答

最坏的情况就是左边的一条单枝树，只有从根找到最左的才是最小值，不就是要将n个结点找完？！

追问

不可以直接取最左的元素吗？

追答

树形结构的查找除了B+树以外，一般不能取最左元素，都是从根开始才能提高查找效率

追问

哦哦。我理解了。谢谢大神阿。有序顺序表中如果安值查找一个一个的找最坏时间复杂度不是On吗？

追答

问题是有序顺序表做顺序查找纯属于没事找事，不然总是原地转圈，O(n!)也是可能的

追问

线索二叉树中的每一个结点都可以在相应的遍历下找到其后继结点。 这句好对吗？