拆分二叉搜索树

Question

给定一个BST树,我们必须根据输入(N)将树分成两个子树,其中subtree1由所有节点组成,小于或等于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参数,因为那是函数的结果,无论如何都会覆盖传递的任何值.

分割算法通常不仅需要切割边缘(制作两棵树),而且还要在截止树的更深层次重复这一点,因为那里可能存在应该附加在切割位置的子树 - 发生了.

例如,如果您的树看起来像这样:

                              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上运行