526互联

平衡树Splay学习笔记 & 洛谷 P3369 【模板】普通平衡树

发布时间 2023-09-01 00:05:56作者: 尹昱钦

传送门

平衡树Splay

Splay本质上是一个二叉查找树。
满足左子树<根<右子树。
核心操作splay就是随机选择一个点向上旋转，使整棵树尽量平衡。
采用双旋（即判断父亲和儿子是否同时作为左儿子或右儿子，若是，则先旋父亲再旋儿子）。
熟能生巧，多练吧。