在二叉搜索树中高效地查找父节点

Question

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

首先，我们有一个根为0且没有其他节点的二叉搜索树。 然后，我们添加n个给定数字，例如a，其中：

例如，我们开始向树中添加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，只需专注于使用数字查找父级。 谢谢。

- FrastoFresto

---

你能分享一下问题链接吗？ - nice_dev

你可能在意欲表达“现在”时，使用了否定的词语。请将每个句子的首字母大写。 - greybeard

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)的解决方案。

- Pham Trung

---

为什么*a₁比a₂晚添加意味着a₂不是a₁的后代*？在问题的示例中，每个值都添加到具有现有根值0的树中，在父项列表中出现两次。 - greybeard

Answer 2

在二叉搜索树中插入节点时，可能会发生以下两种情况之一：

1. 新节点是“比它自己大的最小节点”的左子节点
2. 新节点是“小于或等于它自己的最大节点”的右子节点

为了找到比给定数字大的最小数字，我们可以维护一个排序容器并执行二分查找，这需要 O(logn) 的时间复杂度。因此，以下实现的时间复杂度为 O(nlogn)，其中 n 是树中节点的数量。

#include <iostream>
#include <set>
#include <string>
#include <unordered_set>


int main(int argc, char* argv[]) {
  constexpr int kRoot = 0;

  std::set<int> numbers;
  std::unordered_set<int> left_occupied_numbers;
  numbers.insert(kRoot);

  int num_input, current;
  std::cin >> num_input;

  for (int i = 0; i < num_input; ++i) {
    std::cin >> current;
    // upper_bound will provide the smallest number that is
    // strictly greater to than the current number.
    auto it = numbers.upper_bound(current);
    if (it != numbers.end() &&
        left_occupied_numbers.find(*it) == left_occupied_numbers.end()) {
      // Left child at this iterator is still empty,
      // so the current number can be inserted here.
      // Mark the left child as taken.
      left_occupied_numbers.insert(*it);
    } else {
      // Decrementing the iterator gives the largest number that is
      // smaller than (or equal to, if all number are not distinct)
      // the current number, so the current number can be inserted
      // as the right child of this number.
      --it;
    }
    // This iterator is where current number's parent is.
    std::cout << *it;
    if (i < num_input - 1) {
      std::cout << " ";
    }
    numbers.insert(current);
  }

  std::cout << std::endl;
  return 0;
}

示例运行：

> ./run
7
19 3 5 25 21 -4 2
0 19 3 19 25 0 3

- heothesennoc

Answer 3

您是正确的，构建树可能会很慢。如果树变得退化（即它有长而深的链），那么构建树将需要 O(n²) 的时间复杂度。这里提供了一种 O(n log n) 的方法。

考虑在插入 19 和 3 后的树：

0
 \
  \
   19
  /
 3

我们可以预测要插入的值x的父节点：

• 如果 x < 0，那么其父节点将是0;
• 如果 0 < x < 3，那么其父节点将是3（左子节点，但这不重要）;
• 如果 3 < x < 19，那么其父节点将是3（右子节点）;
• 如果 x > 19，那么其父节点将是19。

让我们将其可视化为：

values         0       3                     19
parents   (0)     (3)             (3)             (19)

当我们插入5时，我们会查找它并打印出其父节点（即3），然后更新我们的数据。

values         0       3          5          19
parents   (0)     (3)       (5)        (5)        (19)

有什么改变吗？

• 我们将5插入到其排序位置（在3和19之间）；
• 我们将对应父节点位置的3更改为5；
• 我们在第一个5旁边插入了另一个5。

您可以将顶部行视为键，将底部行视为值/有效负载。因此，您需要一种允许 O(log n) 插入和查找的结构。我个人喜欢 跳跃表 来完成这项工作，但任何形式的 平衡树 也可以使用。

- Cătălin Frâncu