Last Updated: 2024-03-05 07:30:28 Tuesday
-- TOC --
相比AVL树，红黑树对Height的平衡性要求要弱一些，它只是近似平衡的二叉查找树。
AVL树1962年被提出，红黑树1972年被提出。上世纪七八十年代，是经典算法的黄金时代。
By constraining the node colors on any simple path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced. ---- 《CLRS》
这段描述path length的话，到底是基于什么前提下的？如果按照一般程序员的思维方式，每个节点或红或黑，数据可以存放在任意节点（非决策树），此时，假设从某个节点出发，左子树的黑高为n，右子树的黑高也是n，但是右子树在每层黑节点的前后，都多一层红节点，这样，左指数的高度为n-1（数edge），右子树的高度为2n。最坏路径可能是其他路径2倍多一点点....？比如下面这个红黑树：
由于放开了一点对Height平衡性的限制，在插入或删除数据时，rotation的频次相比AVL树就要少一些，因此红黑树的插入删除性能相对更高。相对应的，AVL树由于很严格的Height平衡要求，数据查询性能相对更优。
下面的图，只画了一侧，对称的另一侧没有画，请同学自己脑补。
所谓的Uncle为黑的情况（或者Uncle不存在）：
需要递归的情况：
本文链接：https://cs.pynote.net/ag/tree/202402189/
-- EOF --
-- MORE --