-1

サイズによるノードのランキングについて、このコードを理解するのに苦労しています。Rank は、キーより小さいすべてのノードのサイズを返します。

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

rank(key, 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;
}
4

1 に答える 1

0

ランクはエントリ (ノード値) を返すのではなく、指定されたキーと候補ノードの左サブツリー (二分探索ツリー内のノードの最も左の値) のキーとの比較を表す値を返すことに注意してください。

返される値は、標準のComparable インターフェイスの実装に由来します。最初の要素が 2 番目より小さい場合は負の整数、大きい場合は正の整数、等しい場合は 0 です。

この特定のケースでは、返される正確な数値は、比較される両方のキー間の距離 (差) を示します。これは、比較結果 (通常はソート アルゴリズム) を使用するコードに役立つ場合があります。

于 2013-10-01T02:01:11.490 に答える