二叉树基础及特殊的二叉树
1.二叉树的分类
- 满二叉树：从高到低，除了叶节点外，所以节点左右节点都存在。
- 完全二叉树：比满二叉树少几个叶节点，从左向右放子节点。
- 平衡二叉树：空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树也都是平衡树。
- 二叉搜索树：空树或者二叉树的所有节点比他的左子节点大，比他的右子节点小。
- 红黑树：不仅是具有二叉搜索树的属性，还具有平衡树的属性，有序且子树差不超过1
红黑树的颜色规则：根节点和特殊节点（即叶节点下面两个虚无的节点和未填写的节点）是黑的，红节点
的左右子节点是黑的，最重要的是对于每个节点，从该节点到子孙叶节点的所有路径包含相同数目的黑节点。
2. 二叉树在搜索上的优势
数组利用下标，搜索方便，删除或者插入麻烦
链表与之相反，查找很慢，删除和插入简单
原因在于这两种数据结构的存储方式，数组是取一段相连的空间，而链表是每创建一个节点便取一个节点所
需的空间，只是使用指针进行连接，空间上并不是连续的。而二叉树就既有链表的好处，又有数组的优点。
3. 二叉树的遍历
先序遍历（pre order）： 根 左 右
中序遍历（in order）： 左 根 右
后序遍历（post order）：左 右 根
4. 二叉树的序列化和反序列化（serialize and deserialize）
序列化：结构化数据---->顺序数据流
反序列化：顺序数据流---->结构化数据
二叉树的遍历可以实现二叉树的序列化，但是单独的一个遍历序列无法完成二叉树的还原，即反序列化，先
序+中序或者后序+中序可以还原二叉树。
5.1. 二叉搜索树（BST：binary search tree）
1.定义：对于任意一个节点，其值大于左子树的任何节点，且小于右子树的任何节点，则为二叉搜索树。(空树也是BST)
2.性质：中序遍历BST，其遍历结果是一个有序序列。因此，二叉搜索树又称为二叉排序树。
优：查找的最大次数为树的高度
缺：因其序列性，有可能会退化成单链表
3.区分：二叉搜索树要求当前节点与其左右子树都需满足定义中的关系；最大堆（或最小堆），只要求当前节点与当前节点的左右子节点满足一定关系。
BST是为了查找，堆是为了排序 .
（堆是完全二叉树，插入到二叉树的最底层的最右边，逐步调整；删除只能删除堆顶节点）
4.插入和删除:
插入：找到对应的空位置，直接插入；否则，不做操作
删除：（1） 删除节点为叶子节点：直接删除
（2） 删除节点只有一个子节点：子节点直接顶替
（3） 删除节点有两个子节点：
a. 找到右子树的最左结点 M （或者左子树的最右结点）
b. 用 M 的值替换要删除的节点
c. 删除 M （此时 M 为 情况（1）或者（2））
二叉搜索树和堆及AVL
二叉搜索树（BST）有序的特性非常重要，在此基础上加入不同的限制条件衍生了平衡二叉树和红黑树，平衡二叉树和红黑树本身都是二叉搜索树
5.2. 平衡二叉树（AVL：Self-balancing binary search tree）
（一）引入：BST退化成单链表时，查找效率很低（O(n)），因此在BST的基础上引入平衡二叉树，规定父节点的左右两棵子树的深度之差的绝对值不超过1
（二）旋转调平衡：旋转分为左旋和右旋
-->左旋：使当前节点变为子节点的左结点
-->右旋：使当前节点变为子节点的右结点
插入分为四种情况：左左 右右 左右 右左
左左：祖父右旋
右右：祖父左旋
左右：父左旋，祖父右旋
右左：父右旋，祖父左旋
-->最小不平衡节点：插入一个节点之后，距离这个插入节点最近的不平衡节点就是最小不平衡节点
（祖父节点是最小不满足平衡的节点，父节点是祖父节点包含新节点分支的最近子孩子）
参考文献：数据结构—平衡二叉树
5.3. 红黑树（：Res Black tree）
（一）引入：由于AVL平衡条件，插入数据需多次调整以满足平衡条件，引入红黑树，相当于降低平衡条件，这样插入时不需要进行多次调整以满足严苛的高度差不超过1的平衡条件，红黑树只需满足最长路径不超过最短路径的两倍即可。
红黑树到叶子节点的最长路径不会超过最短路径的两倍
（二）定义
1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（叶子节点指空节点）。
4.如果一个节点是红色，它的子节点必然是黑色(避免出现连续的两个红色节点 , 黑色可连续)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。（保证两倍关系）
（三）性质：
红黑树的时间复杂度为O(lgn)
一棵含有n个节点的红黑树的高度至多为2log(n+1)
（四）平衡调整：
ａ插入：红黑树的插入操作会导致不满足条件，需要通过 变色 或者 旋转 来调整。
设：插入的节点设为红色，（因条件5黑色节点是数目要相同的）
（1）父节点 黑
直接插入
（2）父节点 红
| case | 处理 |
|
case1：父（红） 叔（红） |
1.父叔两红—设为黑 2.祖—设为红 3.祖为当前节点 |
|
case2：父（红） 叔（黑） 且当前节点为父节点的右孩子 |
1.父左旋 2.父为新节点 |
|
case3：父（红） 叔（红） 且当前节点为父节点的zu孩子 |
1.祖右旋 2.父—设为黑， 祖—设为红 |
核心思想：将红色的节点不断上移到根节点；然后，将根节点设为黑色
ｂ.删除：删除点为红色，不调整，删除点为黑色，触发删除函数
步骤：
（1）将红黑树当作一颗二叉查找树，将节点删除
（2）通过"旋转和重新着色"等一系列来 修正 该树，使之重新成为一棵红黑树
修正：
步骤 （1）： 节点 y 删除后，x 作为后继节点顶替 y
因：既然删除y(y是黑色)，意味着减少一个黑色节点，需再在该位置上增加一个黑色来满足特性（5）
故：设 "x包含一个额外的黑色" (x原本的颜色还存在)
（a） x是“红+黑”节点 x 设为黑色，结束
（b） x是“黑+黑”节点，且 x 是根结点 什么都不做，结束
（c） x是“黑+黑”节点，且 x 不是根结点 分为四种情况
| case1： |
x是"黑+黑"节点，x的兄弟节点是红色 (此时x的父节点和x的兄弟节点的子节点都是黑节点) |
(01) 将x的父节点和兄弟节点颜色互换。 (02) 对x的父节点进行旋转，使其成为兄弟节点的孩子 节点。 (03) 继续判断 x |
| case2： |
x是“黑+黑”节点，x的兄弟节点是黑色 x的兄弟节点的两个孩子都是黑色 |
(01) 将x的父节点和兄弟节点颜色互换。 |
| case3： | x是“黑+黑”节点，x的兄弟节点是黑色 x的兄弟节点的左孩子是红色，右孩子是黑色的 |
(01) 将x兄弟节点的左孩子和兄弟节点颜色互换。 (02) 对x的兄弟节点进行右旋。 (03) 继续判断 x |
| case4： |
x是“黑+黑”节点，x的兄弟节点是黑色
x的兄弟节点的右孩子是红色的，x的兄弟节点的左孩子任意颜色 |
(01) 对x的父节点进行旋转，使其成为兄弟节点的孩子 节点。 (02) 将兄弟节点的黑色下放 |
总体思想： 将情况1首先转换成情况2、情况3或情况4。当然调整过程不一定是从情况1开始。只有进入情况2和情况4才可以推出判断的循环，即修正完成。
修正过程中始终向着兄弟节点转为黑色，兄弟节点的右孩子转为红色的方向转换，图解如下：
上述图解都是x为父节点的左孩子，兄弟节点是父节点的右孩子，当他们在父节点的位置互换后，每种情况下处理过程中转变兄弟节点、孩子节点的颜色及旋转方向都要随之更改。
参考文献：史上最清晰的红黑树讲解（上）