java - split 二叉树

Question

我正在尝试在Java中的根处分割二叉搜索树。我不知道该怎么做。递归调用是最让我困惑的。下面是我得到的伪代码。当x大于T(要 split 的树)时，我要调用split(R.key, R.right, L, R)吗？我走在正确的轨道上吗？这是项目中唯一让我困惑的功能。提前致谢。

 void split( int x, bst T, bst L, bst R) /* assuming x is not in T */
 {
    if T is null, make L and R null
    else if x < T.key
      set R = T /* all keys at the root and in right subtree are greater than x */
      recursively split T's left subtree into L and R’s left subtree
         /* some keys in T's left subtree are greater than x, other may be less than x */

    else /* x is greater than T.key */
      set L = T
      recursively split T's right subtree into L's right subtree and R
 }

Answer 1

重要的是，您必须有一个二叉有序树，使得每个子树的 Left < Root < Right。此外，左子树中不存在节点 > Root 的节点，右子树中不存在节点 < Root 的节点。不需要平衡(所有子树的深度相同 +- 1)。

这就像双语搜索；如果要分割的值大于当前的根，则可以确定它大于左子树中的所有节点(因为前面的限制)。因此，为了搜索树中哪个节点更大，您只需要检查右侧的节点即可。同样，如果分割依据的值小于root的值，则也小于右子树所有节点的值，必须在左树中更细地检查。

为了看得清楚，我建议你画这棵树(这里没有间距)

8

4 12

3 6 10 14

1 2 5 7 9 11 13 15

，设置几个样本分割值，并标记哪些节点将保留在新树中。