红黑树插入旋转四种情况学习

发表于 2022-01-11 11:33:25 by 月小升

完美测试地址
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
插入四种情况。默认新插入都是红色

1.Z是根节点

Z变色为黑色

2.Z的叔叔是红色

Z的父亲，祖父，叔叔 变色，
完美测试5,3,7,6

3.Z的叔叔是黑色，并局部呈现直线

3.1 旋转祖父，直线向右，向左旋，反过来向右
3.2 Z原来的父亲和祖父变色

7 3 9 11，13 这个测试中，下方单独的红色节点11，对应的叔叔为黑色因为9是黑色，所以11是9的孩子，11的另外一个孩子是空（黑色），这个空孩子是13的叔叔，所以13的叔叔是黑色的

4.Z的叔叔是黑色，并局部呈现三角形
父亲和祖父，和Z构成三角
Z的父亲向右旋转
发现和3一样了，对Z的父亲旋转

完美测试 7 3 9 11 10

https://www.bilibili.com/video/BV1t5411a7Rw?from=search&seid=10839704005243776513&spm_id_from=333.337.0.0

https://www.bilibili.com/video/BV1qK4y1M7Fg?p=11&spm_id_from=pageDriver

https://www.bilibili.com/video/BV1aK4y1W7yj/?spm_id_from=333.788.recommend_more_video.2

---

首发地址：月小升博客 – https://java-er.com/blog/red-black-tree-insert-and-rotate/
无特殊说明，文章均为月小升原创，欢迎转载，转载请注明本文地址，谢谢