Вычисление ранга узла в двоичном дереве поиска

Question

Если каждый узел в дереве двоичного поиска сохраняет свой вес (количество узлов в его поддереве), то какой будет эффективный метод вычисления ранга данного узла (его индекс в отсортированном списке), когда я ищу его в дереве?

Answer 1

Начните ранг в ноль. По мере того, как двоичный поиск переходит из корня, добавьте размеры всех левых поддеревьев, которые просканирует поиск, включая левое поддерево найденного узла.

I.e., когда поиск идет слева (от родительского до левого ребенка), он не обнаруживает новых значений меньше, чем найденный объект, поэтому ранжирование остается неизменным. Когда он идет правильно, родительский плюс все узлы в левом поддереве меньше, чем найденный элемент, поэтому добавьте один плюс размер левого поддерева. Когда он находит искомый элемент. любые элементы в левом поддереве узла, содержащего элемент, меньше его, поэтому добавьте его в ранг.

Сведя все это вместе:

int rank_of(NODE *tree, int val) { 
    int rank = 0; 
    while (tree) { 
    if (val < tree->val) // move to left subtree 
     tree = tree->left; 
    else if (val > tree->val) { 
     rank += 1 + size(tree->left); 
     tree = tree->right; 
    } 
    else 
     return rank + size(tree->left); 
    } 
    return NOT_FOUND; // not found 
} 

Это возвращает ранг с нуля. Если вам нужно 1-based, то инициализировать rank до 1 вместо 0.

Answer 2

Поскольку каждый узел имеет поле хранить свой вес, то сначала вы должны реализовать размер вызова метода(), который возвращает количество узлов в substree узла в:

private int size(Node x) 
{ 
if (x == null) return 0; 
else return x.N; 
} 

затем вычислить ранг заданных узел легко

public int rank(Node key) 
{ return rank(key,root) } 

    private int rank(Node key,Node root) 
    { 
     if root == null 
      return 0; 
     int cmp = key.compareTo(root); 
// key are smaller than root, then the rank in the whole tree 
// is equal to the rank in the left subtree of the root. 
     if (cmp < 0) { 
      return rank(key, root.left) 
     } 
//key are bigger than root,the the rank in the whole tree is equal 
// to the size of subtree of the root plus 1 (the root) plus the rank 
//in the right sub tree of the root. 
     else if(cmp > 0){ 
      return size(root.left) + 1 + rank(key,root.right); 
     } 
// key equals to the root, the rank is the size of left subtree of the root 
     else return size(root.left); 
    } 

Answer 3

Зависит от реализации BST, но я считаю, что вы можете решить ее рекурсивно.

public int rank(Key key){ 
    return rank(root, key); 
} 

private int rank(Node n, Key key){ 
    int count = 0; 
    if (n == null)return 0; 
    if (key.compareTo(n.key) > 0) count++; 
    return count + rank(n.left, key) + rank(n.right, key); 
}