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

Question

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

据我所知，rank(k)返回给定键的排名k，并select(r)返回给定排名的键r。

所以我的问题是：

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

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

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

谢谢！

Answer 1

您的问题实际上归结为：“关于 AVL 树，‘等级’一词通常是如何定义的？” （并且，可能，“选择”通常也是如何定义的）。

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

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

两个注意事项：首先，由于这些都不会修改树，因此使用何种形式的平衡并没有真正的区别（例如，AVL 与红/黑）；就此而言，一棵完全没有平衡的树也是等效的。其次，如果您需要经常这样做，您可以通过向每个节点添加一个额外的字段来记录其左侧有多少个节点，从而大大提高速度。

Answer 2

Rank 是左子树中的节点数加一，是针对每个节点计算的。我相信等级不是 AVL 树特有的概念——它可以为任何二叉树计算。

选择与排名正好相反。给出了一个排名，您必须返回一个与该排名匹配的节点。

以下代码将执行排名计算：

void InitRank(struct TreeNode *Node)
{
        if(!Node)
        {
                return;
        }
        else
        {       Node->rank = 1 + NumeberofNodeInTree(Node->LChild);
                InitRank(Node->LChild);
                InitRank(Node->RChild);
        }

}


int NumeberofNodeInTree(struct TreeNode *Node)
{
        if(!Node)
        {
                return 0;
        }
        else
        {
                  return(1+NumeberofNodeInTree(Node->LChild)+NumeberofNodeInTree(Node->RChild));
        }
}

Answer 3

这是我为 AVL Tree 编写并运行良好的代码，以获得特定值的排名。区别只是你使用了一个节点作为参数，而我使用了一个键作为参数。您可以按照自己的方式进行修改。示例代码：

    public int rank(int data){
    return rank(data,root);
}

private int rank(int data, AVLNode r){
    int rank=1;
    while(r != null){
        if(data<r.data)
            r = r.left;
        else if(data > r.data){
            rank += 1+ countNodes(r.left);
            r = r.right;
        }
        else{
            r.rank=rank+countNodes(r.left);
            return r.rank;
        }
    }
    return 0;
}

[NB] 如果你想从 0 开始你的排名，那么初始化变量 rank=0。您绝对应该实现方法 countNodes() 来执行此代码。