首先介绍一下红黑树的几点性质:
性质1:根节点是黑色
性质2:每个叶子节点是黑色(指的是空叶子节点)
性质3:每个红色节点的两个子节点一定是黑色
(子节点必须同时存在或不存在)
性质4:任意一节点到每个叶子节点的路径都包含数量相同的黑节点(非空叶子节点)
性质4.1:如果一个节点存在黑色子节点,那么该节点肯定有两个子节点(不然黑色失衡)
扩展5:不可能有两个相连的红节点
红黑树是二叉查找树,但不是完美平衡,只是黑色完美平衡。
红黑树通过三种方式达到自平衡:左旋、右旋、变色。
1.红黑树查找
因为红黑树是二叉查找树,所以满足二叉查找规则,如若不清楚,可参考博客AVL树原理剖析。
2.红黑树插入
3.红黑树节点的删除
以上就是红黑树最关键的理论部分,如若需要代码,请加文章开头的群号
