一个关于插入时的问题

回复帖子

@dishangti 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); 
    }
@EternalAlexander 2019-02-12 20:28 回复

递归写法按理可以不加
这个地方你需要把update放在rotate的前面

@dishangti 2019-02-12 20:30 回复

@EternalAlexander 是因为旋转树之前节点已经插入了节点但是没有更新,旋转时进行更新导致结果不正确吗?