新增网站备案,天河建设网站专家,网络运营推广是做什么的,电脑网站建设服务器好了我就很愉快的回来补坑了~ Treap也是一种平衡树#xff0c;它较普通二叉查找树而言#xff0c;每个节点被赋予了一个新的属性#xff1a;优先级#xff08;没错就是类似优先队列的优先#xff09;#xff0c;对于Treap中的每个结点#xff0c;除了它的权值满足二叉查… 好了我就很愉快的回来补坑了~ Treap也是一种平衡树它较普通二叉查找树而言每个节点被赋予了一个新的属性优先级没错就是类似优先队列的优先对于Treap中的每个结点除了它的权值满足二叉查找树的性质外它的优先级还满足堆性质也就是结点的优先级小于它所有孩子的优先级。 换句话说从权值上看Treap是一个二叉查找树从优先级上看Treap是一个堆。所以我们发现Treap其实可以看做是TreeHeap。 我们发现普通BST会不平衡是因为有序的数据会使查找路径退化成链而随机数据使其退化的概率非常小。因此我们在Treap中赋予的这个优先级的值采用随机生成的办法这样Treap的结构就趋于平衡了。如果脸黑怎么办逃 如果我们假设所有点的权值与优先级都互不相同那么Treap的形态是唯一确定的。 我们考虑在所有结点中找到优先级最小的点则它一定是Treap的根而权值小于它的点会在根的左子树大于它的点会在根的右子树这就可以递归下去构建Treap。这个建立过程与快速排序类似因此Treap的期望深度与快排的期望递归层数一样都是O(log n)的。 为了使Treap满足性质有时我们不可避免地要对结构进行调整而我们调整的方式是旋转。在维护Treap的过程中我们会出现两种旋转左旋与右旋。 左旋一个子树这个子树的根节点为x则旋转后会把x变为这个子树的新根的左儿子x的右儿子会成为子树新的根。右旋一个子树这个子树的根节点为x则旋转后会把x变为这个子树的新根的右儿子x的右儿子会成为子树新的根。详细图解见Splay传送门https://blog.csdn.net/g21glf/article/details/82931486。 显然旋转后这个Treap仍然满足权值的BST性质因此这个旋转操作就保证了若我们满足了BST性质那么不满足堆性质的部分我们可以通过旋转使其满足堆性质。旋转的意义也正是在此使不满足堆序的两个节点通过调整位置重新满足堆序而不改变BST性质。 Treap的各种操作与BST无异唯一有些不同的就是插入操作。我们从根节点开始插入如果要插入的值小于当前节点的值那么我们要在当前节点的左子树进行插入否则我们要在当前节点的右子树进行插入 若当前节点是个空节点 则我们在这个位置上新建一个节点。插入之后新建的这个节点可能会使Treap不满足堆性质那么我们就通过旋转操作不断调整这个步骤可以通过递归来实现。 在删除时我们首先需要在Treap上走找到需要删除的那个节点接着我们可以利用旋转操作不停调整需要删除的这个节点在树中的位置。若删除节点为叶节点那么我们可以直接删除 若它只有一个儿子 那么我们直接让那个儿子代替这个被删除的节点即可。 否则若删除节点左儿子的优先级小于删除节点右儿子优先级那么我们对删除节点进行右旋让左儿子成为新的子树的根反之同理。直到它变为前两种情况。 由于Treap的树高是期望O(log n)的所以它各个操作的期望复杂度也是O(log n)。 【贴代码~】 更新
void update(const int k)
{tr[k].sizetr[lc[k]].sizetr[rc[k]].size;
} 右旋
void zig(int k)
{int ylc[k];lc[k]rc[y];rc[y]k;size[y]size[k];update(k);ky;
}
左旋
void zag(int k)
{int yrc[k];rc[k]lc[y];lc[y]k;size[y]size[k];update(k);ky;
} 插入
void insert(int k,int key)
{if(!k){kpool;key[k]key;pri[k]rand();cnt[k]size[k]1;lc[k]rc[k]0;return ;}elsesize[k];if(k.keykey)cnt[k];else{if(keyk.key){insert(lc[k],key);if(pri[lc[k]]pri[k])zig(k);}else{insert(rc[k],key);if(pri[rc[k]]pri[k])zag(k);}}return ;
} 删除
void del(int k,int key)
{if(k.keykey){if(cnt[k]1)cnt[k]--,size[k]--;else{if(!lc[k]||!rc[k])klc[k]rc[k];else{if(pri[lc[k]]pri[rc[k]])zig(k),del(k,key);elsezag(k),del(k,key);}}}else--size[k];if(keyk.key)del(lc[k],key);elsedel(rc[k],key);return ;
} 询问优先级
int queryrank(const int key)
{int xrt,res0;while(x){if(keykey[x])return ressize[lc[x]]1;if(keykey[x])xlc[x];elseressize[lc[x]]cnt[x],xrc[x];}return res;
} 寻找第k大
int querykth(int k)
{int xrt;while(x){if(size[lc[x]]ksize[lc[x]]size[x]k)return x.key;if(size[lc[x]]k)xlc[x];elsek-size[lc[x]]cnt[x],xrc[x];}return 0;
} 求前驱
int querypre(const int k)
{int xrt,res-INF;while(x){if(key[x]key)reskey[x],xrc[x];elsexlc[x];}return res;
}
求后继
int querysuf(const int k)
{int xrt,resINF;while(x){if(key[x]key)reskey[x],xlc[x];elsexrc[x];}return res;
} 以上就是个人关于Treap的一些感悟后续会补坑。。。 转载于:https://www.cnblogs.com/Ishtar/p/10010833.html
