一、二叉树
1、CBT—FBT一定是CBT
参考文章：Algorithm：【Algorithm算法进阶之路】之数据结构基础知识https://yunyaniu.blog.csdn.net/article/details/94663836#2、树Tree结构
2、BST—二叉查找树BST的增删改查
1、BST的查找节点
查找某节点p的过程如下：
n 将当前节点cur赋值为根节点root；
n 若p的值小于当前节点cur的值，查找cur的左子树；
n 若p的值不小于当前节点cur的值，查找cur的右子树；
n 递归上述过程，直到cur的值等于p的值或者cur为空；
o 当然，若节点是结构体，注意定义“小于”“不小于”“等于”的具体函数。
2、BST的插入节点
原理要符合二叉树的建立。
n若当前的二叉查找树为空，则插入的元素为根节点，
n若插入的元素值小于根节点值，则将元素插入到左子树中，
n若插入的元素值不小于根节点值，则将元素插入到右子树中，
n递归上述过程，直到找到插入点为叶子节点。
3、BST的删除节点
记待删除的节点为p，分三种情况进行处理
待删除点为叶子节点：p为叶子节点，直接删除该节点，再修改p的父节点的指针
待删除点只有一个孩子：若p为单支节点（即只有左子树或右子树），则将p的子树与p的父亲节点相连，删除p即可。
待删除点只有一个孩子：若p的左子树和右子树均不空，则找到p的直接后继d(p的右孩子的最左子孙)，因为d一定没有左子树，所以使用删除单支节点的方法：删除d，并让d的父亲节点dp成为d的右子树的父亲节点；同时，用d的值代替p的值；
(1)、对偶的，可以找到p的直接前驱x(p的左孩子的最右子孙)，x一定没有右子树，所以可以删除x，并让x的父亲节点成为x的左子树的父亲节点。
3、BBT—平衡二叉树BBT→AVL/RBT
平衡二叉树（Balanced Binary Tree）是二叉查找树的一个变体，也是第一个引入平衡概念的二叉树。1962年，G.M. Adelson-Velsky 和E.M. Landis发明了这棵树，所以它又叫AVL树。
平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找BST树退化成链表的问题，把插入、查找、删除的时间复杂度最好情况和最坏情况都维持在O(logN)。
1、BBT的动机
对一棵查找树（search tree）进行查询/新增/删除 等动作, 所花的时间与树的高度h 成比例, 并不与树的容量 n 成比例。如果可以让树维持矮矮胖胖的好身材, 也就是让h维持在O(lg n)左右, 完成上述工作就很省时间。能够一直维持好身材, 不因新增删除而长歪的搜寻树, 叫做balanced search tree（平衡树）。
2、BBT的特点：
BBT是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
BBT常用算法有红黑树、AVL、Treap、伸展树、SBT等。
最小BBT的节点的公式： F(n)=F(n-1)+F(n-2)+1，这个类似于一个递归的数列，可以参考Fibonacci数列，1是根节点，F(n-1)是左子树的节点数量，F(n-2)是右子树的节点数量。
0、AVL和RBT红黑树
0、AVL和红黑树对比
两者都属于自平衡二叉树。
两者查找,插入，删除的时间复杂度相同。
1、AVL树—可理解为BBT
AVL树查找的时间复杂度为O(logN)，因为树一定是平衡的。但是由于插入或删除一个节点时需要扫描两趟树，依次向下查找插入点，依次向上平衡树，AVL树不如红黑树效率高，也不如红黑树常用。
AVL树是平衡二叉搜索树的鼻祖：AVL树是最先发明的自平衡二叉查 找树。
AVL树有两个性质
它或者是一颗空二叉树，或者是具有下列性质的二叉树：
(1)、其根的左右子树，高度之差的绝对值不能超过1；
(2)、其根的左右子树，都是二叉平衡树。
AVL应用 1、Windows NT内核中广泛存在。
2、红黑树
红黑树的平衡是在插入和删除的过程中取得的。对一个要插入的数据项，插入程序要检查不会破坏树一定的特征。如果破坏了，程序就会进行纠正，根据需要更改树的结构。通过维持树的特征，保持了树的平衡。
红黑树 并不追求“完全平衡 ”：它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。
红黑树能够以 O(log2 n) 的时间复杂度进行搜索、插入、删除操作。
任何不平衡都会在三次旋转之内解决。
红黑树有两个特征
1、节点都有颜色
2、在插入和删除过程中，要遵循保持这些颜色的不同排列的规则。
红黑规则 1、每一个节点不是红色的就是黑色的。
2、根总是黑色的
3、如果节点是红色的，则它的子节点必须是黑色的（反之不一定成立）。
4、从根到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点。
（空子节点是指非叶节点可以接子节点的位置。换句话说，就是一个有右子节点的节点可能接左子节点的位置，或是有左子节点的节点可能接右子节点的位置）
红黑树的应用
1、广泛用于C++的STL中,map和set都是用红黑树实现的。
(1)、JDK的TreeMap是一个红黑树的实现，能保证插入的值保证排序。
2、IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查。
1、BBT的旋转
高度不平衡节点的两颗子树的高度差2，只考虑该不平衡节点本身，分四种情况分别讨论。
(1)、四种分类：左左、左右、右左、右右；
(2)、四种旋转：对称与旋转，左左和右右对称；左右和右左对称
左左和右右两种情况是对称的，这两种情况的旋转算法是一致的，只需要经过一次旋转就可以达到目标，称之为单旋转。
左右和右左两种情况也是对称的，这两种情况的旋转算法也是一致的，需要进行两次旋转，称之为双旋转。
a、高度不平衡之左左
6节点的左子树3节点高度比右子树7节点大2，左子树3节点的左子树1节点高度大于右子树4节点，这种情况成为左左。
b、高度不平衡之左右
6节点的左子树2节点高度比右子树7节点大2，左子树2节点的左子树1节点高度小于右子树4节点，这种情况成为左右。
c、高度不平衡之右左
2节点的左子树1节点高度比右子树5节点小2，右子树5节点的左子树3节点高度大于右子树6节点，这种情况成为右左。
d、高度不平衡4之右右
2节点的左子树1节点高度比右子树4节点小2，右子树4节点的左子树3节点高度小于右子树6节点，这种情况成为右右。
(1)、BBT的左左—单旋转
如图，假设K2不平衡：为使树恢复平衡，把K1变成根节点。K2大于K1，所以，把K2置于K1的右子树上。K1右子树Y大于K1，小于K2，所以，把Y置于k2的左子树上。
左旋：就是让左边的孩子K1去提到上边，升级作为爸爸，自己K2变成儿子。
(2)、BBT的左右双旋转
对于左右和右左这两种情况，单旋转不能使它达到一个平衡状态，要经过两次旋转。
以左右为例：节点K3不满足平衡特性，它的左子树K1比右子树D深2层，且K1子树更深的是右子树K2。
2、BBT的插入
BBT插入的方法和BST基本一致。区别是，插入完成后需要从插入的节点开始，维护一个到根节点的路径，每经过一个节点都要维持树的平衡。维持树的平衡要根据高度差的特点选择不同的旋转算法。
3、BBT的查找
BBT查找的方法和BST完全一样。不过根据高度基本平衡存储的特性，BBT能保持O(logN)的稳定时间复杂度，而BST则相当不稳定。
4、BBT的删除
BBT删除的方法和BST基本一致。区别是，删除完成后，需要从删除节点的父亲开始，向上维护树的平衡一直到根节点。
