Estom的博客

平衡二叉树 树>二叉树>二叉搜索树>二叉平衡树 参考文献 AVL 1 简介概念 满足二叉搜索树的定义 所有结点的平衡因子的绝对值都不超过1，即平衡因子只能是1,0,-1三个值。 如果任何节点的平衡因子为1，则意味着左子树比右子树高一级。 如果任何节点的平衡因子为0，则意味着左子树和右子树包含相等的高度。 如果任何节点的平衡因子是-1，则意味着左子树比右子树低一级。 1平衡系数=左子树的高度 - 右子树的高度 复杂性 算法 平均情况 最坏情况 空间 o(n) o(n) 搜索 o(log n) o(log n) 插入 o(log n) o(log n) 删除 o(log n) o(log n) 优势 AVL树能防止二叉树偏斜，控制二叉搜索树的高度。高度为h的二叉搜索树中的所有操作所花费的时间是O(h)。 如果普通二叉搜索树变得偏斜(即最坏的情况)，它可以扩展到O(n)。 通过将该高度限制为log n，AVL树将每个操作的上限强加为O(log n)，其中n是节点的数量 2 操作基本操作 创建 遍历（同上） 插入 删除 ...

红黑树 树>二叉树>二叉搜索树>平衡二叉搜索树>红黑树（自平衡二叉搜索树） 参考文献 红黑树 1 简介定义 满足二叉搜索树的定义。 每个节点或者是黑色，或者是红色。 根节点是黑色。每个叶子节点（NIL）是黑色。（这里叶子节点，是指为空NULL的叶子节点！） 如果一个节点是红色的，则它的子节点必须是黑色的。 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。 优势 主要是用它来存储有序的数据，它的时间复杂度是O(lgn)，效率非常之高。 时间复杂度 红黑树的时间复杂度为: O(lgn) 2 操作 太过复杂，日后处理，根据参考文献。 基础操作 创建 遍历（同上） 插入 删除 旋转和着色 插入 第一步: 将红黑树当作一颗二叉查找树，将节点插入。 红黑树本身就是一颗二叉查找树，将节点插入后，该树仍然是一颗二叉查找树。也就意味着，树的键值仍然是有序的。此外，无论是左旋还是右旋，若旋转之前这棵树是二叉查找树，旋转之后它一定还是二叉查找树。这也就意味着，任何的旋转和重新着色操作，都不会改变它仍然是一颗二叉查找树的事实。 好吧？那接下来，...

B树1 简介概念 B 树又叫平衡多路查找树。一棵m阶的B树定义如下： B树中的每个节点最多包含m个子节点。最多包含m-1个键。 除根节点和叶节点外，B树中的每个节点至少包含[m/2]（向上取整）个子节点。 根节点要么是空、要么是独自的根、要么必须至少有2个子节点。 有k个子节点的节点必有k-1个键。每个键按顺序升序排序。 所有叶节点必须处于同一层（水平）。 4阶B树如下 应用 大规模数据存储中，二叉树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下 如何减少树的深度，一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。 多路查找树。根据平衡二叉树的启发，使用平衡多路查找树结构，也就是这篇文章所要阐述的第一个Btree。 分类 B树 B+树 B*树 2 操作基础操作 创建 遍历和搜索 插入 删除 分裂 合并 创建搜索 B树中搜索类似于二叉搜索树中的搜索 将数据项49与...

B+树 参考文献 B树B+树 1 简介概念 像是在建立额外的索引 有m个子树的中间节点包含有m个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引； 所有的叶子结点中包含了全部关键字的信息，及指向含有这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大的顺序链接。 (而B 树的叶子节点并没有包括全部需要查找的信息)； 所有的非终端结点可以看成是索引部分，结点中仅含有其子树根结点中最大（或最小）关键字。 (而B 树的非终节点也包含需要查找的有效信息)； 优点 B+树的磁盘读写代价更低 B+树的内部结点并没有指向关键字具体信息的指针。因此其内部结点相对B 树更小。如果把所有同一内部结点的关键字存放在同一盘块中，那么盘块所能容纳的关键字数量也越多。一次性读入内存中的需要查找的关键字也就越多。相对来说IO读写次数也就降低了； B+树查询效率更加稳定 由于非终结点并不是最终指向文件内容的结点，而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同，导致每一个数据的查询效率相当； B+树便于范围查...

堆 二叉搜索树、多路搜索树都是左小右大。堆树是上下大小不一样。 二叉搜索树是从根节点向叶子节点构造。进行插入。堆树是从叶子节点，向根节点进行构造。 参考文献 堆,但是有很严重的错误 1 简介 堆是一颗完全二叉树； 堆中的某个结点的值总是大于等于（最大堆）或小于等于（最小堆）其孩子结点的值。 堆中每个结点的子树都是堆树。 因为堆的第三条性质，堆的每一个子树，都是一个堆树。如果从叶节点开始进行一次向上调整。虽然能够保证最大值上浮到根节点。但是却无法保证它是一个堆树。因为进行一次向上调整。根节点的子树也许不是堆树。 使用数组表示的堆树 应用 堆结构的一个常见应用是建立优先队列（Priority Queue）。 普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配内存。堆仅仅使用一个数组来存储数组，且不使用指针。 2 操作基本操作 上浮 下沉 取顶 创建：把一个乱序的数组变成堆结构的数组，时间复杂度为 $O(n)$ 插入：把一个数值放进已经是堆结构的数组中，并保持堆结构，时间复杂度为 $O(log N)$ 删除：从最大...

字典树Trie 参考资料 字典树trie 数据结构算法10 1 Trie定义 Trie，又称前缀树或字典树，是一种有序树，用于保存关联数组，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。 字典树设计的核心思想是空间换时间，所以数据结构本身比较消耗空间。但它利用了字符串的**共同前缀（Common Prefix）**作为存储依据，以此来节省存储空间，并加速搜索时间。Trie 的字符串搜索时间复杂度为 O(m)，m为最长的字符串的长度，其查询性能与集合中的字符串的数量无关。其在搜索字符串时表现出的高效，使得特别适用于构建文本搜索和词频统计等应用。 2 Trie 的性质 根节点（Root）不包含字符，除根节点外的每一个节点都仅包含一个字符； 从根节点到某一节点路径上所经过的字符连接起来，即为该节点对应的字符串； 任意节点的所有子节点所包含的字符都不相同； ...

差分数组Sparse Array1 定义 定义：原数组为a，差分数组为d，那么有$$d[i] = a[i] - a[i - 1]$$ 其实差分数组是一个辅助数组，从侧面来表示给定某一数组的变化，一般用来对数组进行区间修改的操作 2 性质 a[i]等于d[i]的前缀和 $$a[i] = \sum_{0}^i d_i$$ d[i]等于a[i]两个临近元素的差$$d[i] = a[i] - a[i - 1]$$ 3 应用区间修改 当对一个区间进行增减某个值的时候，他的差分数组对应的区间左端点的值会同步变化，而他的右端点的后一个值则会相反地变化。他们的差分数组其实是不会变化的。 例如：将区间【1，4】的数值全部加上3 [l,r]区间内的数加k可以表示为如下形式： $$d[l]+k\d[r+1]-k$$ 元素求值 既然我们要对区间进行修改，那么差分数组的作用一定就是求多次进行区间修改后的数组。 直接反过来即得$$a[i]=a[i-1]+d[i]$$ 实例1 区间涂色问题描述 N个气球排成一排，从左到右依次编号为1,2,3…...

树状数组Binary Tree Array1 概念lowbit运算$$lowbit(x) = x & ((\sim x)+1)$$ 作用：二进制表示中，保留最后的1。如x=10100100,lowbit(x)=00000100 树状数组 根据lowbit的运算规则构建树状数组。 其中数组A第i个位置的值管理区间[i-lowbit(i)+1,i]。即去掉二进制最后一位后到当前位置的的区间。 $$A[i] = \sum_{k=i-lowbit(i)+1}^i A[k]$$ 其中数组A第i个位置的值的被管节点。即找到所有的之后的$2^i$的点，也包括非$2^i$的点。 $$i = i + lowbit(i) ,i<max(i)$$ 本质理解 怎么看每个原始数组的数字管理多少？只要顺着原始数组的数字往下画竖线，碰到的第一根横线所覆盖的范围就是它能管理的范围。 怎么看每个原始数组的数字被谁管理？顺着原始数组的数字往下画竖线，碰到的第一根横线之后的所有横先，都是管理该数字的树状数组值。 在构建的树状数组中$2^i$管理之前...

线段树Segment Tree1 线段树的概念概述 线段树(Segment Tree)也是一棵树，只不过元素的值代表一个区间。常用区间的 统计 操作，比如一个区间的 最大值(max),最小值(min),和(sum) 等等 如一个长度为10的数组，它对应的 求和 线段树，如下图所示(图中的数字表示索引)： 定义 线段树是一个平衡二叉树，但不一定是完全二叉树。 根节点就是 0~lenght-1 的和 根节点的左右子树平分根节点的区间 然后依次类推，直到只有一个元素不能划分为止，该元素也就是二叉树的叶子节点。 复杂度 时间复杂度为O(log n) 空间复杂度为O(n) 2 线段树的基本操作构建线段树 根据上面我们对线段树的描述，构建一个线段树就比较简单了，根节点就是整个区间，根节点的左右子树平分根节点的区间，直至区间内只剩下一个元素不能平分为止。如下面递归的伪代码： 123456789101112131415161718192021private void buildSegmentTree(int treeIndex, int treeLeft, int treeRi...

(注：切勿简单的认为一棵m阶的B树是m叉树，虽然存在四叉树，八叉树，KD树，及vp/R树/R*树/R+树/X树/M树/线段树/希尔伯特R树/优先R树等空间划分树，但与B树完全不等同)