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

完美测试地址
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


This entry was posted in 数学与算法 and tagged , . Bookmark the permalink.
月小升QQ 2651044202, 技术交流QQ群 178491360
首发地址:月小升博客https://java-er.com/blog/red-black-tree-insert-and-rotate/
无特殊说明,文章均为月小升原创,欢迎转载,转载请注明本文地址,谢谢
您的评论是我写作的动力.

Leave a Reply

Your email address will not be published. Required fields are marked *

*

*