我知道搜索一棵有n个节点的平衡树是O(logN),但我甚至不知道为什么问题中所说的树也是一棵平衡二叉树。
好吧,就像你说的,一个有k个节点的平衡BST的查找时间是O(log k)。所以我们要做的就是插入n2n 对于k,看看我们得到了什么。
对数(n2n) = log n + log 2n = log n + n log 2 = O(n)。
对数(n2n)
= log n + log 2n
= log n + n log 2
= O(n)。
这也是有道理的,因为一棵树上的节点数量是指数级的,用对数时间算法打出的树应该是线性时间。