统计给定范围内AVL树的节点数

Question

我需要编写一个 C++ 函数，给定一个范围 (a,b)，returns AVL 树中在给定范围内的节点数，特别是在 log( n) 时间复杂度。如果需要，我可以向树的节点添加更多字段。

我应该指出，a,b 不一定会出现在树中。例如，如果树的节点是：1,2,5,7,9,10，那么运行使用参数 (3,9] 的函数应该 return 3.

我应该使用哪种算法来实现这个？

Answer 1

这是一个著名的问题 - dynamic order statistcs by tree augmentation。

您基本上需要扩充节点，以便在查看子指针时，您知道在时间 O(1) 时子树的子树中有多少个子节点。很容易看出，这可以在不影响复杂性的情况下完成。

一旦你有了它，你就可以通过执行从节点到根的两次遍历来回答任何查询（在这个和那个之间，inclusive/exclusive - 所有可能性）。确切的遍历取决于细节（例如检查 C++ 中的函数 lower_bound 和 upper_bound）。

Answer 2

首先你可以实现按键拆分操作。也就是说，给定一棵树，执行 split(tree, key, ts, tg) 将密钥拆分为两棵树； ts 包含小于 key 的键； t2 大于或等于的。这个操作可以在 O(lg n) 中完成。

然后，通过两次拆分，第一次在 a 上，第二次在 b 上，您可以在 O(lg n) 中获得所需的子集范围。

拆分可以实现如下（伪代码）：

void split(Node * root, const Key & key, Node *& ts, Node *& tg) noexcept
  {
    if (root == Node::NullPtr)
      return;

    if (key < KEY(root))
      {
         Node * r = RLINK(root), * tgaux = Node::NullPtr;
         split(LLINK(root), key, ts, tgaux);         
         insert(tgaux, root); // insert root in tgaux
         tg = join_ex(tgaux, r);
       }
    else 
      {   // ket greater or equal than key to tg
        Node * l = LLINK(root), *tsaux = Node::NullPtr;
        split(RLINK(root), key, tsaux, tg));
        insert(tsaux, root); // insert root in tsaux
        ts = join_ex(l, tsaux);
       }
  }

join_ex(t1, t2)连接了两棵独占树；也就是说，t1 的所有键都小于树 t2 的任何键。这种连接可以在 O(lg n) 中以类似于 Knuth 在 TAOCP V3 6.2.3 中描述的连接的方式实现。

Grosso modo 如果要加入 l 和 r，则假设 h(l) > h(r)。您从 r 中删除最左边的节点（最小值）。让 j 这个 加入节点 和 r' 结果树 (r - j)。现在你从 r 的右侧下降，直到到达节点 p，使得 h(p) - h(r') 等于 0 或 1。此时你做

并且您将 p 视为已插入。

编辑：我对这个问题的解释是错误的。对不起。没看出来是算不算算集合。以下是我的回答。我不会删除我写的东西，因为我认为它仍然有用。

Ami Tavory 是对的。

如果你使用扩展树，即在每个节点中存储子树基数，那么你可以很容易地计算出一个键的中序位置。我通常调用这个操作position(key)。如果 key 不在集合中，那么它将 returns 插入到树中时 key 的位置。

根的中序位置是左树的基数。

现在，为了计算 [a, b) 集的基数，您执行 position(b) - position(a)。如果树中不存在 a 或 b，您可能需要进行一些调整。不过基本上是这样。

position(key) 我认为 "naturally" 很简单。假设使用 COUNT(node):

访问节点基数

long position(Node * root, const Key & key) noexcept
{
  if (r == Node::NullPtr)
    return 0;

  if (key < KEY(root)) 
    return position(LLINK(r), key, p);
  else if (KEY(r) < key) 
    return position(RLINK(r), key) + COUNT(LLINK(r)) + 1;
  else // the root contains key
    return COUNT(LLINK(r));
}

由于avl树是平衡的，position需要O(lg n)。所以两次调用需要 O(lg n)。非递归版本很简单。

希望你知道原谅我的错误

统计给定范围内AVL树的节点数

Count the number of nodes in an AVL tree in a given range

c++

algorithm

tree