[总结] 平衡树总结

1. treap

• 众所周知, treap = tree + heap
  也就是 treap 是具有堆性质的平衡二叉树(BST), 而堆性质的维护就靠一个随机值和旋转操作. 可以是小根堆也可以是大根堆.

---

• 在代码实现上, 左旋和右旋有太多的相似处, 可以用一个带旋转方向参数的 rotate 操作来完成.

---

• 模板
  loading…

---

2. splay

• 和 treap 比较起来, splay 多的就是伸展(splay)操作.

---

• 关于伸展操作
  
  • 两种实现方式 : 自顶向下和自底向上.
    自底向上的 splay 我是参考的 HZWER, 需要使用fa数组记录当前结点的父结点. 比较方便的是可以直接通过这个fa数组发现从一个结点走到任意已知结点的路径. 于是就诞生了自底向上的splay. 正因为这种特性, 这种伸展方式可以适应任何题目.
  • 自顶向下的 splay 可以看《训练指南》, 刘汝佳的代码. 比较简洁高效. 我是把指针改成了数组, 不习惯指针的写法, 主要是不知道怎么调试.
    自顶向下就需要知道你想 splay 的结点的排名. 那么有的题目比如 书架 那个题, 直接告诉你哪个结点编号, 但它是第几个结点不知道, 这样就只能用第一种自底向上的splay了.
    另外splay可以一次旋转两回也可以旋转一回. 旋转一回的方法比较简单, 整个过程相当于先找到第 k 个结点, 再递归自底向上旋转到目标结点. 转两回的参考《训练指南》.

---

• 模板
  loading…

---