红黑树的特性
红黑树是一种自平衡二叉树，因为它必须满足如下性质：
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3 每个叶节点（NIL节点，空节点）是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的路径上包含的黑色节点数量都相同。
由于有这些性质存在，红黑树从根到最远叶子的路径长度不会超过从根到最近叶子路径长度的两倍
因此红黑树基本上是平衡的，不会出现那种二叉查找树非常极端地变成链表的场景
补链接图：红黑树样例
红黑树保证了有限度的平衡，且没有较高的平衡开销，原因如下：
红黑树可以是全黑的，如果有红节点，全黑路径一定是最短路径，而一红一黑相间的路径一定是最长路径（可以连黑，没有连红）
因为每条路径黑节点数量是相等的，因此最长路径一定不会超过最短路径的2倍
红黑树节点黑高：从节点出发（不含本身）到达任意NIL节点所经过的黑节点数量。
红黑树相比与AVL树的优势是插入性能更高，但查找性能没有很大减少：
插入方面：红黑树的插入和删除操作需要旋转的次数相对较少，因此在插入和删除操作频繁的情况下，红黑树可能更加高效。
查找方面：复杂度都是O(log2N）- 2O(log2N)，AVL树是严格O(log2N），但实际上常数项对于计算机效率没有多大影响，因此查找性能降低并不大
红黑树保证平衡的方法
保证平衡的方法
变色和左旋右旋
变色：改变节点的颜色。
旋转：
左旋：以某个节点为支点，将其右子节点旋转为它的父节点。
右旋：以某个节点为支点，将其左子节点旋转为它的父节点。
红黑树的插入方法
刚插入的新节点是红色的，因此违背了红黑树的特性，需要调整：
L1-如果插入节点没有父节点，当前插入的就是根，根节点置黑
L2-如果父节点为黑色或没有爷爷节点，不做任何处理
L3 -如果父节点为红色
L3.1-如果有叔叔节点且为黑色，叔叔父亲置黑爷爷置红
L3.2-没有叔叔节点或叔叔为红色
L3.2.1-先转父亲，如果父亲在左自己在右，则父亲左旋，如果父亲在右自己在左，则右旋（自己和父亲在异侧，向自己的异侧转）
L3.2.2-再转爷爷，爷爷必然要旋转，怎么旋转看父亲，父亲在左，爷爷右旋，父亲在右，爷爷左旋，同时父亲置黑爷爷置红（爷爷要向父亲的异侧转）
L4-然后从爷爷节点继续调整，直到调整到根
具体可以参考HashMap代码
红黑树左旋/右旋规律
对侧的同侧孙子升级为自己的对侧孩子
对侧孩子占自己的位置
自己成为对侧孩子的同侧孩子
评论区