使用特定方法拆分二叉树

Question

给定一棵二叉树，我必须返回一棵树，其中包含所有小于k、大于k的元素和一棵树，其中仅包含一个元素-k。允许使用的方法：删除节点-O（n）插入-O（n）查找-O（n）查找min-O（n）我假设这些方法的复杂性，因为在练习中没有写到树是平衡的。所需的复杂性-O（n）原始树必须保持其结构。我完全被卡住了。非常感谢任何帮助！

给定的树是二元搜索树，输出应该是二元搜索树。

Answer 1

我真的看不到一种简单有效的方法来与您提到的操作分离。但我认为，实现一个非常有效的分割相对容易。

如果树是平衡的，那么您可以在O（log n）中执行拆分，如果您定义了一个称为连接异的特殊操作。让我首先将join_ex（）定义为所讨论的操作：

Node * join_exclusive(Node *& ts, Node *& tg)
  {
    if (ts == NULL)
      return tg;

    if (tg == NULL)
      return ts;

    tg=.llink) = join_exclusive(ts->rlink, tg->llink);

    ts->rlink = tg;
    Node * ret_val = ts;
    ts = tg = NULL; // empty the trees

    return ret_val;
  }

假设您想从两个BST和tr构建一个新树，这样ts中的每个键都比tr中的每个键都少。

如果有两个排他树

然后可以看到如下所示：

请注意，如果为任何BST获取任何节点，则其子树满足此条件；左子树中的每个键都比右子树中的每个键都小。您可以基于join\u ex（）设计一个很好的删除算法。

现在我们准备好进行拆分操作：

void split_key_rec(Node * root, const key_type & key, Node *& ts, Node *& tg)
  {
    if (root == NULL)
      {
        ts = tg = NULL;
        return;
      }

    if (key < root->key)
      {
        split_key_rec(root->llink, key, ts, root->llink);         
        tg = root;
       }
     else
       {
         split_key_rec(root->rlink, key, root->rlink, tg)
         ts = root;
       }
  }

如果在此图中将根设置为T

然后可以看到拆分的图示：

split\u key\u rec（）。在操作结束时，ts包含键小于k的BST，tg是键大于或等于k的BST。

现在，为了完成您的需求，您可以调用split\u key\u rec（t，k，ts，tg），然后进入一个BST，所有键都小于k。几乎对称地，你进入一个BST，所有键都大于或等于k。因此，最后一件事是验证tg的根是否是k，如果是这种情况，则取消链接，并在ts、k和tg中得到结果（tg是没有k的树）。

如果原始树中有k，则tg的根将是k，而tg将没有剩下的子树。

Answer 2

本质上，您的目标是创建一个有效的BST，其中k是根节点；在这种情况下，左侧子树是包含所有小于k的元素的BST，右侧子树是包含所有大于k的元素的BST。

这可以通过一系列树旋转来实现：

• 首先，对值为k的节点进行O（n）搜索，构建其祖先到根节点的堆栈

每个旋转需要O（1）时间，所以这个算法终止于O（n）时间，因为最多有O（n）祖先，在平衡树中，算法需要O（log n）时间，尽管结果不是平衡树。

在您的问题中，您写道“插入”和“删除”操作需要O（n）时间，但这是您的假设，即问题中没有说明这些操作需要O（n）时间。如果您只操作您已经有指针的节点，那么基本操作需要O（1）时间。

如果要求不破坏原始树，那么您可以在O（n）时间内复制它。

Answer 3

我认为没有办法设计一个O（n）算法，给定的黑盒函数和它们的时间复杂性，因为它们只能被称为（最大）常数次数（如3次）以保持在O（n）约束内。

但如果允许使用基本的标准节点操作（通过左或右子级遍历，将左或右子级设置为给定子树）访问和创建BST，则可以执行以下操作：

创建三个将填充并返回的新空BST。将它们命名为左、中、右，其中第一个节点的所有值都小于k，第二个节点最多有一个节点（值为k），最后一个节点的所有值都小于k。填充左和右时，保持对最接近值k的节点的引用：在左中，该节点将是值最大的节点，在右中，该节点将是值最小的节点。

遵循以下步骤：

• 应用通常的二进制搜索，从根向值为k的节点移动

在最坏的情况下，对值为k的节点的搜索可能需要O（n），因为BST没有被赋予平衡。所有其他操作（在其中一个新BST中向特定节点添加子树）在恒定时间内运行，因此在最坏的情况下它们总共执行O（n）次。

如果给定的BST是平衡的（不一定是完美的，但与AVL规则类似），那么算法将在O（logn）时间内运行。然而，输出BST可能不平衡，并且可能违反AVL规则，因此需要旋转。

下面是一个JavaScript实现。当您运行此代码段时，测试用例将运行一个BST，该BST具有值为0的节点。。19（按随机顺序插入），k=10。输出将依次迭代三个创建的BST，以验证它们是否输出0。。9、10和11。。19分别为：

class Node {
    constructor(value, left=null, right=null) {
        this.value = value;
        this.left = left;
        this.right = right;
    }
    insert(value) { // Insert as a leaf, maintaining the BST property
        if (value < this.value) {
            if (this.left !== null) {
                return this.left.insert(value);
            }
            this.left = new Node(value);
            return this.left;
        } else {
            if (this.right !== null) {
                return this.right.insert(value);
            }
            this.right = new Node(value);
            return this.right;
        }
    }
    // Utility function to iterate the BST values in in-order sequence
    * [Symbol.iterator]() {
        if (this.left !== null) yield * this.left;
        yield this.value;
        if (this.right !== null) yield * this.right;
    }
}

// The main algorithm
function splitInThree(root, k) {
    let node = root;
    // Variables for the roots of the trees to return:
    let left = null;
    let mid = null;
    let right = null;
    // Reference to the nodes that are lexically closest to k:
    let next = null;
    let prev = null;

    while (node !== null) {
        // Create a copy of the current node
        newNode = new Node(node.value);
        if (k < node.value) {
            // All nodes at the right go with it, but it gets no left child at this stage
            newNode.right = node.right;
            // Merge this with the tree we are creating for nodes with value > k
            if (right === null) {
                right = newNode;
            } else {
                next.left = newNode;
            }
            next = newNode;
            node = node.left;
        } else if (k > node.value) {
            // All nodes at the left go with it, but it gets no right child at this stage
            newNode.left = node.left;
            // Merge this with the tree we are creating for nodes with value < k
            if (left === null) {
                left = newNode;
            } else {
                prev.right = newNode;
            }
            prev = newNode;
            node = node.right;
        } else {
            // Create the root-only tree for k
            mid = newNode;
            // The left subtree belongs in the left tree
            if (left === null) {
                left = node.left;
            } else {
                prev.right = node.left;
            }
            // ...and the right subtree in the right tree
            if (right === null) {
                right = node.right;
            } else {
                next.left = node.right;
            }
            // All nodes have been allocated to a target tree
            break;
        }
    }
    // return the three new trees:
    return [left, mid, right];
}

// === Test code for the algorithm ===

// Utility function
function shuffled(a) {
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]];
    }
    return a;
}

// Create a shuffled array of the integers 0...19
let arr = shuffled([...Array(20).keys()]);
// Insert these values into a new BST:
let root = new Node(arr.pop());
for (let val of arr) root.insert(val);

// Apply the algorithm with k=10
let [left, mid, right] = splitInThree(root, 10); 

// Print out the values from the three BSTs:
console.log(...left);  // 0..9
console.log(...mid);   // 10
console.log(...right); // 11..19