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}
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…