5

2つのランククエリ[rank(k)とselect(r)]を実装する必要があります。しかし、これを始める前に、2つの機能がどのように機能するかを理解する必要があります。

私の知る限り、指定さrank(k)れたキーのランクを返し、指定されたランクのキーkをselect(r)返しますr。

だから私の質問は：

1.）AVL（自己平衡BST）のノードのランクをどのように計算しますか？

2.）複数のキーが同じランクを持つことは可能ですか？もしそうなら、何が戻っselect(r)てきますか？

質問に答えるのに役立つ場合に参照できるサンプルAVLツリーを含めます。

ここに画像の説明を入力してください

ありがとう！

4

3 に答える 3

3

あなたの質問は、「AVLツリーに関して通常「ランク」という用語はどのように定義されているのか」ということになります。（そして、おそらく、'select'は通常どのように定義されていますか）。

少なくとも私が使用した用語を見たように、「ランク」はツリー内のノード間の位置、つまり左側にあるノードの数を意味します。通常、ノードへのポインター（またはおそらくキー値）が与えられ、その左側のノードの数を数える必要があります。

「選択」は基本的に反対です。特定のランクが与えられ、指定されたノード（またはそのノードのキー）へのポインターを取得する必要があります。

2つの注意：最初に、これらはどちらもツリーをまったく変更しないため、使用されるバランシングの形式（AVLと赤/黒など）に実際の違いはありません。さらに言えば、バランスがまったく取れていないツリーも同等です。次に、これを頻繁に行う必要がある場合は、各ノードにフィールドを追加して、左側にあるノードの数を記録することで、速度を大幅に向上させることができます。

于 2011-02-28T03:07:26.083 に答える
1

ランクは、左側のサブツリー内のノードの数に1を加えたものであり、ノードごとに計算されます。ランクは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));
        }
}
于 2013-08-30T09:13:58.860 に答える
0

これが私が書いたコードで、AVLツリーが特定の値のランクを取得するためにうまく機能しました。違いは、ノードをパラメーターとして使用し、キーをパラメーターとして使用したことです。これを独自の方法で変更できます。サンプルコード：

    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;
}

[注]ランクを0から開始する場合は、変数rank=0を初期化します。このコードを実行するには、countNodes（）メソッドを実装する必要があります。

于 2015-09-08T20:14:46.317 に答える