Skip to main content

splay tree

· 5 min read
ayanami

splay tree​

  1. Counting Binary Tree

ref: 卡特兰数（Catalan number）（二） - 知乎 (zhihu.com), stackoverflow 专栏

给定节点数 n，二叉树的种类数？ 卡塔兰数 C(n).

C(n)=1n+1∗C2nnC(n) = \frac{1}{n+1} * C_{2n}^{n}

直观理解？换个角度，自底向上

总共 n 个节点每次链接两个形成一个新节点，有多少种连法

等效于对序列 A1A2A3A4...AnA_1A_2A_3A_4...A_n 加括号，有几种不同的加法

等效于括号问题（定义卡特兰数的原始问题）：

一个合法的括号序列定义（非递归）为：

  • 闭合（左括号数=右括号数）
  • 从左到右，任意时刻左括号数>=右括号数

递归为：

  • （a）是括号序列
  • A，B 是括号序列，（AB）也是括号序列

由非递归定义可以得到一些等价问题：

  • 一个 n*n 方格，不能过对角线，从左下出发，只能向右或者上走，终点在右上角（把 n 格子的 n+1 条线看成 n 元素序列的 n+1 个可以插入括号的点，向右走看成是左括号，向上走看成右括号）

  • 一个二进制序列，任意时刻累计 0 的数目小于等于 1 的数目，最后 0 数要等于 1 数

  • 一个允许{push,pop}的队列，n 次操作之后队列为空

设这样的数目为 C(n)

递推式子：C(n)=C(0)C(n)+C(1)C(n−1)+...+C(n)C(0)C(n) = C(0)C(n) + C(1)C(n-1)+...+C(n)C(0) （直观理解: C(0)C(n)C(0)C(n)是左子树 0 个，右子树 n 个，以此类推）

  1. splay tree

ref: 深入理解伸展树(splay tree) - 知乎 (zhihu.com)， Splay Tree Visualzation (usfca.edu)

试图对 AVL 树进行优化

由局部性原理，想到能否将最近访问的元素（容易再次被访问）旋转到根上去方便下次访问

朴素想法: 一直向上，和父节点旋转！zig-zag

问题：如果是“一”字形，在将最底层的节点旋转到顶部的同时，路径上的节点也被旋转下来了，树的整体形态没变，最坏的时候每一次调整都是 O(n)

伸展树改进：如果是“之”字形，和朴素想法一样；如果是“一字形”，先旋转父节点和祖先节点（如果有，没有就算了），再将查询节点向上旋转

可以证明这样的优化会让最坏情况的平均时间复杂度降到 log(n)

这是自底向上的方法，要求从根开始查询时维护 O(n)的查询栈，还有不直观的自顶向下方法，优化了空间效率

伸展树的应用：

  • 优化对 AVL 树的连续查询
  • 区间操作：由于伸展（zig-zag 等）不影响树的性质（在这里重要的是中序遍历的序列不变（要是旋转改变了二叉查找树的结构那不就寄了）），所以当我们用一棵二叉查找树代表一个 comparable 的元素序列时，可以利用伸展变换执行一些操作：
    • 插入区间：在第 p 个元素和第 p+1 个元素之间插入区间：将 p 向上伸展到根，再将 p+1 向上伸展到根的右子树，插入区间的根就是 p+1 的左子树
    • 删除区间：删除[m,n]区间只需要将第 m-1 个元素伸展到根，再将 n+1 个元素伸展到根的右子树，之后删掉它的左子树就行
    • 翻转区间：反转区间[m,n]内的元素，注意到逆序的递归表述： R(AmB)=R(B)mR(A)R(AmB) = R(B)mR(A), 操作为：1.将元素 m-1 伸展到根 2.将元素 n+1 伸展到根的右子树，此时[m,n]就是它的左子树 3.维护一个 reverse 标记，标记为 1 则交换左右子树，并将该标记下放给左右子树的根，将[m,n]的根的 reverse 标记置 1
Loading Comments...