给定n个节点的平衡二叉搜索树,每个节点的值是整数。给定一个整数,在树中找出与该整数最接近的节点的最小算法复杂度是()
A.Θ(logn)
B.Θ(n^2)
C.Θ(nlogn)
D.Θ(n)
E.Θ(1)
F.Θ(log*n)
正确答案是 A
平衡二叉树的时间复杂度是log(n),如果二叉树的元素个数为n,那么不管是对树进行插入节点、查找、删除节点都是log(n)次循环调用就可以了。它的时间复杂度相对于其他数据结构如数组等是最优的。
枚举最后在树中找到的树和已知数的关系,一种是大于,一种是小于等于,这两种情况分别可以做到0(lgn)
题目中的logn都是只以2为底的对数,,,,在二叉排序树中查找一个数时,当这棵二叉树是平衡二叉树时,可以获得最佳的时间复杂度logn,,,题目想问的是二叉排序树中时间复杂度最小是多少吧,,,另外,如果要找最接近x的整数,是先找到第一个比x大的结点k,然后拿 k 跟 k的父亲结点 跟 x做比较,,,
我也觉得要O(n)啊,考虑这样一种情况,根节点是10,左子树为1,右子树为100,现在找11,最接近的明显是1,但是用二叉查找树的算法就会找到100。所以只能一个个的遍历看。
请写出以下代码执行输出:(构造函数、静态块执行顺序)
使用js实现数组的快速排序
叉树前序遍历的递归和非递归实现?
某公园内有个奇怪的摊主小周,他只在星期一、星期二、星期三、星期五和星期六工作,而且他只出售4种商品:玩具汽车、充气气球、橡皮泥和遥控飞机。<
枚举最后在树中找到的树和已知数的关系,一种是大于,一种是小于等于,这两种情况分别可以做到0(lgn)
题目中的logn都是只以2为底的对数,,,,
在二叉排序树中查找一个数时,当这棵二叉树是平衡二叉树时,可以获得最佳的时间复杂度logn,,,
题目想问的是二叉排序树中时间复杂度最小是多少吧,,,
另外,如果要找最接近x的整数,是先找到第一个比x大的结点k,然后拿 k 跟 k的父亲结点 跟 x做比较,,,
我也觉得要O(n)啊,考虑这样一种情况,根节点是10,左子树为1,右子树为100,现在找11,最接近的明显是1,但是用二叉查找树的算法就会找到100。所以只能一个个的遍历看。