понимание этой рекурсивной функции в дереве BST

Question

Мне сложно понять этот код для ранжирования узлов по размеру. Ранг возвращает размер всех узлов меньше, чем ключ.

http://algs4.cs.princeton.edu/32bst/BST.java.html

как результат, возвращаемый для ранга (ключ, x.left) ???

код:

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

    // Number of keys in the subtree less than key. 
    private int rank(Key key, Node x) { 
     if (x == null) return 0; 
     int cmp = key.compareTo(x.key); 
     if  (cmp < 0) return rank(key, x.left); 
     else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right); 
     else    return size(x.left); 
    } 


// is the symbol table empty? 
    public boolean isEmpty() { 
     return size() == 0; 
    } 

    // return number of key-value pairs in BST 
    public int size() { 
     return size(root); 
    } 

// return number of key-value pairs in BST rooted at x 
private int size(Node x) { 
    if (x == null) return 0; 
    else return x.N; 
} 

Answer 1

Обратите внимание, что ранг не возвращает записи (значение узла), а, значение, которое представляет сравнение между данным ключом и что кандидата левого поддерева узла (самый левый значение для узла в binary search tree).

Значение, которое оно возвращает, является результатом реализации стандарта Comparable interface: отрицательное целое число, если первый элемент меньше второго, положительный, если он больше, 0, если они равны.

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