병합 이진 탐색 트리

Question

두 트리의 요소가 모두 두 번째 트리의 요소보다 낮다는 것을 알고 두 개의 BST를 병합하는 효율적인 방법을 찾고 있습니다. 일부 병합 방법을 보았지만이 기능이 없으면 알고리즘을 단순화해야한다고 생각합니다.

아이디어가 있으십니까?

Answer 1

나무가 균형을하지 않거나 결과는 아주 쉽게 그 균형을 안 경우 : 첫 번째 BST가 두 번째보다 크기가 큰 경우

는

without loss of generality - let the first BST be smaller (in size) than the second. 
1. Find the highest element in the first BST - this is done by following the right son while it is still available. Let the value be x, and the node be v 
2. Remove this item (v) from the first tree 
3. Create a new Root with value x, let this new root be r 
4. set r.left = tree1.root, r.right = tree2.root 

(*) 단지의 과정을 반복 두 번째 트리에서 가장 작은 노드로 v을 찾습니다.

(*) 복잡성 O(min{|T1|,|T2|}) 최악의 경우 (나무가 매우 inbalanced 경우 가장 높은 요소를 발견), 및 O(log(min{|T1|,|T2|})) 평균 경우입니다 - 나무가 비교적 균형합니다.