为 AVL 容器设计一个恒定时间的 begin() 中序迭代器函数

Question

美好的一天，

如果想要设计一个基于 (AVL) 树的符合标准的容器，其迭代器函数必须是常数时间。正如该讨论中所指出的，搜索树中的查找往往是对数的。

假设传统的树类设置，其中作为私有成员，我们有根节点和大小。 Node 也是按常规设计的（具有三个指针，左-右-父），并且迭代器是惰性的并存储节点指针。然后，为了提供

begin()

，必须从根到最左边，这在最坏的情况下需要 O(logn) 时间。所以我的问题是：

• 您认为满足树

  begin()

  复杂性要求的最佳方法是什么？

我正在考虑保留另一个私有节点指针成员，该成员将在每次修改后更新，但在我看来，还有更优化解决方案的空间。

• 对于

  end()

  ，我可以只返回一个

  nullptr

  吗？

Answer 1

可以实现哨兵节点，它代表

end()

迭代器指向的位置，以便始终满足以下要求：

• 根元素是哨兵节点的左子节点，后者是根元素的父节点；
• 哨兵节点的父节点是它自己；
• 哨兵节点的左指针指向最左边的元素。

设计逻辑基于这样的思想：哨兵节点代表开始之前和结束之后的位置。这样就可以创建一个循环序列：如果实现了指向最右边元素的迭代器或者将指向最左边元素的迭代器递减，那么它就会落在哨兵节点上。

它允许以恒定时间访问

begin()

和

end()

位置，而最右边元素和

end()

位置之间的遍历是对数时间。

此外，这种设计允许以简单的方式实现迭代器的递增和递减操作，而不需要执行特定的检查。

示例：

Node* inc(Node* x)
{
  if(x->right != nullptr){
    x = x->right;
    while(x->left != nullptr)
      x = x->left;
  }
  else{
    while(x == x->parent->right)
      x = x->parent;
    x = x->parent;
  }
  return x;
}

Node* dec(Node* x)
{
  if(x->left != nullptr){
    x = x->left;
    while(x->right != nullptr)
      x = x->right;
  }
  else{
    while(x == x->parent->left)
      x = x->parent;
    x = x->parent;
  }
  return x;
}