简单数据结构课件-2021-2022学年中学生信息学奥林匹克竞赛数据结构（难点）精讲（161张PPT）

(课件网) 简单数据结构 信息学奥林匹克竞赛知识点（难点）讲解———数据结构【尖端】 1.序列维护（线段树&平衡树） 线段树 相信大家都会线段树了，所以就不讲原理了 平衡树 全称“平衡二叉搜索树”，常见的类型有： 1.splay 2.treap 3.AVL Tree 4.Red Black Tree 5.Scape Goat Tree 6.Weight Balanced Leafy Tree（特殊结构） 二叉搜索树 性质：一个节点x左子树所有点的关键字都比x的关键字小，右子树所有点的关键字都比x的关键字大 平衡树 限于篇幅，这里只讲一下treap和splay treap “树堆”“Tree + Heap” 性质：每个点随机分配一个权值，使treap同时满足堆性质和二叉搜索树性质 复杂度：期望O( logn ) treap 设每个节点的关键字是key，随机权值是rand 1.如果v是u的左儿子，则key[v] < key[u] 2.如果v是u的右儿子，则key[v] > key[u] 3.如果v是u的子节点，则rand[u] > rand[v] treap Treap维护权值的时候一般会把相同的权值放在同一个节点上 所以一个treap节点需要维护以下信息： 左右儿子 关键字 关键字出现次数 堆随机值 节点大小（即子树大小） 说要讲模板，这里就利用一下hzwer的吧 旋转 平衡二叉搜索树主要通过旋转来保持树的平衡，即保证复杂度 Treap的旋转 旋转有单旋和双旋，treap只需要单旋，这一点比较简单 Treap的插入 先给这个节点分配一个随机的堆权值 然后把这个节点按照bst的规则插入到一个叶子上： 从根节点开始，逐个判断当前节点的值与插入值的大小关系。如果插入值小于当前节点值，则递归至左儿子；大于则递归至右儿子； 然后通过旋转来调整，使得treap满足堆性质 Code Treap的删除 和普通的BST删除一样： 如果删除值小于当前节点值，则递归至左儿子；大于则递归至右儿子 若当前节点数值的出现次数大于 1 ，则减一（通常将同一个权值缩掉） Treap的删除 若当前节点数值的出现次数等于 1 : 若当前节点没有左儿子与右儿子，则直接删除该节点（置 0）； 若当前节点没有左儿子或右儿子，则将左儿子或右儿子替代该节点； 若当前节点有左儿子与右儿子，则不断旋转当前节点，并走到当前节点新的对应位置，直到没有左儿子或右儿子为止。 Code Treap的查询 递归到叶子节点，一路维护信息即可 Treap维护权值 现在大家都会用treap来维护一个集合 支持插入，删除，查询（kth，rank等）了吧 Treap的其他功能 Treap还可以支持维护序列时的分裂合并 这里不详细讲了（我也不会） 具体可以看luogu日报？ splay “伸展树”“自适应查找树” splay 每次对一个节点进行操作的时候通过一种方法把这个点旋转至根 需要根据不同的情况判断应该怎么旋转，这里就不详细介绍了 splay Splay具有“自适应性” 大概就是说splay会根据操作的特点调整树结构，使得操作尽可能高效 可以去了解了解splay的动态最优性猜想，是个著名的open problem Disadvantage 可以通过势能分析证明splay的复杂度是均摊O( logn )的，也就是说splay在很多次操作中可能会有一次O( n )复杂度的操作 而且这样的操作也很好构造 所以splay不适合做一些需要撤销操作/可持久化的题目（虽然可以通过随机旋转什么的方法来规避，但还是感觉很吃力） 自身常数比较大 Advantage Splay用来维护序列还是比较好写的，用来维护名次树感觉不好写 由于自适应性，splay不需要特殊的技巧就可以高效启发式合并，还可以高效实现LCT（STT）等动态树 打个广告———WBLT 全称：Weight Balanced Leafy Tree 这个Weight Balanced是指的Balanced by Boundary，也就是BB[α] 和clj那个定义不一样 大概可以理解为通过旋转而不是重构来满足替罪羊树那个平衡关系 也就是说替罪羊树是Weight Balanced Tree的一种 打个广告———WB ... ...