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

简单数据结构 信息学奥林匹克竞赛知识点（难点）讲解——数据结构【尖端】 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）； 若当前节点没有左儿子或右儿子，则将左儿子或右儿子替代该节点； 若当前节点有左儿子与右儿子，则不断旋转当前节点，并走到当前节点