CS-Notes
CS-Notes copied to clipboard
二叉查找树rank方法错误
@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的第一个节点无法区分