splay

既然你看到这里，相信你一定了解splay的思想。 splay按照STB的性质进行维护，并将其均摊复杂度降为了log(n) splay既然被称为序列之王，如此优秀的算法想必还有其他应用。 Splay的区间操作 我们知道查找树的中序遍历是一个有序的序列。这个时候我们不采用查找树左小右大的规则，而是把它的 ......

「学习笔记」平衡树基础：Splay 和 Treap 点击查看目录 知识点 平衡树概述 二叉搜索树（BST）的简单定义： 根节点的左子树权值 $<$ 根节点权值 $<$ 根节点的右子树权值； 左子树和右子树均为二叉搜索树。 这样的数据结构可以维护一个集合的以下操作： 查找最小/最大值； 插入一个元素； ......