高效合并两个二叉搜索树并创建一个 BST

Question

假设我必须通过合并两个 BST（其中 T1 和 T2 都是 BST）来创建一个 BST，这样 T1 的节点比 T2 多，并且使用此算法，对于 T2 中的每个节点，从 T2 中删除节点并将节点的值插入到T1，最后返回T1。阅读其他帖子，该算法的运行时间似乎是 O(m * log(n))，其中 n 是 T1 中的节点数，m 是 T2 中的节点数。但我并不能 100% 确定为什么这会导致运行时间复杂度。谁能向我解释为什么它是 O(m * log(n))？我的第一个猜测是 O(m*n) 因为在迭代中，我们必须从 T2 中删除一个节点，这会导致运行时间为 O(m) ，并且以下插入的运行时间是 O(n) 所以应该'是不是O(m*n)？

Answer 1

你说的是二叉搜索树，不是平衡二叉搜索树。并且，将值插入 BST （二叉搜索树） 的时间复杂度为：

• 最佳案例：

  O(log(n))

  。 （当它完全平衡时）。
• 最坏情况：

  O(n)

  。

此后，我们将所有元素从

T2

（最初有 m 个元素） 移动到

T1

（最初有 n 个元素）。因此，总体时间复杂度为：

• 最佳案例：

  O(m.log(n))

  。
• 最坏情况：

  O(m.n)

  。

然而，实际上我们可以考虑平均时间复杂度，该复杂度介于最佳情况和最坏情况之间。

编辑：考虑一个澄清的案例。

T2            T1     # initial BST
#             #
8             3
 \             \
  9             4
   \             \ 
    10            5
     \             \
      11            6
                     \ 
                      7                       
m = 4      &   n = 5      (initial values).

Moving the 8 to the T1 from T2  
T2            T1    
#             #
9             3
 \             \
  10            4
   \             \ 
    11            5
                   \
                    6
                     \ 
                      7
                       \
                        8

Steps taken to insert 8 into its right place = 5 or (n)
Total Steps taken   = 5 or (n)

Moving the 9 to the T1 from T2  
T2            T1    
#             #
10            3
 \             \
  11            4
                 \ 
                  5
                   \
                    6
                     \ 
                      7
                       \
                        8
                         \
                          9

Steps taken to insert 9 into its right place = 6 or (n+1)
Total Steps taken   = 5+6  or (n) + (n+1)

Moving the 10 to the T1 from T2 
T2            T1    
#             #
11            3
               \
                4
                 \ 
                  5
                   \
                    6
                     \ 
                      7
                       \
                        8
                         \
                          9
                           \
                           10

Steps taken to insert 10 into its right place = 7 (n+2)
Total Steps taken   = 5+6+7 or (n) + (n+1) + (n+2) 

Moving the 11 to the T1 from T2 
T2            T1    
#             #
NULL          3
               \
                4
                 \ 
                  5
                   \
                    6
                     \ 
                      7
                       \
                        8
                         \
                          9
                           \
                           10
                             \
                             11

Steps taken to insert 11 into its right place = 8 (n+3)
Total Steps taken   = 5+6+7+8 or (n) + (n+1) + (n+2) + (n+3)

因此，通过观察我们可以说，在最坏的情况下，将

m

个值从 T2 移动到 T1 所需的步数：

=> (n) + (n+1) + (n+2) + .......   + (n + (m-1))
=> (n+n+n+...m times) + (1+2+3+....+(m-1))
=> (n.m) + (m.(m-1))/2

从那时起，

n > m

。因此，我们可以忽略加号后的第二个方程。

因此，时间复杂度：

O(n.m)

。