红黑树的简单了解

参考&＃xff1a;

https://www.sohu.com/a/201923614_466939 &＃xff08;漫画算法&＃xff0c;什么是红黑树&＃xff1f;&＃xff09;

https://blog.csdn.net/sun_tttt/article/details/65445754 &＃xff08;最容易懂得红黑树&＃xff09;

红黑树是一个平衡二叉树。

二叉查找树&＃xff08;BST&＃xff09;具备什么特性&＃xff1f;

1. 左子树上所有节点的值小于或等于它的根节点的值
2. 右子树上所有节点的值均大于或等于它的根节点的值
3. 左、右子树也分别为二叉排序树

红黑树是在普通二叉树上&＃xff0c;对每个节点添加一个颜色属性形成的&＃xff0c;同时整个红黑树需要同时满足一下五条性质&＃xff1a;

1. 节点是红色或者黑色
2. 根节点是黑色
3. 每个叶节点&＃xff08;NIT或空节点&＃xff09;是黑色
4. 每个红色节点的两个子节点都是黑色的&＃xff08;也就是说不存在两个连续的红色节点&＃xff09;
5. 从任一节点到每个叶节点的所有路径都包含相同数目的黑色节点

因为这些规则的限制&＃xff0c;才保证了红黑树的自平衡。

红黑树从根到叶子的最长路径不会超过最短路径的两倍。

当插入或者删除节点时&＃xff0c;为了维持红黑树的规则&＃xff0c;需要对红黑树做出调整。

调整方法主要是变色跟旋转&＃xff0c;旋转又分为左旋转和右旋转。