瞭解BST樹中的遞歸函數

Question

我很難理解這個代碼按大小對節點排序。 Rank返回小於密鑰的所有節點的大小。

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。

在這種特殊情況下，返回的確切數字表示所比較的兩個鍵之間的距離（差異），這對於使用比較結果的代碼可能非常有用 - 通常是排序算法。