-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

请注意，rank 不返回条目（节点值），而是表示给定 Key 与候选节点左子树（二叉搜索树中节点的最左侧值）之间的比较的值。

它返回的值源于标准Comparable 接口的实现：如果第一个元素小于第二个元素，则为负整数，如果大于第二个元素，则为正，如果它们相等，则为 0。

在这种特殊情况下，返回的确切数字表示被比较的两个键之间的距离（差异），这对于使用比较结果的代码可能很有用——通常是排序算法。

于 2013-10-01T02:01:11.490 回答