Welcome to ShenZhenJia Knowledge Sharing Community for programmer and developer-Open, Learning and Share
menu search
person
Welcome To Ask or Share your Answers For Others

Categories

How to merge two binary search trees maintaining the property of BST?

If we decide to take each element from a tree and insert it into the other, the complexity of this method would be O(n1 * log(n2)), where n1 is the number of nodes of the tree (say T1), which we have splitted, and n2 is the number of nodes of the other tree (say T2). After this operation only one BST has n1 + n2 nodes.

My question is: can we do any better than O(n1 * log(n2))?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
thumb_up_alt 0 like thumb_down_alt 0 dislike
269 views
Welcome To Ask or Share your Answers For Others

1 Answer

Naaff's answer with a little more details:

  • Flattening a BST into a sorted list is O(N)
    • It's just "in-order" iteration on the whole tree.
    • Doing it for both is O(n1+n2)
  • Merging two sorted lists is into one sorted list is O(n1+n2).
    • Keep pointers to the heads of both lists
    • Pick the smaller head and advance its pointer
    • This is how the merge of merge-sort works
  • Creating a perfectly balanced BST from a sorted list is O(N)
    • See code snippet below for algorithm[1]
    • In our case the sorted list is of size n1+n2. so O(n1+n2)
    • The resulting tree would be the conceptual BST of binary searching the list

Three steps of O(n1+n2) result in O(n1+n2)

For n1 and n2 of the same order of magnitude, that's better than O(n1 * log(n2))

[1] Algorithm for creating a balanced BST from a sorted list (in Python):

def create_balanced_search_tree(iterator, n):
    if n == 0:
        return None
    n_left = n//2
    n_right = n - 1 - n_left
    left = create_balanced_search_tree(iterator, n_left)
    node = iterator.next()
    right = create_balanced_search_tree(iterator, n_right)
    return {'left': left, 'node': node, 'right': right}

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
thumb_up_alt 0 like thumb_down_alt 0 dislike
Welcome to ShenZhenJia Knowledge Sharing Community for programmer and developer-Open, Learning and Share
...