红黑树的知识点总结(概念 、 性质)
红黑树的概念
红黑树是二叉搜索树的一种，它在二叉搜索树的基础上给每个结点增加颜色，可以是红色或者是黑色，所以叫做红黑树。通过对对节点颜色的限制，红黑树确保了没有一条路径会比其他路径长出两倍，而达到接*衡。
红黑树的性质
- 每个节点只能是红色或者黑色
- 根节点必须是黑色的
- 如果一个结点是红色的，则它的两个孩子结点都要是黑色的
- 对于每个结点，从该节点到其所有后代叶结点的简单路径上，黑色节点的个数都相等
- 每个叶子结点都是黑色的（此处的叶子结点指的是空结点）
总结：
红黑树：二叉搜索数 + 给结点增加颜色（红 、 黑）+ 一些条件约束
不可能存在连在一起的红色结点，黑色结点可能会连在一起
插入 / 查找的时间复杂度（log2n）