我需要实现两个排名查询 [rank(k) 和 select(r)]。但在开始之前，我需要弄清楚这两个函数是如何工作的。
据我所知，rank(k) 返回给定键 k 的排名，而 select(r) 返回给定等级 r 的键。
所以我的问题是:
1.) 如何计算 AVL(自平衡 BST)中节点的等级？
2.) 是否可能有多个键具有相同的等级？如果是这样，select(r) 会返回什么？
我将包含一个示例 AVL 树，如果它有助于回答问题，您可以引用它。
谢谢!
最佳答案
您的问题实际上可以归结为:“术语‘等级’通常是如何针对 AVL 树定义的？” (可能还有“select”通常是如何定义的)。
至少正如我所看到的那样，“排名”是指树中节点之间的位置——即它左边有多少个节点。您通常会得到一个指向节点的指针(或者可能是一个键值)，您需要计算其左侧的节点数。
“选择”基本上是相反的——你被赋予了一个特定的等级，并且需要检索一个指向指定节点(或该节点的键)的指针。
两个注意事项:首先，由于这些都不会修改树，因此使用何种形式的平衡并没有真正的区别(例如，AVL 与红色/黑色)；就此而言，一棵完全没有平衡的树也是等价的。其次，如果您需要经常这样做，您可以通过向每个节点添加一个额外字段来记录其左侧有多少节点，从而显着提高速度。
关于algorithm - 如何找到 AVL 树中节点的等级？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5137741/