红黑树操作详解——很形象的过程

红黑树是一种很好的自平衡二叉排序树,在此,给出一个网友给出的红黑树操作详解:

https://segmentfault.com/a/1190000012728513

里面给出了红黑树的详细操作,过程很形象!!!

结合可视化数据结构网站:

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

可以很好的理解红黑树的完整的插入,删除的过程。

总之,需要明白的是:红黑树是一种自平衡的二叉排序树,可以从其插入删除的过程体现,红黑树的自平衡性。

对于红黑树而言,需要体会这几点:

红黑树并不要求左右子树高度差最多差1(注意AVL树就需要这一点要求,其实红黑树左右子节点最多差2。

红黑树在插入删除的时候,最多执行三次旋转,便可以实现树的平衡性(AVL树可能需要更多次)。

也就是对于RB—Tree而言,插入和删除最多需要三次旋转操作,这实际上是一个很重要的特性,意味着对于节点的管理更加的易于维护!!!

实际 上,对于红黑树的优缺点,只有完全清楚其过程,才能体会这一点。

后续中:注意完成对红黑树与AVL树的对比;注意RB-Tree树的删除操作。

原文地址:https://www.cnblogs.com/shaonianpi/p/10616489.html