关于Treap堆性质的问题
查看原帖
关于Treap堆性质的问题
65743
滑稽的小宫楼主2020/12/23 16:32

如果在递归的时候旋转:(借用题解rk2的代码)

void insert(int &id,int v){//id依然是引用,在新建节点时可以体现
	if(!id){
		id = New(v);//若节点为空,则新建一个节点
		return ;
		}
	if(v == val[id])cnt[id]++;//若节点已存在,则副本数++;
	else{//要满足BST性质,小于插到左边,大于插到右边
		int d = v < val[id] ? 0 : 1;//这个d是方向的意思,按照BST的性质,小于本节点则向左,大于向右
		insert(ch[id][d],v);//递归实现
		if(dat[id] < dat[ch[id][d]])Rotate(id,d ^ 1);//(参考一下图)与左节点交换右旋,与右节点交换左旋
		}
	pushup(id);//现在更新一下本节点的信息
	}

那么旋转过程中似乎不能保证优先级的大顶堆性质吧?

因为旋转的话原子节点的孩子会变成原父节点的节点,但只有原父节点比原子节点小的时候会旋转,这时候原父节点有可能比原子节点的孩子的优先级小,就会导致最后父节点比子节点小的情况

而且这个是递归实现的,处理完当前节点以后不会把它的子节点处理,所以这个错误会一直保留下去

如果这样不能保证的话,有没有别的办法可以保证?

2020/12/23 16:32
加载中...