java - 拆分二叉搜索树

Question

给定一棵 BST 树，我们必须根据输入 (N) 将树分解为两棵子树，其中子树 1 包含所有小于或等于 N 的节点，子树 2 包含所有小于或等于 N 的节点均大于 N。

          50
     /        \
     40         60
  /    \        /
 30     45     55
                 \
                  58

输出:

       50
      /                               
     40          
   /    \         
 30     45


     60

    /

   55

     \

       58

我提出了以下算法，但它无法正常工作:

static Node splitTree(Node root, Node root2, int k){
    if(root == null)
        return null;

    while(root != null){
        if(root.data > k)
            root = root.left;
        else if(root.data < k)
            root = root.right;
        else
        {
            root2=root.right;
            root.right=null;
            break;
        }

    }
        return root2;


}

Answer 1

您不需要 root2 参数，因为它是函数的结果，无论传递什么值都会被覆盖。

split 算法通常不仅需要切割一条边(制作两棵树)，而且还需要在切割树的更深层重复此操作，因为那里可能有应该附加在该位置的子树截止发生了。

例如，如果你的树看起来像这样:

                              16  
               +---------------+---------------+
               8                              24
       +-------+-------+               +-------+-------+
       4              12              20              28
   +---+---+       +---+---+       +---+---+       +---+---+
   2       6      10      14      18      22      26      30
 +-+-+   +-+-+   +-+-+   +-+-+   +-+-+   +-+-+   +-+-+   +-+-+
 1   3   5   7   9  11  13  15  17  19  21  23  25  27  29  31

而你想用k = 11进行切割，那么两棵树将如下所示:

               8
       +-------+-------+
       4              10
   +---+---+       +---+---+
   2       6       9      11
 +-+-+   +-+-+     
 1   3   5   7      

                              16  
               +---------------+---------------+
              12                              24
               +-------+               +-------+-------+
                      14              20              28
                   +---+---+       +---+---+       +---+---+
                  13      15      18      22      26      30
                                 +-+-+   +-+-+   +-+-+   +-+-+
                                17  19  21  23  25  27  29  31

注意有几条边被切割和替换:16-8 被 16-12 替换，8-12 被 8-10 替换。这可以重复几次，并且对应于在树中找到目标值(位置)所必须进行的侧向开关(左右之间)的数量。

建议代码:

static void setChild(Node node, boolean toLeft, Node child){
    // Assign child node to the indicated direction: left or right
    if (toLeft) {
        node.left = child;
    } else {
        node.right = child;
    }
}

static Node splitTree(Node root, int k){
    Node root2 = null;
    Node parent1 = null;
    Node parent2 = null;
    // Determine at which side of the root we will travel
    boolean toLeft = root != null && k < root.data;

    while (root != null) {
        while (root != null && (k < root.data) == toLeft) {
            parent1 = root;
            root = toLeft ? root.left : root.right;
        }
        setChild(parent1, toLeft, null); // Cut out the edge. root is now detached
        toLeft = !toLeft; // toggle direction
        if (root2 == null) {
            root2 = root; // This is the root of the other tree.
        } else if (parent2 != null) {
            setChild(parent2, toLeft, root); // re-attach the detached subtree
        }
        parent2 = parent1;
        parent1 = null;
    }
    return root2;
}

查看它在 repl.it 上运行