java - 关于二叉查找树的put方法
大家讲道理
大家讲道理 2017-04-18 10:05:44
0
1
649

看二叉查找树的时候看到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呢?

大家讲道理
大家讲道理

光阴似箭催人老,日月如移越少年。

全部回复(1)
刘奇

注释写得有问题, 对于二叉查找树来说put其实是插入的意思。

  1. 如果cmp < 0 || cmp > 0, 则左子树或者右子树的会多一个node, 那么size会加1

  2. 如果cmp==0,相当于加一个重复节点,一般情况下,并不会在树中追加一个重复结点,而是在当前node.size上加1

热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责声明 Sitemap
PHP中文网:公益在线PHP培训,帮助PHP学习者快速成长!