采用边查找边插入的方式,类似重新建立一个一维数组时间复杂度=O(n)因为深度不庆知平衡,所以会发展成单链的形状,就是一条线 n个点那么深。
二叉排序树是查找过程中,当树中不存在关键字等zhi于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点,并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右结点。
因此二叉排序树插入时间复杂度最大为O(n)。若是二叉排序树比较平衡,其时间复亏晌杂度下降,最小的时间复杂度为O(logn)。
扩展资料:
①结点:包含一个数据元销差锋素及若干指向子树分支的信息。
②结点的度:一个结点拥有子树的数目称为结点的度。
③叶子结点:也称为终端结点,没有子树的结点或者度为零的结点。
④分支结点:也称为非终端结点,度不为零的结点称为非终端结点。
⑤树的度:树中所有结点的度的最大值。
参考资料来源:百度百科-二叉树
Pi(n-i+1)指的是你插入i元素以后,需要移动的元素的个数,然后你可以想一下,梁悉饥在第一个元素后面插入元素i需要移动n个元素,在第二个元橡返素后面插入元素i需要陆消移动元素(n-1)个元素,依此论推,在第n个元素后面插入元素i需要移动1个元素,这是一个等差数列,首项为n,公差为1,最后一项是1,你求和以后需要除以(n+1)就算出来结果了,忘采纳,不懂可以加我QQ327579459,我可以给你讲讲。欢迎分享,转载请注明来源:内存溢出
评论列表(0条)