CS-Notes icon indicating copy to clipboard operation
CS-Notes copied to clipboard

二叉查找树rank方法错误

Open byedo opened this issue 2 years ago • 0 comments

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

private int rank(Key key, Node x) {
    if (x == null)
        return 0;
    int cmp = key.compareTo(x.key);
    if (cmp == 0)
        return size(x.left);
    else if (cmp < 0)
        return rank(key, x.left);
    else
        return 1 + size(x.left) + rank(key, x.right);
}

其中
if (x == null) return 0;

应该返回-1;否则和树中rank为0的第一个节点无法区分

byedo avatar Jun 27 '22 23:06 byedo