相关疑难解决方法(0)

如何合并两个保持BST属性的二叉搜索树？

如果我们决定从树上取每个元素,并将其插入到另一个中,这种方法的复杂性将是O(n1 * log(n2))其中n1的(比如树的节点数量T1),这是我们分裂,并且n2是节点的数量另一棵树(比如说T2).在此操作之后,只有一个BST具有n1 + n2节点.

我的问题是:我们能比O更好(n1*log(n2))吗？

我有一个段树,它包含一系列数字的数据(这里选择的数据结构).这是代码:

class SegmentTree:
    def __init__(self, N):
        def _init(b, e):
            if b is e:
                data = foo() # No dependency
                return Node(b, e, data, None, None)
            else:
                mid = (b + e ) / 2

                L = _init(b, mid)
                R = _init(mid + 1, e)

                data = foo() #Data depends on L and R

                return Node(b, e, data, L, R)

        self.root = _init(1, N)

对于大约300的N,超过最大递归深度超出错误时,这会失败.有没有办法迭代地而不是递归地创建树？