上回书说到：平衡树。 伸展树简介An Indroduction to Splay 由 和 于 年提出的一种数据结构。后者证明了路径压缩的并查集的时间复杂度、求解 强连通分量的其中一种方法也以他的名字命名。 是一种二叉搜索树，与平衡树类似，它也可以通过“旋转”进行自我平衡。通过“伸展操作Splay”来将某个节点旋转至根节点来满足二叉搜索树的性质。能够在均摊 的时间复杂度内完成节点的...

书接上回：二叉搜索树 BST。二叉搜索树是本文所讲平衡树的必要前置知识。 平衡树简介Brief Introduction of Treap 平衡树是为了解决普通二叉搜索树（）时间复杂度退化现象而产生的一种复杂度更为稳定的数据结构（但它仍然属于 的一个子类，因此具备 的所有性质）。在极端的数据面前（具备单调性的数据）， 会退化成为一个 的算法。但是通过引入随机化参数，在数学期望的控制下就...

二叉搜索树简介A Brief Introduction 二叉搜索树Binary Search Tree是一种特殊的二叉树，它有如下的性质： 左儿子（如果存在）的节点值比当前节点的值要小 右儿子（如果存在）的节点值比当前节点的值更大 某个节点的左/右子树（如果存在）也为一个二叉搜索树 中序遍历得到的节点值序列是不下降的（属于是推论） 二叉搜索树是很多重要树形数据结构的理论基础，例如树堆Tr...