有效地在二叉搜索树中寻找父母

Question

我正在尝试解决以下问题：

首先，我们有一个BST 与根0，没有别的。我们不加ň等给出的数字一个其中：

例如，我们不开始在树上添加n = 7个数字：
19 3 5 25 21 -4 2
在添加所有数字之后，目标是按照添加顺序找到每个节点的父级：
0 19 3 19 25 0 3

我的第一种方法是在添加节点的同时构建树并同时打印父节点：

    private static TreeNode treeInsert(TreeNode root, TreeNode newNode) {
    TreeNode y = null;
    TreeNode x = root;
    while (x != null) {
        y = x;
        if (newNode.key < x.key) x = x.left;
        else x = x.right;

    }
    newNode.parent = y;

    if (y == null) root = newNode;
    else if (newNode.key < y.key) y.left = newNode;
    else y.right = newNode;

    return newNode;

}

和这个辅助类：

class TreeNode {
    TreeNode left;
    TreeNode right;
    TreeNode parent;
    int key;

   public TreeNode(int key) {
        this.key = key;

   }

所以我可以找到父母。这里的问题是这个算法很慢！如果给定的数量太多，并且如果我们认为树不平衡，那么添加新节点可能会花费很多时间。这个问题的时间限制为1，由于我提到的原因，我超出了该限制。我不能平衡这棵树，因为父母改变了。但是也许有一种方法可以解决这个问题，而无需构建bst，而只专注于使用数字查找父母。

谢谢。

Answer 1

我们可以用段来表示现有的二叉搜索树。

假设我们已经添加了：

0, 21, 10, -4

所以，基本上，我们有这些部分[-4 0][0 10][10 21]

当我们添加一个新的数字时x，我们只需要找到这个数字如果落到哪个段即可。让我们说x = 3

所以，该段[0 10]=> 我们将其分解为[0 3][3 10]

接下来是确定该节点的父节点是什么。很简单，只需要跟踪稍后在段中添加的节点即可。在这种情况下，10肯定是加在0后面的，所以10应该是父级。

比方说

class Segment{
    int start, end, later;
}

因此，对于上面的序列，我们有段列表：

Segment (-4, 0, -4), Segment(0, 10, 10) , Segment (10, 21, 10)

如果 x = 11，则Segment (10, 21, 10)其父节点也将落入10。

添加后11，我们将得到段列表：

Segment (-4, 0, -4), Segment(0, 10, 10), Segment (10, 11 , 11) , Segment (11, 21, 11)

如果该数字不在任何段内，这种情况也应该很简单。我把这个案例留给读者自己去理解。

维护一个平衡的 BST 来存储段列表，我们可以获得 O(n log n) 的解决方案。