红黑树
1.二叉查找(排序)树BST
（1）什么是BST？
二叉查找树满足：
- 左子树上所有结点的值均小于或等于它的根结点的值。
- 右子树上所有结点的值均大于或等于它的根结点的值。
- 左、右子树也分别为二叉排序树。
总结来说左小右大。
（2）BST的优缺点
-
优点：
比如我们要找节点10，算上根节点，一共找4次就能找到。也就是说，使用BST查找一个元素的最大查找次数等于树的高度。插入新节点也是如此，通过一层一层查找找到合适位置。 -
缺点：
在数据递增或递减时，BST会不平衡，导致查找的性能退化成线性的。比如下面这样一棵BST，"左子树"成了线性链表了。
2.红黑树
为了解决二叉排序树可能退化成线性链表的问题，引入了红黑树。
（1）什么是红黑树？
红黑树是一种自平衡的二叉排序树。它具有一下特点：
- 根节点是黑色，其他节点是红色或黑色；
- 每个叶子节点都是黑色的空节点（称为NIL节点）；
- 每个红色节点的两个子节点都是黑色，也就是说从每个叶子到根的所有路径上不能有两个连续的红色节点；
- 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
（2）红黑树调整策略
当插入(新插入节点都是红色的)或删除节点后，可能打破红黑树的规则，因此需要对红黑树进行调整，有以下两种调整策略：
- 变色：将红色节点变为黑色，或者把黑色节点变为红色，使该树重新符合红黑树的要求。
-
旋转：
-
左旋转：左旋转使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
-
右旋转：右旋转使得父节点被自己的左孩子取代，而自己成为自己的右孩子。
-
左旋转：左旋转使得父节点被自己的右孩子取代，而自己成为自己的左孩子。
（3）★★如何向红黑树中插入一个新节点？
首先根据二叉排序树的性质找到插入位置，因为新插入的节点是红色的，所以如果父节点也是红色(大前提)时需要进行调整。有三种情况：
-
case1：叔叔节点也是红色，将父节点和叔叔节点的颜色与爷爷结点的颜色互换。
-
case2：没有叔叔且新节点、父节点和爷爷节点在一条斜线上，进行旋转，都是左节点就右旋，都是右节点就左旋，最后变色。
-
case3：没有叔叔且新、父、爷不在一条斜线上，两次旋转，第一次旋转成case2，再按case2旋转一次，然后变色即可。
（4）二叉排序树的删除
删除二叉排序树的一个节点分为三种情况：
- 待删节点没有子节点，如节点1，直接删除即可。
- 待删节点有一个子节点，如节点2，将这个子节点(1)替代待删节点即可。
- 待删节点有两个子节点，如节点4，将待删节点与它中序遍历的后续节点(5)互换，然后删除此时新位置上的待删节点即可。
（5）★红黑树的删除
删除红黑树首先按照删除二叉排序树的三种情况：
-
首先是待删节点X没有子节点的情况，待删节点可能是黑色也可能是红色：
-
如果是红色的话，X的父节点一定是黑色且X没有兄弟，此时直接删除X就结束了；
-
如果X是黑色的话，那么X一定有兄弟，如果兄弟是黑色，那么兄弟就没有孩子，此时删除X，需要把黑兄弟变红；
-
如果兄弟是红色，那么兄弟就有俩黑色孩子，此时删除X需要旋转和变色（如最后一张图）。
-
如果是红色的话，X的父节点一定是黑色且X没有兄弟，此时直接删除X就结束了；
-
其次是待删节点X只有一个子节点，由红黑树的性质，只有一个子节点的节点，一定是父(X)黑子红的情况，此时删除X需要用子节点替代X的位置，并变为黑色：
-
最后是最麻烦一种，也就是待删节点X有两个子节点，这两个子节点分为两红、两黑、一红一黑的3种情况：
- 两红：删除X后需要用后继与X交换再删除现在的X，然后
- 两黑：
- 一红一黑：
（6）红黑树的应用
TreeMap、TreeSet以及JDK1.8的HashMap底层都用到了红黑树。
（7）二叉排序树(RST)、平衡二叉树(AVL)和红黑树(RBT)的比较？
二叉排序树在一般情况下，查找的时间复杂度是O(logn)，但是如果节点是递增或者递减的话，就退化成线性链表了，时间复杂度就成了O(n)，这属于二叉排序树的一大缺点。
平衡二叉树在二叉排序树的基础上，还要求左右子树高度差不能超过1，这样就能保证不会退化成线性链表了，但是它的问题是在插入和删除时，由于要保证严格的平衡，所以需要频繁旋转。
红黑树将节点分成红色和黑色两种，还要求了5个性质，它的平衡性比平衡二叉树弱一点，只要求满足红黑树的5条性质即可，不用严格保证高度差不超过1，因此查询时间上会比AVL慢一点。但是在插入和删除时，红黑树可以通过变色来代替旋转，这比平衡二叉树速度又快了一点儿。
综上所述，如果对于完全随机的数据，就能保证二叉排序树不退化，普通的二叉排序树就很好用；如果对于查询操作较多的情况，AVL比红黑树更胜一筹；但是综合考量的话，还是红黑树更好用，应用场景最广泛。
查看6道真题和解析
我现在也只有一个保底
太难了
