Как найти ранг узла в дереве AVL?

Question

Мне нужно реализовать два ранговых запроса [rank(k) и select(r)].Но прежде чем я смогу начать с этого, мне нужно выяснить, как работают две функции.

Насколько я знаю, rank(k) возвращает ранг данного ключа k, а select(r) возвращает ключ данного ранга r.

Итак, мои вопросыявляются:

1.) Как рассчитать ранг узла в AVL (самобалансирующееся BST)?

2.) Возможно ли, чтобы несколько ключей имели одинаковыйранг?И если да, то что вы вернете select(r)?

Я собираюсь включить пример дерева AVL, к которому вы можете обратиться, если оно поможет ответить на вопрос.

Спасибо!

Answer 1

Ваш вопрос действительно сводится к следующему: «Как обычно определяется термин« ранг »по отношению к дереву AVL?» (и, возможно, как обычно определяется 'select').

По крайней мере, как я видел используемый термин, «ранг» означает положение среди узлов в дереве - то есть, сколько узлов находится слева от него. Обычно вам дают указатель на узел (или, возможно, значение ключа), и вам нужно посчитать количество узлов слева от него.

«Выбор» в основном противоположен - вам присвоен определенный ранг, и вам нужно получить указатель на указанный узел (или ключ для этого узла).

Два примечания: во-первых, поскольку ни один из них вообще не изменяет дерево, не имеет никакого значения, какая форма балансировки используется (например, AVL или красный / черный); в этом отношении дерево без балансировки также эквивалентно. Во-вторых, если вам нужно делать это часто, вы можете значительно улучшить скорость, добавив дополнительное поле к каждому узлу, записывая, сколько узлов слева от него.

Answer 2

Ранг - это количество узлов в левом поддереве плюс один и рассчитывается для каждого узла.Я считаю, что ранг не является концепцией, специфичной для деревьев 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

Вот что я сделал. В моей программе ранг элемента определяется как 1+ (нет элементов больше, чем этот элемент). Здесь вы можете заметить, что элемент не обязательно должен присутствовать в дереве.

Алгоритм нахождения ранга:

1.В древовидной структуре следите за количеством элементов в поддереве, включая корень. Таким образом, верхушка дерева содержит все элементы дерева.

2.Сравните элемент с узлом, если он меньше, чем узел, то элементов (1 + нет элементов в правом дочернем элементе) больше, чем ключевой элемент. Добавьте его к общему количеству и рекурсивно ищите элемент в левом потомке.

3.Если элемент больше корневого узла, то просто рекурсивно ищите элемент в правом дочернем элементе (не нужно ничего добавлять, поскольку мы пренебрегаем левым деревом, в котором все элементы меньше заданного ключа )

4.Заключить алгоритм, когда вы обнаружите, что элемент достигнут нуля.

Данная программа не возвращает элементов больше указанного ключа. 1+ возвращаемое значение - ранг.

фрагмент кода:

int AVLUtils::rank(Node *root,long long val)
  {
    int n_ele_greater=0;
    int rank =0;

    if(root == NULL)
    return 0;
   if(val < root->key)
     {
    n_ele_greater = 1+this->n_elements(root->right_child)+this->rank(root->left_child,val);
     }
   else if(val > root->key)
     {
    n_ele_greater=this->rank(root->right_child,val);
    }

    else if(val == root->key)
    {
    return(this->n_elements(root->right_child));
    }
    return(n_ele_greater);
   }

Надеюсь, это поможет:)

Answer 4

Вот код, который я написал и отлично работал для 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;
}

[N.B] Если вы хотите начать свой ранг с 0, то инициализируйте переменную rank = 0. Вы определенно должны были реализовать метод countNodes () для выполнения этого кода.