分割二叉搜索树 [英] Split a binary search Tree

问题描述

给定一个BST树，我们必须根据输入（N）将其分解为两个子树，其中subtree1由小于或等于N的所有节点组成，而subtree2由所有小于或等于N的节点组成大于N。

Given a BST tree, we have to break the tree depending on the input(N), into two subtrees, where subtree1 consists of all the nodes, which are less than or equal to N and subtree2 consists of all the nodes which are greater than N.

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

输出：

       50
      /                               
     40          
   /    \         
 30     45


     60

    /

   55

     \

       58

我想出了以下算法，但无法正常工作：

I have come up with following algorithm but its not working correctly:

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;


}

推荐答案

您不需要 root2 参数，因为那是函数的 result ，无论传递什么值都将被覆盖。

You would not need the root2 argument, since that is the result of the function, and whatever value would be passed would be overwritten anyway.

通常，分割算法不仅需要切割边缘（制作两棵树），而且还需要在切割树的更深层重复此操作，因为

The algorithm to split would in general not only need to cut an edge (making two trees), but also repeat this at deeper levels of the cut-off tree, since there may be subtrees there that should be attached at the place the cut-off happened.

例如，如果您的树看起来像这样：

For instance, if your tree looks like this:

                              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 ，那么两棵树看起来像这样：

And you want to cut with k = 11, then the two trees would look like this:

               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。这可以重复几次，并且对应于在树中找到目标值（位置）的侧向切换次数（在左右之间）。

Note how there are several edges that were cut and replaced: 16-8 is replaced with 16-12, and 8-12 is replaced with 8-10. This can repeat several times, and corresponds to the number side-switches (between left and right) one has to make to find the (place for the) target value in the tree.

建议的代码：

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;
}

查看它在复制

这篇关于分割二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！