一个关于插入时的问题

回复帖子

@低熵体 2019-02-12 20:26 回复

插入时我将插入的节点size设置为1了,不是应该会通过update将路径上所有节点size都+1吗,为什么还要自己增加1?(见注释部分)

    void insert(int &p, int val) {
        if (p == 0) {
            p = ++size;
            treap[p].val = val;
            treap[p].key = qrand();
            treap[p].size = 1;
            return;
        }
        //treap[p].size++;

        if (val >= treap[p].val) insert(treap[p].right, val);
        else insert(treap[p].left, val);

        if (treap[p].left != 0 && treap[p].key > treap[treap[p].left].key) rightRorate(p);
        if (treap[p].right != 0 && treap[p].key > treap[treap[p].right].key) leftRorate(p);

        update(p); 
    }
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。