UC知道创建平衡二叉树需要的时间
来源：百度知道 编辑：UC知道 时间：2024/09/21 22:53:09
10.A1,A2,A3是三个n大小的已排序实数集，创建A1UA2UA3的平衡二叉树需要的时间是
A.O(n2) B. O(n(log(n))) C. O(n) D. O(log(n))
请高人给出答案并给予解释
A.O(n2) B. O(n(log(n))) C. O(n) D. O(log(n))
请高人给出答案并给予解释
根据平衡二叉树的性质(左子树都比根小,右子树都比根大),所以插入时比较的时间复杂度就是树的层数,n个结点应该是log(n)级别的,选D吧
创建一棵树,那么必然要访问所有的结点啊,所以至少是O(n)级别的,D不可能是对的.
第二个，这是书上的答案