二叉树
二叉树是在程序设计中经常用到的数据结构之一，我们在数据结构中经常说的堆结构就是一种二叉树。二叉树与通常的树不同的是它规定每个节点最多只能拥有两个子节点。
完全二叉树
完全二叉树是二叉树的一种形态，它要求除了最后一层外，其余层必须完全填充，且有子节点的节点的度数必须为2。其叶子节点均靠左对其。
完满二叉树
完满二叉树要求比完全二叉树低，它仅要求所有的非叶子节点的度数为2，即所有有子节点的节点都必须有两个子节点。
完美二叉树
完美二叉树又被称为满二叉树。顾名思义，其要求所有层都需要完全填充。此时深度为h的满二叉树的节点数为$$2^{h} - 1$$
二叉查找树
二叉查找树又被称为二叉排序树。是一种特殊的二叉树，它并不要求一定是完满二叉树还是满二叉树，它只要求节点的值大于其左子节点，小于其右子节点。
由上图可以看出，二叉查找树在进行二叉树查找时，基本遵循的是二分查找的思想。它的算法复杂度为$$O(logn)$$一棵深度为h的二叉查找树，我们也可以说它的算法复杂度为$$O(h)$$
平衡二叉树
平衡二叉树是一种能够在构建二叉树时完成自平衡性的二叉查找树。
传统的二叉查找树虽然算法复杂度达到了O(logn)，但当二叉查找树构建时，节点过度偏向于一侧时，它的算法复杂度可能会被退化为O(n)，即退化为链表。
如下图
AVL树
AVL树即是传统平衡二叉树，它具有以下两个性质：
- 节点两边的高度差不大于1.
- 节点的子树也为AVL树。
如下图，我们用上面的红数字来记录该节点左子树与右子树的层数差，现在最大层数差的绝对值不超过1，故我们称它现在处于平衡状态。
我们可以考虑，不平衡状态有以下四种情况：
分别是：
- 向左子树的左节点添加元素导致不平衡
- 向左子树的右节点添加元素导致不平衡
- 向右子树的左节点添加元素导致不平衡
- 向右子树的右节点添加元素导致不平衡
也就是左左、左右、右左、右右。
为了让它查找时的算法复杂度最低，我们需要对整个平衡树进行旋转。
单旋转
当平衡树左子树较重时，需要右旋，将左子树的根节点作为新根节点，将左子树根节点的右子节点作为原根节点的左子节点。
当平衡树右子树较重时，需要左旋，将右子树的根节点作为新根节点，将右子树根节点的左子节点作为原根节点的右子节点。
单旋转适用于左左、右右的情况。
双旋转
双旋转就是先将较重子树进行一次单旋转，然后总体再进行一次单旋转，这样一共进行两次旋转使树成为平衡状态。
删除节点
由于二叉树节点的删除也会破坏其平衡性，所以在进行删除时，主要使用以下方式：
若要删除的节点的左右子树非空，则选取其深度最大的子树，将子树中的最大（最小）值赋值给根节点，然后删除子树中最大（最小）值的节点。
假设要删除根节点：
在删除结束后，要判断当前的树是否平衡，若不平衡，则进行旋转。
VAL树的插入、删除、查询时间复杂度均为$$O(logn)$$
红黑树
红黑树(RB-tree)是通过颜色来维持二叉树平衡的树，它必须遵守以下五点规则：
- 每个结点都只能是红色或者黑色中的一种。
- 根结点是黑色的。
- 每个叶结点（NIL节点，空节点）是黑色的。
- 如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
- 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点。
当我们插入数据时，如果插入的节点颜色为黑色，则一定会违背规则3，所以我们默认插入的节点为红色。在我们插入数据时，我们判断插入后的红黑树是否违背以上的五个规则，如果违背，则要对其进行调整，也就是旋转和着色。
- 插入到一个空的树，插入结点则为根结点，只需要将红色结点重新转染成黑色结点来满足性质2；
- 新结点的父结点为黑色，满足所有条件；
- 新结点的父结点为红色，因为性质2和性质4，所以树必然有祖父结点，则又包括以下的情况：
- 父亲结点和叔父结点均为红色，显然无法满足性质4，则将父亲结点和叔父结点绘制成黑色，祖父结点设置成红色，但是仍然无法满足情况，比如考虑到祖父结点可能是根结点，则无法满足性质2，或者祖父结点的父结点是红色的，则无法满足性质4，这时需要将祖父结点作为新的结点来看待进行各种情况的判断，涉及到对祖父结点的递归；
- 父亲结点为红色同时叔父结点为黑色或者从缺，这里又分为两种情况，新插入结点为父亲结点的左子结点和右子结点（假设其中父亲结点为祖父结点的左子结点），区别在于旋转的方向，显然，这棵树父亲结点既然为红色，那么其祖父结点则为黑色（性质4），不然无法满足前提。
- 新插入结点为父亲结点的左子结点，那么就构成了一个左左的情况，在之前平衡树中提到过，如果要将其进行平衡，则需要对父结点进行一次单右旋转，形成一个父亲结点为相对根结点，子结点和祖父结点为子结点的树，同时将父亲结点的红色改为黑色，祖父结点更改为红色，这下之前无法满足的性质4和性质5就满足了；
- 新插入结点为父亲结点的右子结点，那么就会构成一个左右的情况，在之前的平衡树也提到过要进行一次双旋转，先对新结点进行一次单左旋转，变成了左左的结构，再进行一次单右旋转，从而达到满足所有性质；
- 父亲结点是祖父结点的右结点，参考平衡树进行相应的操作，原理是一致的
红黑树
