gyro永不抽风！ - 二叉树
type: channel
link: https://gallery.gyrojeff.top/index.php/tag/二叉树/
items: Splay 初探
items: 初探二叉搜索树

Splay 初探
type: item
date: 2022-03-19T08:30:04+00:00
description: Preface BST 的问题 解决方案之一——Splay 右旋 (Zig)、左旋 (Zag) 如何判断是要左旋还是右旋？ Splay 操作【上旋 (旋转到根)】 代码层面的数据结构维护 一些辅助函数 旋转的代码实现 Splay 的代码实现 插入操作 两种查询寻 删除操作、寻找前继、寻找后继 代码 Reference Preface 昨天写了最普通的 BST，今天来写一下 Splay。注意：这一节建立在已经能够理解普通的二叉搜索树的基础上，若有疑问，见上一篇博客。 BST 的问题 首先我们要意识到，最普通的 BST 可能会退化成链。通过插入大小递减的数，我们就可以轻易地让二叉树退化成链，从而是复杂度达到最坏复杂度 $O(n)$。 解决方案之一——Splay Splay 可以解决这样的问题，最然最坏复杂度也是 $O(n)$，但是可以证明，连续的 $m$ 个操作的复杂可以降到 $O(m\log n)$，即均摊复杂度为 $O(\log n)$。这里不给出 Splay 复杂度的证明，可由势能分析证明。我们主要讲一下 Splay 的思想。 Splay 的核心在于，每次操作之后，我们都将该操作对应的节点旋转到根的位置。注意：这里使用了 旋转 一词。接下来我们来解释旋转的过程。 右旋 (Zig)、左旋 (Zag) 要解释「旋转到根」，我们先要引入两个概念：左旋与右旋。 为什么叫右旋和左旋？因为我们是把位置较低的元素 (x / y) 向 (右 / 左) 旋转，达到了较高的位置。 注意：在这张图中，我画了两个 R，意思是 x / y 无论是 R 的左儿子还是右儿子，这个旋转的结果都是不变的。 接下来我们来证明右旋和左旋不会改变二叉树的性质，能让其依旧满足二叉搜索树的定义。 证明： 由于二叉搜索树是递归定义的，所以我们只需要证明图中出现的有限个节点的大小关系保持不变即可。 左图的关系： $$ A < x < B $$ $$ x < y < C $$ $$ B < y $$ 右图的关系： $$ A < x < y $$ $$ B < y < C $$ $$ B > x $$ 不难发现，通过代数变换，就能证明这两个不等式组是完全等价的。 如何判断是要左旋还是右旋？ 答案很简单，如果我们要往上旋转的儿子是左儿子，那就右旋，如果是右儿子，那就左旋。 Splay 操作【上旋 (旋转到根)】 我们之前已经介绍了左旋与右旋，其可以把一个节点 x 降低一个深度 (上移一个单位)。那如果我们想要把一个节点上移使之成为根节点，那我们就需要进行若干个左旋和右旋操作来达成这一问题。 接下来我们来介绍迭代过程中的三种大类型。 (1) 该节点的父亲就是根节点：旋一次，结束迭代 (2) 根节点不是父亲，并且父亲的儿子类型和该节点的儿子类型相同【比方说：父亲是祖父的左儿子，这个节点也是父亲的左儿子】 这种情况下，先旋一次父亲，再旋一次自身 (3) 根节点不是父亲，并且父亲的儿子类型和该节点的儿子类型不同【比方说：父亲是祖父的左儿子，这个节点也是父亲的右儿子】 这种情况下，直接自旋两次即可。 有一张图可以很好地解释 (2) 和 (3)，分别对应图中的 Case 1 和 Case 2 代码层面的数据结构维护 为了方便维护，我们定义如下 struct 以及数据: int cnt = 0; // 维护节点数 int rt = 0; // 根的节点编号 struct node { int val, // 这个节点所代表的值 cnt, // 这个值出现的次数 sz, // 以这个节点为根的子树的大小 fa, // 父节点编号 ch[2]; // ch[0] 左儿子；ch[1] 右儿子 } t[maxn]; 一些辅助函数 // 调试用，遍历 Splay void print(int u) { if (!u) return; print(t[u].ch[0]); for (int i = 0; i < t[u].cnt; i ++) cout << t[u].val << ' '; print(t[u].ch[1]); } // 更新 u 的 size（重新计算） void update_sz(int u) { t[u].sz = t[t[u].ch[0]].sz + t[u].cnt + t[t[u].ch[1]].sz; } // 查询 u 是其父亲的左儿子还是右儿子 int identify(int u) { return t[t[u].fa].ch[1] == u; } // 清除编号为 u 的所有值（在删除节点的时候会用到） void clear(int u) { t[u] = (node) {0, 0, 0, 0, 0, 0}; } // let u be fa's [ch] so…

初探二叉搜索树
type: item
date: 2022-03-18T16:31:02+00:00
description: 引言 二叉搜索树其实非常常用，但是......我好像从来没写过，一直用的 STL 的模板。为一手写过的二叉树可能就是堆了吧。趁着可靠大先辈学的时候稍微看了一下，大致理解了。（这么晚看这个真的该自裁） Reference 由于内容...十分基础，所以直接放链接了，我觉得写的比较好的教程： https://oi-wiki.org/ds/bst/ 模板题：洛谷 P5076 传送门: https://www.luogu.com.cn/problem/P5076 // 普通二叉搜索树模板 #include <iostream> #define fuck cout << __LINE__ << endl using namespace std; const int maxn = 1e4+5; int cnt = 0; struct node { int val, cnt, size, l, r; } t[maxn]; void print(int u) { if (!u) return; print(t[u].l); for (int i = 0; i < t[u].cnt; i ++) cout << t[u].val << " "; print(t[u].r); } // 引用 u 的好处是能够在最后直接把新建的节点的编号赋给父亲的某个儿子 void insert(int &u, int val) { if (!u) { t[u = ++ cnt] = (node) {val, 1, 1, 0, 0}; return; } t[u].size ++; if (t[u].val == val) t[u].cnt ++; else if (val < t[u].val) insert(t[u].l, val); else insert(t[u].r, val); } int query_last(int u, int val, int ans) { if (val > t[u].val) { if (!t[u].r) return t[u].val; return query_last(t[u].r, val, t[u].val); } else { if (!t[u].l) return ans; return query_last(t[u].l, val, ans); } } int query_next(int u, int val, int ans) { if (val < t[u].val) { if (!t[u].l) return t[u].val; return query_next(t[u].l, val, t[u].val); } else { if (!t[u].r) return ans; return query_next(t[u].r, val, ans); } } int query_rank(int u, int val) { if (u == 0) return 1; if (t[u].val == val) return t[t[u].l].size + 1; if (val < t[u].val) return query_rank(t[u].l, val); return t[u].cnt + t[t[u].l].size + query_rank(t[u].r, val); } int query(int u, int rank) { if (rank > t[t[u].l].size && rank <= t[t[u].l].size + t[u].cnt) return t[u].val; if (rank <= t[t[u].l].size) return query(t[u].l, rank); return query(t[u].r, rank - t[t[u].l].size - t[u].cnt); } signed main() { int n; cin >> n; while (n --> 0) { int a, m; cin >> a >> m; if (a == 1) { cout << query_rank(1, m) << endl; } else if (a == 2) { cout << query(1, m) << endl; } else if (a == 3) { cout << query_last(1, m, -2147483647) << endl; } else if (a == 4) { cout << query_next(1, m, 2147483647) << endl; } else if (a == 5) { if (!cnt) { t[++…