如何合并两个二叉搜索树并保持 BST 的属性？如果我们决定从一棵树中取出每个元素并将其插入到另一棵树中，则此方法的复杂度将为 O(n1 * log(...
如何合并两棵二叉搜索树并保持 BST 的属性？
如果我们决定从一棵树中取出每个元素并将其插入到另一棵树中，则此方法的复杂度将是 O(n1 * log(n2)) ， n1 其中 是已拆分的 T1 树（假设 ）的节点数 n2 是另一棵树（假设 ）的节点数 T2 。 经过此操作后，只有一个 BST 有 n1 + n2 节点。
我的问题是：我们能做得比 O(n1 * log(n2)) 更好吗？
即使我们将任何未排序列表合并到 BST 中，O(n1 * log(n2)) 也是平均情况。我们没有利用列表是排序列表或 BST 的事实。
根据我假设一个 BST 有 n1 个元素，另一个有 n2 个元素。现在将一个 BST 转换为 O(n1) 中的排序数组列表 L1。
合并 BST(BST，数组)
if (Array.size == 0) return BSTif(Array.size ==1)将元素插入BST。return BST;
找到数组中左元素 < BST.rootnode 且右元素 >=BST.rootnode 的索引，说 Index.if(BST.rootNode.leftNode ==null ) //即没有左节点{将从 Index 到 0 的整个数组插入到 BST 的左侧，}else{合并 BST(BST.leftNode, Array{0 到 Index})}
if(BST.rootNode.rightNode ==null)//即没有右节点{将数组从 Index 到 Array.size 全部插入到 BST 的右侧 }else{ Merged BST(BST.rightNode, Array{Index to Array.size})}
返回 BST。
由于每次我们对数组和 BST 进行分区来处理子问题，因此该算法所花费的时间将比 O(n1 * log(n2)) 要少。
