文章插图
如左图，8，13节点不平衡，对13节点进行LL右旋转，得到右图
文章插图
这时8，10是不平衡的，对8节点进行RR左旋转，得到右图 。
红黑树概念一种二叉查找树，但在每个节点增加一个存储位表示节点的颜色，可以是red或black（非红即黑） 。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制，红黑树确保没有一条路径会比其它路径长出两倍 。它是一种弱平衡二叉树，相对于要求严格的AVL树来说，它的旋转次数少，所以对于插入、删除操作较多的情况下，我们就用红黑树 。
文章插图
特点
- 每个节点非红即黑；
- 根节点是黑的；
- 每个叶节点(叶节点即树尾端NULL指针或NULL节点)都是黑的；
- 如果一个节点是红的,那么它的两儿子都是黑的；
- 对于任意节点而言，其到叶子点树NULL指针的每条路径都包含相同数目的黑节点；
- 高度始终保持在h = logn
- 一般插入的是红色结点
在红黑树的结点上添加20，刚开始作为50的左子结点，这样不符合红黑树的规则，并且这样的情况满足上面说的情况5，因此50结点会变成黑色，根结点右旋 。先完成右旋，再完成变色 。
文章插图
旋转
文章插图
变色
文章插图
继续添加结点200，首先会作为100的右结点添加，因此父结点和叔叔结点都变成黑色，祖父结点50变成红色，然后根节点不能为红色，因此继续变色，最后根节点变成黑色 。需要注意的是红色节点的子结点必须为黑色节点，但是没有规定黑色节点的子结点必须为红色，说明黑色节点下面子结点什么颜色都可以 。
文章插图
变色
文章插图
继续变色
文章插图
继续添加结点300，首先会作为子结点添加到200的右子结点，因此首先以插入结点的祖父结点100为支点发生左旋，然后变色，父结点200变成黑色，原祖父结点变成红色 。
文章插图
左旋
文章插图
变色
文章插图
继续添加结点150，首先会作为子结点添加到100的右子结点，因此父结点和叔叔结点变成黑色，祖父结点200变成红色，变完色后发现符合黑红树规则，无需再旋转或变色 。
文章插图
变色
文章插图
继续添加元素160，会先作为右结点挂在150下面，然后这种情况符合上面第五种，因此先按照祖父结点100为支点左旋，然后父结点变成黑色，原祖父结点变成红色，完后发现符合黑红树规则，无需再选择或变色 。
文章插图
左旋
文章插图
变色
文章插图
添加320到子结点，会首先挂在350下面，父结点是红色，叔叔结点（null）为黑色，由于当前结点在父结点的左边，因此先以父结点350为支点右旋，右旋后变成上面的第五种情况，因此先以祖父结点300左旋，然后父结点320变色为黑色，原祖父结点300变色为红色 。
文章插图
右旋
文章插图
左旋变色
推荐阅读
- 一文吃透JVM分代回收机制
- 一文看懂 Git 的底层工作原理
- 两年法考差1分通过，是不够努力吗，复习建议等一文全攻略
- 一文解析「小米大模型」
- 一文带您了解线性回归：多个变量之间的最佳拟合线的算法
- 主动离职，还能收获失业补助金？你不知的“隐藏”福利，一文解析！
- 为什么很多人都在吹ChatGPT改变世界？一文全面了解
- 一文带您了解向量数据库
- 一文读懂医保亲情账户
- 一文了解Redis哨兵模式