【Java集合进阶】数据结构(平衡二又树旋转机制)数据结构(红黑树、红黑规则、添加节点处理方案详解)

🍬 博主介绍👨‍🎓 博主介绍：大家好，我是 hacker-routing ，很高兴认识大家~
✨主攻领域：【渗透领域】【应急响应】 【Java】 【VulnHub靶场复现】【面试分析】
🎉点赞➕评论➕收藏 == 养成习惯（一键三连）😋
🎉欢迎关注💗一起学习👍一起讨论⭐️一起进步📝文末有彩蛋
🙏作者水平有限，欢迎各位大佬指点，相互学习进步！

---

目录

数据结构(平衡二又树旋转机制)

数据结构（平衡二叉树）左旋

数据结构（平衡二叉树）右旋

数据结构（平衡二叉树）需要旋转的四种情况

数据结构（平衡二叉树）小结

数据结构(红黑树、红黑规则、添加节点处理方案详解)

数据结构（红黑树）

数据结构（红黑树）红黑规则

数据结构（红黑树）添加节点的规则

---

数据结构(平衡二又树旋转机制)

数据结构（平衡二叉树）左旋

确定支点：从添加的节点开始，不断的往父节点找不平衡的节点

步骤：

1. 以不平衡的点作为支点
2. 把支点左旋降级，变成左子节点
3. 晋升原来的右子节点

旋转如下图：

数据结构（平衡二叉树）右旋

步骤：

1. 以不平衡的点作为支点

2. 把支点右旋降级，变成右子节点

3. 晋升原来的左子节点

数据结构（平衡二叉树）需要旋转的四种情况

左左：当根节点左子树的左子树有节点插入，导致二叉树不平衡

一次右旋解决

左右：当根节点左子树的右子树有节点插入，导致二叉树不平衡

解决：先局部左旋，再整体右旋

右右：当根节点右子树的右子树有节点插入，导致二叉树不平衡

解决：一次左旋

右左：当根节点右子树的左子树有节点插入，导致二叉树不平衡

解决：先局部右旋，再整体左旋

数据结构（平衡二叉树）小结

数据结构(红黑树、红黑规则、添加节点处理方案详解)

数据结构（红黑树）

1. 红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构
2. 1972年出现，当时被称之为平衡二叉B树。后来，1978年被修改为如今的"红黑树"
3. 它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色
4. 每一个节点可以是红或者黑;红黑树不是高度平衡的，它的平衡是通过"红黑规则"进行实现的

平衡二叉树：

1. 高度平衡
2. 当左右子树高度差超过1时，通过旋转保持平衡

红黑树：

1. 是一个二叉树但是不是高度平衡的
2. 条件：特有的红黑规则

数据结构（红黑树）红黑规则

1. 每一个节点或是红色的，或者是黑色的

2. 根节点必须是黑色

3. 如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些NiL视为叶节点，每个叶节点(Nil)是黑色的

4. 如果某一个节点是红色，那么它的子节点必须是黑色(不能出现两个红色节点相连的情况)

5. 对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点;

数据结构（红黑树）添加节点的规则

——红黑树在添加节点的时候，添加的节点默认是红色的