在具有n个结点的二叉排序树上插入一个结点时，其时间复杂度是多少

Question

如题所述

Answer 1

最差情况下是O(n) 如果是最一般最基础的二叉树的话，因为深度不平衡，所以会发展成单链的形状,就是一条线 n个点那么深，如果是深度平衡的二叉树 o(logn)。

因为插入的时候需要先查找插入的位置，而查找插入的位置，需要的时间就是log2n。

扩展资料：

①结点：包含一个数据元素及若干指向子树分支的信息。

②结点的度：一个结点拥有子树的数目称为结点的度。

③叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。

④分支结点：也称为非终端结点，度不为零的结点称为非终端结点。

参考资料来源：百度百科-二叉树

Answer 2

在具有n个结点的二叉排序树上插入一个结点时，其时间复杂度是O(n) ，如果是最一般最基础的二叉树的话，因为深度不平衡，所以会发展成单链的形状，就是一条线n个点那么深。

若根结点的关键字值等于查找的关键字，成功。否则，若小于根结点的关键字值，递归查左子树。若大于根结点的关键字值，递归查右子树。若子树为空，查找不成功。

扩展资料

插入算法：

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

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

本回答被网友采纳

Answer 3

最差情况下是O(n) 如果是最一般最基础的二叉树的话, 因为深度不平衡,所以会发展成单链的形状,就是一条线 n个点那么深
如果是深度平衡的二叉树 o(logn)本回答被提问者采纳