如何在AVL树中找到节点的等级？

Question

我需要实现两个排名查询 [rank(k)和select(r)]。但在开始之前，我需要弄清楚这两个函数是如何工作的。

据我所知，rank(k)返回给定 key 的等级k，并select(r)返回给定 rank 的键r。

所以我的问题是：

1.) 如何计算 AVL（自平衡 BST）中节点的等级？

2.) 是否可能有多个键具有相同的等级？如果是这样，什么会select(r)回来？

我将包含一个示例 AVL 树，如果它有助于回答问题，您可以参考它。

谢谢！

Answer 1

你的问题实际上可以归结为：“对于 AVL 树，术语‘等级’通常是如何定义的？” （可能还有“选择”通常是如何定义的）。

至少正如我所看到的术语，“排名”是指树中节点之间的位置——即，其左侧有多少个节点。通常会给您一个指向节点（或者可能是键值）的指针，并且您需要计算其左侧的节点数。

“选择”基本上是相反的——你被赋予了一个特定的等级，并且需要检索指向指定节点的指针（或该节点的键）。

两个注意事项：首先，由于这些都不会修改树，所以使用什么形式的平衡（例如，AVL 与红/黑）没有真正的区别；就此而言，一棵根本没有平衡的树也是等效的。其次，如果您需要频繁执行此操作，则可以通过向每个节点添加一个额外的字段来记录其左侧有多少个节点，从而显着提高速度。