看二叉查找树的时候看到put方法:
public void put(Key key, Value val) {
if (key == null) throw new NullPointerException("first argument to put() is null");
if (val == null) {
delete(key);
return;
}
root = put(root, key, val);
assert check();
}
private Node put(Node x, Key key, Value val) {
//if key存在于以x为结点的子树中则更新它的值
//then 将以key和val为键值的新结点插入到该子树中
if (x == null) return new Node(key, val, 1);
int cmp = key.compareTo(x.key);
//比它小往左边走
if (cmp < 0) x.left = put(x.left, key, val);
//不然往右边走
else if (cmp > 0) x.right = put(x.right, key, val);
//找到了就赋新的值
else x.val = val;
x.size = 1 + size(x.left) + size(x.right);//为什么要+1???
return x;
}
为什么要x.size = 1 + size(x.left) + size(x.right);
??进入这里的条件是如果该结已存在就赋予新的值吧?那么仅仅是更新一个值为什么要增加1个size呢?
註解寫得有問題, 對二元查找樹來說put其實是插入的意思。
如果cmp 0, 則左子樹或右子樹的會多一個node, 那麼size會加1
如果cmp==0,相當於加一個重複節點,一般情況下,並不會在樹中追加一個重複結點,而是在當前node.size上加1