二叉排序树在最坏的情况下查找最小值的时间复杂度是多少?
发布网友
发布时间：2022-04-28 10:32
共2个回答
热心网友
时间：2023-09-26 12:34
二叉排序树在最坏的情况下查找最小值的时间复杂度是O(n)。
一棵空树，或者是具有下列性质的二叉树：若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于它的根结点的值；左、右子树也分别为二叉排序树；没有键值相等的结点。
首先执行查找算法，找出被插结点的父亲结点。判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。若二叉树为空。则首先单独生成根结点。
扩展资料：
与次优二叉树相对，二叉排序树作为一种动态树表，特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。
新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
热心网友
时间：2023-09-26 12:35
O(n)，最坏时二叉排序树退化为单枝树，只能从根开始一层一个查找，实质变为顺序查找
