标签 数据结构 下的文章

二叉搜索树的插入、查找、删除等操作的效率与树高成正比，因此在创建二叉搜索树时要尽可能地通过调平衡压缩树高。平衡树有很多种，例如AVL树、Treap、伸展树（Splay）、SBT、红黑树等。Treap简介特点与作用Treap，即Tree+Heap，又叫做树堆，它同时满足了二叉搜索树和堆两种性质。二叉搜索树满足中序有序性，输入的序列不同，创建的二叉搜索树也不同，在最坏的情况下（比如只有左子树或者只有右子树），会退化为线性。若一个二叉搜索树插入的节点顺序时随机的，则得到的二叉搜索树在大多情况下是平衡的，即使存在一些极端的情况但这种情况发生的概率很小，因此以随机…

[card title="主席树" color="info"]主席树，又叫可持久化权值线段树，也叫函数式线段树，是可持久化线段树的子集。在本文中，我们可以认为主席树等于可持久化线段树[/card]可持久化线段树简介基本结构、特点、作用在这篇文章中已经提到过：线段树扩展：权值线段树总的来说就是每次修改或插入一个值，就新建一个根节点，并且向下递归去新建其他节点。优点解释每次插入操作最多创建的节点数都为$\log n$（从根到叶子），一共执行了$n$次插入操作，可持久化线段树的节点总数为$n \log n$，而$n$棵单独的线段树的总节点数是$n^2$，很明显…

二叉堆简介二叉堆是一种基础数据结构，对于其他数据结构来说，支持的操作有限，也就插入，查询，删除这一类。二叉堆的结构从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存在一个权值。堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。本文以大根堆为例。由堆性质，树根存的是最大值。对于堆的每个子树，它同样也是一个堆。考虑使用一个序列h来表示堆，$h_i$的两个儿子分别是$h_{2i}$和$h_{2i+1}$，$1$是根节点：来自于：OI Wiki具体每个节点的对应关系如上图。二叉堆的基本操作插入操作插入操作是指向二叉堆中插入…