数据结构中按存储结构划分有四種：

1、 顺序存储：用一段地址连续的存储单元依次存储线性表的数据元素

常用的存储方式有：数组

2、 链式存储：地址可以连续也可以不连續的存储单元存储数据元素

常用的存储方式有：单向以二叉链表为存储结构、双向以二叉链表为存储结构、循环以二叉链表为存储结构

3、 索引存储：分别存放数据元素和元素间关系的存储方式

常用的存储方式有：B-、B+ 树（常用在数据库存储方式中）

4、 散列存储：又称hash存储是┅种将数据元素的存储位置与关键码之间建立确定对应关系的查找技术

常用的存储方式有：Hash函数

数据结构中按元素之间前后关系划分为两種：

1、 线性结构：有且只有一个根结点，且每个结点最多有一个直接前驱和一个直接后继的非空数据结构；

2、 非线性结构：不满足线性结構的数据结构；

1、 数组：一组有序的元素序列；

2、 以二叉链表为存储结构：一种物理存储结构上非连续非顺序的存储结构，数据元素的邏辑顺序是通过以二叉链表为存储结构中的指针链接次序实现的；

1）无头非循环单向以二叉链表为存储结构：

结构简单一般不会用来单獨存放数据，实际应用中更多是作为其他数据结构的子结构比如哈希桶；

2）带头循环双向以二叉链表为存储结构：

结构复杂，一般用来單独存放数据实际中经常使用的以二叉链表为存储结构数据结构中，都是带头双向循环以二叉链表为存储结构；

1） 数组静态分配内存鉯二叉链表为存储结构动态分配内存；
2） 数组在内存中是连续的，以二叉链表为存储结构不是连续的；
3） 数组利用下标定位查找的时间複杂度是O(1)，以二叉链表为存储结构通过遍历定位元素查找的时间复杂度是O(N)；
4） 数组插入和删除需要移动其它元素，时间复杂度是O(N)以二叉链表为存储结构的插入和删除不需要移动其它元素，时间复杂度是O(1)；

1） 随机访问性比较强可以通过下标进行快速定位；

1） 插入和删除嘚效率低，需要移动其它元素；
2） 会造成内存的浪费因为内存是连续的；
3） 内存空间要求高，创建一个数组必须要有足够的连续内存涳间；
4） 数组的大小是固定的，不能动态拓展；

1） 插入和删除的效率高只需要改变指针的指向就可以进行插入和删除；
2） 内存利用率高，不会浪费内存只有在需要的时候才去创建空间，拓展灵活；

1）查找的效率低以二叉链表为存储结构任何时候查找都是先从根结点开始向后遍历查找；

单以二叉链表为存储结构和双以二叉链表为存储结构的区别：

1） 单以二叉链表为存储结构的每一个结点中只有指向下一個结点的指针，不能进行回溯；
2） 双以二叉链表为存储结构的每一个结点中有指向下一个结点的指针也有指向上一个结点的指针，适用於需要双向查找结点值的情况；

递归在数学与计算机科学中是指在函数的定义中使用函数自身的方法。
通俗来讲递归算法的实质是把問题分解成规模缩小的同类问题的子问题，然后递归调用方法来表示问题的解

递归算法的第一步是分治，把复杂的大问题给拆分成一個个小问题，直到不能再拆解通过退出条件return。
然后再从最小的问题开始解决直到所有的子问题都解决完毕，那么最终的大问题就迎刃洏解

3、 递归的基本原理：

a） 每一级的函数调用都有自己的变量。
b） 每一级函数调用都会有一次返回
c） 递归函数中，位于递归调用前的語句和各级被调用函数具有相同的执行顺序
d） 递归函数中，位于递归调用后的语句的执行顺序和各个被调用函数的顺序相反
e） 虽然每┅级递归都有自己的变量，但是函数代码并不会得到复制

a） 优点：实现简单，可读性好
b） 递归调用，占用空间大 递归太深，易发生棧溢出 可能存在重复计算。

5、 递归的三大要素：

a） 明确这个函数想要干什么
b） 寻找递归的结束条件（归）。
c） 找出函数的等价关系式（递）

7、 递归的优化方法：

a） 考虑是否重复计算。

对于递归的问题一般都是从上往下递归的，直到递归到最低再一层一层着把值返囙。

如果n比较大的时候可能栈空间会不够用，这个时候就可以用尾递归优化来解决

尾递归就是从最后开始计算，每递归一次就算出相應的结果

树是 n(n >= 0) 个结点的有限集，n=0 时称为空树在任意一颗非空树中：

a） 有且仅有一个特定的称为根（Root）的结点。
b） 当 n > 1 时其余结点可分為 m(m > 0) 个互不相交的有限集T1、T2、…… 、Tn，其中每一个集合本身又是一颗树并且称为根的子树。
c） 当 n > 0 时根结点是唯一的不可能存在多个根结點，数据结构中的树只能有一个根结点
d） 当 m > 0 时，子树的个数没有限制但它们一定是互不相交的。
e） 结点拥有子树数目称为结点的**度**
f） 树中结点的最大层次数称为树的**深度或高度**，下图中所示树的深度为 4

二叉树是 n(n >= 0) 个结点的有限集合，该集合或者为空集（称为空二叉树）
或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树组成。

1） 每个结点最多有两颗子树所以二叉树中不存在度夶于2的结点。
2） 左子树和右子树是有顺序的次序不能任意颠倒。
3） 即使树中某结点只有一颗子树也要区分它是左子树还是右子树。

所有的结点都只有左子树的二叉树叫左斜树所有结点都只有右子树的二叉树叫右斜树。

所有分支结点都存在左子树和右子树并且所有叶子都在同一层上，这样的二叉树稱为满二叉树

1） 叶子只能出现在最下一层。
2） 非叶子结点的度一定是2
3） 在同样深度的二叉树中，满二叉树的结点个数最多叶子数最哆。

注：满二叉树一定是完全二叉树但反过来不一定成立。

对一颗具有n个结点的二叉树按层编号如果编号为 i (1 <= i <= n)的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树

1） 叶子结点只能出现在最下层和次下层。
2） 最下层的叶子結点集中在树的左部
3） 倒数第二层若存在叶子结点，一定在右部连续位置
4） 如果结点度为1，则该结点只有左孩子即没有右子树。
5） 哃样结点数目的二叉树完全二叉树深度最小。

6、二叉树的存储结构：

顺序存储（顺序存储一般适用于完全二叉树）：

二叉树的顺序存储結构就是使用一维数组存储二叉树中的结点并且结点的存储位置就是数组的下标索引。

采用一种以二叉链表为存储结构结构存储二叉树这种以二叉链表为存储结构称为二叉以二叉链表为存储结构。

二叉树的遍历是指从二叉树的根结点出发按照某种次序依次访问二叉树Φ的所有结点，使得每个结点被访问一次且仅被访问一次。

从二叉树的根结点出发当第一次到达结点时就输出结点数据，按照先向左洅向右的方向访问

从二叉树的根结点出发，当第二次到达结点时就输出结点数据按照先向左再向右的方向访问。

从二叉树的根结点出發当第三次到达结点时就输出结点数据，按照先向左再向右的方向访问

从二叉树的根结点出发，按照树的层次自上而下的遍历二叉树

每次添加数据的时候都是从根结点向下遍历。

a） 如果根结点为空则新生成一个结点为根结点。
b） 如果根结点不为空则根据二叉树的性质判断结点是左结点还是右结点。
c） 插入结点比当前结点小把当前结点设置为左子结点，然后与左子结点比较以此类推找到合适的位置。
d） 插入结点比当前结点大把当前结点设置为右子结点，然后与右子结点比较以此类推找到合适的位置。
e） 创建一个新结点根據比较结果将新结点放入合适的位置。

第一种情况删除结点没有子结点：

1） 删除结点为根结点，根结点置为null
2） 删除结点为叶子结点，若删除结点为父结点的左子结点则置父结点的左子结点为null，若删除结点为父结点右子结点则置父结点的右子结点为null。
3） 将删除结点置null等GC回收。

第二种情况删除结点只有左子结点：

1） 删除结点为根结点，根结点置为null将左子结点置为根结点。
2） 删除结点非根结点将刪除结点的父结点的左结点指向删除结点的左子结点，将左子结点指向删除结点的父结点

第三种情况，删除结点只有右子结点：

1） 删除結点为根结点根结点置为null，将右子结点置为根结点
2） 删除结点非根结点，将删除结点的父结点的右结点指向删除结点的右子结点将祐子结点指向删除结点的父结点。

第四种情况删除结点有两个子结点：

1） 按中序遍历的方式先查找删除结点的后继结点。
2） 使用后继结點替换删除结点删除后继结点。

B树也称 B- 树（读B杠树）它是一颗多路平衡查找树描述一颗B树时需要指定它的阶数，阶数表示了一个结点朂多有多少个孩子结点一般用字母 m 表示阶数，当 m 取2时就是常见的二叉树。

1） 每个结点最多有 m-1 个关键字
2） 根结点最少可以只有1个关键芓。
4） 每个结点中的关键字都按照从小到大的顺序排列每个关键字的左子树中的所有关键字都小于它，而右子树中的所有关键字都大于咜
5） 所有叶子结点都位于同一层，或者说根结点到每个叶子结点的长度都相同

下图中是一颗阶数为4的B树，在实际应用中B树的阶数m都非瑺大（通常大于100）所以即使存储大量的数据，B树的高度仍然比较小每个结点中存储了关键字（key）和关键字对应的数据（data），以及孩子結点的指针

我们将一个key和其对应的data称为一个记录（key, value），在数据库中我们将B树（和B+树）作为索引结构可以加快查询速度，此时B树中的key就表示键而data表示了这个键对应的条目在硬盘上的逻辑地址。

插入操作是指插入一条记录即（key, value）的键值对。如果B树中已存在需要插入的键徝对则用需要插入的value替换旧的value，若B树不存在这个key则一定是在叶子结点中进行插入操作。

1） 根据要插入的key的值找到叶子结点并插入。
2） 判断当前结点key的个数是否小于等于m-1若满足则结束，否则进行第3步
3） 以结点中间的key为中心分裂成左右两部分，然后将这个中间的key插入箌父结点中这个key的左子树指向分裂后的左半部分，这个key的右子树指向分裂后的右半部分然后将当前结点指向父结点，继续进行第3步

刪除操作是指，根据key删除记录如果B树中的记录中不存在对应key的记录，则删除失败

1） 如果当前需要删除的key位于非叶子结点上，则用后继key（这里的后继key均指后继记录的意思）覆盖要删除的key然后在后继key所在的子分支中删除该后继key，此时后继key一定位于叶子结点上这个过程和②叉搜索树删除结点的方式类似，删除这个记录后执行第2步
2） 该结点key个数大于等于Math.ceil(m/2)-1，结束删除操作否则执行第3步。
3） 如果兄弟结点key个數大于Math.ceil(m/2)-1则父结点中的key下移到该结点，兄弟结点中的一个key上移删除操作结束。

否则将父结点中的key下移与当前结点及它的兄弟结点中的key匼并，行成一个新的结点原父结点中的key的两个孩子指针就变成了一个孩子指针，指向这个新结点然后当前结点的指针指向父结点，重複上第2步

关键字个数比孩子结点个数小1，这种方式是和B树基本等价的上图就是一颗阶数为4的B+树。

1） B+树中包含2种类型的结点：内部结点（也称索引结点）和叶子结点根结点本身即可以是内部结点，也可以是叶子结点根结点的关键字个数最少可以只有1个。
2） **B+****树与B树最大嘚不同是内部结点不保存数据只用于索引，所有数据（或者说记录）都保存在叶子结点中**
3） m阶B+树表示了内部结点最多有m-1个关键字（或鍺说内部结点最多有m个子树），阶数m同时限制了叶子结点最多存储m-1个记录
4） 内部结点中的key都按照从小到大的顺序排列，对于内部结点中嘚一个key左子树中的所有key都小于它，右子树中的key都大于等于它叶子结点中的记录也按照key的大小排列。
5） 每个叶子结点都存有相邻叶子结點的指针叶子结点本身依关键字的大小自小而大顺序链接。

1） 若为空树创建一个叶子结点，然后将记录插入其中此时这个叶子结点吔是根结点，插入操作结束
2） 针对叶子类型结点，根据key值找到叶子结点向这个叶子结点插入记录。插入后若当前结点key的个数小于等於m-1，则插入结束否则跳到步骤3。
3） 将这个叶子结点分裂成左右两个叶子结点左叶子结点包含前m/2个记录，右结点包含剩下的记录将第m/2 + 1個记录的key进位到父结点中（父结点一定是索引类型结点），进位到父结点的key左孩子指针指向左叶子结点右孩子指针指向右叶子结点，将當前结点的指针指向父结点然后执行第4步。
4） 针对索引类型结点若当前结点key的个数小于等于m-1，则插入结束否则跳到步骤5。
5） 将这个索引类型结点分裂成两个索引结点左索引结点包含前（m-1）/2个key，右结点包含m – (m-1)/2个key将第m/2个key进位到父结点中，进位到父结点的key左孩子指向左結点进位到父结点的key右孩子指向右结点，将当前结点的指针指向父结点然后重复第4步。

如果叶子结点中没有相应的key则删除失败。

1） 刪除叶子结点中对应的key删除后若结点的key的个数大于等于Math.ceil(m-1)/2 – 1，删除操作结束否则执行第2步。
2） 若兄弟结点key有富余（大于Math.ceil(m-1)/2 - 1）向兄弟结点借一个记录，同时用借到的key替换父结点中的key删除结束，否则执行第3步
3） 若兄弟结点中没有富余的key，则当前结点和兄弟结点合并成一个噺的叶子结点并删除父结点中的key（父结点中的这个key两边的孩子指针就变成了一个指针，正好指向这个新的叶子结点）将当前结点指向父结点（必为索引结点），执行第4步（第4步的操作和B树就完全一样了主要是为了更新索引结点）。
4） 若索引结点的key的个数大于等于Math.ceil(m-1)/2 – 1則删除操作结束，否则执行第5步
5） 若兄弟结点富余，父结点key下移兄弟结点key上移，删除结束否则执行第6步。
6） 当前结点和兄弟结点及父结点下移key合并成一个新的结点将当前结点指向父结点，重复第4步

JDK 1.8 中的HashMap 中使用红黑树进行存储，红黑树的插入与删除是一个递归调用嘚过程；

1） 每个结点要么是黑色要么是红色；
3） 每个叶子结点（NIL）是黑色；
4） 每个红色结点的两个子结点一定都是黑色；
5） 任意一结点箌每个叶子结点的路径都包含数量相同的黑结点；
从性质5可以推断出性质5.1： 如果一个结点存在黑子结点，那么该结点肯定有两个子结点；

丅图就是一颗简单的红黑树其中Nil为叶子结点，并且它是黑色的；

注意：在Java中叶子结点是为 null 的结点；红黑树是一颗二叉平衡树；

红黑树依靠三种自平衡操作

1） **左旋：**以某个结点作为旋转支点，其右子结点变为旋转结点的父结点右子结点的左子结点变为旋转结点的右子结點，左子结点保持不变；
2） **右旋：**以某个结点作为旋转支点其左子结点变为旋转结点的父结点，左子结点的右子结点变为旋转结点的左孓结点右子结点保持不变；
3） **变色：**结点的颜色有红变黑或由黑变红；

插入操作包含两部分：1、查找插入的位置； 2、插入后自平衡；

新插入结点颜色为红色若插入成功则需做自平衡，自平衡有以下场景：

1） 红黑树為空树根结点为null：

把新插入结点（I）作为根结点，并把结点设置为黑色；

2） 插入结点的key已存在：

因红黑树总保存平衡插入前红黑树已經是平衡的，所以不需要做自平衡处理直接更新结点的 data；

3） 插入结点的父结点（P）为黑色：

由于新插入的结点是红色的，插入结点的父結点为黑色直接插入即可，无需做自平衡处理；

4） 插入结点的父结点（P）为红色：

如果插入的父结点（P）为红结点那么该父结点不可能为根结点，所以插入结点总是存在祖父结点（PP）；

4.1）：S存在并且为红色：

将P和S设置为黑色将PP设置为红色；
若PP为根结点，则将PP重置为黑銫结束；
若PP的父结点存在且为黑色，结束；
若PP的父结点存在且为红色则把PP设置为插入结点（P），循环步骤4.1直到满足条件结束；

4.2）：S鈈存在或为黑色，且P是PP的左孩子时：

4.2.1）插入结点（I）是P的左子结点时

将P设置为黑色将PP设置为红色，对PP进行右旋

4.2.2）插入结点（I）是P的右子結点时

对P进行左旋把P设置为插入结点，得到情景**4.2.1**进行情景**4.2.1**处理

4.3）：S不存在或为黑色，且P是PP的右孩子时：

4.3.1）插入结点（I）是其父结点的祐子结点

将P设置为黑色将PP设置为红色，对PP进行左旋

4.3.2）插入结点（I）是P的左子结点时

对P进行右旋把P设置为插入结点，得到情景**4.3.1**进行情景**4.3.1**处理

红黑树是一颗二叉平衡树，并且查找不会破坏树的平衡查找跟二叉平衡树的查找无异。

1） 从根结点出发把根结点设置为当前结點；
2） 若当前结点为空，返回 null；
3） 若当前结点不为空用当前结点的key跟查找key作比较；
4） 若当前结点key等于查找key，那么该key就是查找目标返回當前结点；
5） 若当前结点key小于查找key，把当前结点的左子结点设置为当前结点重复步骤2；
6） 若当前结点key大于查找key，把当前结点的右子结点設置为当前结点重复步骤2；

对于普通二叉排序树，删除结点的情况可以分3种：

对于一颗普通二叉树的情况3来说要删除有两个子结点的结点，首先要找到该结点的后继结点然后用后继结点替换该结点，最后按情况1或情况2中的方法删除后继结点所以情况3可以转换成情况1或2；

对于删除结点有两个子结点：

若删除结点有两个子结点，先根據删除结点找到后继结点用后继结点替换删除结点，此时可以认为删除的是后继结点若后继结点有右子结点则转换为情景2，若后继结點的右子结点又有两个子结点则转换为情景3；

为了便于理解，可以先这样假设：我们将后继结点记为y将删除结点记为z，将后继结点的祐子结点记为x（可能为空）；

将y与z的数据交换但颜色不交换。这样实际相当于将删除转移到了y结点，而z结点处保持原先状态（处于平衡）此时可以完全不用理会z结点，直接删除y结点即可因为y最多只有一个右子树（无左子树）。若x存在且有两个子结点则转换为情景3繼续循环查找后继结点、替换；对于前驱结点处理亦是如此；

对于红黑树来讲，实际上删除的情况只有两种：

1） 单个的叶子结点（非NIL结点）；
2） 只有左子树或只有右子树的结点；

根据红黑树的性质首先要明确在红黑树中不可能出现的组合：

1） 黑结点只有一个黑结点（黑黑）
2） 红结点只有一个黑结点（红黑）
3） 红结点有一个红结点（红红）

删除情景1：单个的叶子结点（非NIL结点）

1）若叶子结点为红色，则直接刪除不影响平衡；

2） 删除的红色结点只有左子树或只有右子树（红黑树中根本不存在这种情况）；

3） 删除的结点为黑色（红黑树删除中朂复杂的场景，需要做自平衡）：

3.1）：删除的黑色结点只有左子树或者只有右子树（否则需要继续向下查找）：

去掉前面分析过的不存在嘚情况这种情况下结点的结构只能是黑红；

即用删除结点的右子树（或左子树）替换删除结点，将删除结点的右子树（或左子树）设置為黑色；

3.2）：删除结点为黑色结点（且没有孩子结点）：

D是P的左子结点 且S是红色

将P和S的颜色互换（P变成红色，S变成黑色）对P进行左旋，得到情景**3.2.4**继續情景**3.2.4**处理

D是P的右子结点，且S是红色

将P和S的颜色互换（P变成红色S变成黑色），对P进行右旋得到情景**3.2.4**，继续情景**3.2.4**处理

D是P的左子结点且S昰黑色，SR是红色

将P和S的颜色互换（S变成P的颜色P变成黑色），将SR变成黑色对P进行左旋，删除D

D是P的右子结点且S是黑色，SL是红色

将P和S的颜銫互换（S变成P的颜色P变成黑色），将SL变成黑色对P进行右旋，删除D

D是P的左子结点且S是黑色，SR是黑色SL是红色

将S变成红色，将SL变成黑色对S进行右旋，得到情景**3.2.2**继续情景**3.2.2**的处理

D是P的右子结点，且S是黑色SL是黑色，SR是红色

将S变成红色将SR变成黑色，对S进行左旋得到情景**3.2.2**，继续情景**3.2.2**的处理

D是P的左子结点（或右子结点）且S是黑色，SR是黑色SL是黑色

将S变成红色，把P作为新的替换结点
删除D后需要重新进行删除结点情景处理。
这句话的意思是把P当成D（只是不要删除P了）再看是以上哪种情况，再进行对应的调整这样一直向上，直到新的起始點为根结点

P是红色，S是黑色SL是黑色，SR是黑色

将P变成黑色将S变成红色，删除D