主页
红黑树的4条性质
- 任何节点非黑即红
- 所有叶子节点(NULL节点)都是黑色节点
- 一个红色节点没有红色子节点
- 从任何节点到其后代所有叶子节点(NULL节点)的每条路径都有相同数量的黑色节点
插入
所有插入操作都是在叶子结点进行的,插入节点默认为红色。
插入的6种情况及处理方法
- 1️⃣ 空树 👉 创建树,插入节点作为根节点,颜色改为黑色
- 2️⃣ 节点已经存在 👉 无需做处理
- 3️⃣ 父节点是黑色 👉 由于插入节点是红色,直接插入不会影响平衡
- ⤵ 父节点红
- 4️⃣ 叔叔节点为红色 👉 父亲和叔叔设置为黑色,祖父设置为红色,并把祖父当成插入节点向上递归
- ⤵ 叔叔节点不存在或为黑色
- 5️⃣ 插入节点与父节点顺边 👉 父亲、祖父颜色反转,对祖父做旋转
- 6️⃣ 插入节点与父节点反边 👉 旋转成顺边处理,得到情况5 ⤴
插入情况图示
删除
- 当删除的节点有两个子节点时,用右树最左节点或左树最右节点进行替换后,可以把情况转换成删除替换节点,这类替换节点只能是有0个或有1个子节点;
- 有一个子节点时,改节点必然是黑色,子节点是红色。(如果改节点是红色,则违反性质4;如果唯一子节点也是黑色,也会违反性质4)
- 没有子节点时,这种情况最复杂,需要看兄弟节点那边的情况;
删除的8种情况及处理方法
- 1️⃣ 空树 👉 无需做处理
- 2️⃣ 节点不存在 👉 无需做处理
- 3️⃣ 节点是红色 👉 直接删除
- ⤵ 节点是黑色
- 4️⃣ 有子节点 👉 把子节点改为黑色,并用子节点替换
- ⤵ 没有子节点
- 5️⃣ 兄弟节点是红色 👉 父节点变红,兄弟节点变黑,对父节点旋转,得到情况8 ⤵
- ⤵ 兄弟节点是黑色
- 6️⃣ 兄弟节点顺边子节点是红色 👉 将父节点和兄弟的顺边子节点设置为黑,兄弟节点设置为父节点颜色,并向替换节点方向旋转兄弟节点
- ⤵ 兄弟节点顺边子节点是黑色
- 7️⃣ 兄弟节点对边子节点是红色 👉 将兄弟对边子节点设为黑,兄弟节点设为红,对兄弟节点顺边旋转,得到情况6 ⤴
- 8️⃣ 兄弟节点对边子节点是黑色 👉 将兄弟节点设置为红,把父亲节点作为新的处理节点递归 ⤴