j*****k 发帖数: 1198 | 1 Eg: BST1 B1, BST2 B2.
Choose the root which has bigger value to be the new BST's root,
then insert each node of the other BST into the new BST. If B1
has m nodes, B2 has n modes, it takes O(mn). That's not good. Is
there other more efficient way? | e***r 发帖数: 68 | 2 According to :
Joining of two BSTs at Page552:
Program 12.23 Joining of two BSTs
If either BST is empty, the other is the result. Otherwise, we combine the
two BSTs by (arbitrarily) choosing the root of the first as the root, root
inserting that root into the second, then (recursively) combining the pair
of left subtrees and the pair of right subtrees.
private Node joinR(Node a, Node b)
{ if (b == null) return a;
if (a == null) return b;
insertT(b, a.item); //把a插入到b |
|