红黑树
1.二叉树
二叉树指的是每个节点最多只能有两个字数的有序树。通常左边的子树称为左子树 ，右边的子树称为右子树
image.png
2.排序二叉树
排序二叉树是有顺序的，它是一种特殊结构的二叉树
主要特性：
若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若她的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
具有递归性，排序二叉树的左子树、右子树也是排序二叉树。
image.png
3.平衡二叉树
平衡二叉数又被称为 AVL 树
具有以下性质的排序二叉树：
它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。
两个条件：
平衡二叉树必须是排序二叉树，也就是说平衡二叉树他的左子树所有节点的值必须小于根节点的值，它的右子树上所有节点的值必须大于它的根节点的值。
左子树和右子树的深度之差的绝对值不超过1。
4.红黑树
其实红黑树和上面的平衡二叉树类似，本质上都是为了解决排序二叉树在极端情况下退化成链表导致检索效率大大降低的问题，红黑树最早是由 Rudolf Bayer 于 1972 年发明的。
红黑树首先肯定是一个排序二叉树，它在每个节点上增加了一个存储位来表示节点的颜色，可以是 RED 或 BLACK 。
image.png
红黑树的特性：
性质1：每个节点要么是红色，要么是黑色。
性质2：根节点永远是黑色的。
性质3：所有的叶子节点都是空节点（即null），并且是黑色的。
性质4：每个红色节点的两个子节点都是黑色。（从每个叶子到根的路径上不会有两个连续的红色节点。）
性质5：从任一节点到其子树中每个叶子节点的路径都包含相同数量的黑色节点。
红黑树的插入：
红黑树的插入和普通排序二叉树的插入基本一致，排序二叉树的要求是左子树上的所有节点都要比根节点小，右子树上的所有节点都要比跟节点大，当插入一个新的节点的时候，首先要找到当前要插入的节点适合放在排序二
叉树哪个位置，然后插入当前节点即可。红黑树和排序二叉树不同的是，红黑树需要在插入节点调整树的结构来让树保持平衡。
一般情况下，红黑树中新插入的节点都是红色的
红黑树的旋转：
旋转分为左旋和右旋。
1）左旋
逆时针旋转两个节点，让一个节点被其右子节点取代，而该节点成为右子节点的左子节点。
image.png
2）右旋
顺时针旋转两个节点，让一个节点被其左子节点取代，而该节点成为左子节点的右子节点。
image.png
左左节点旋转（插入节点的父节点是左节点，插入节点也是左节点）
