✨✨所属专栏：C++✨✨
✨✨作者主页：嶔某✨✨
红⿊树的概念
红⿊树是⼀棵⼆叉搜索树，他的每个结点增加⼀个存储位来表示结点的颜⾊，可以是红⾊或者⿊⾊。 通过对任何⼀条从根到叶⼦的路径上各个结点的颜⾊进⾏约束，红⿊树确保没有⼀条路径会⽐其他路径⻓出2倍，因⽽是接近平衡的。
红⿊树的规则
1. 每个结点不是红⾊就是⿊⾊
2. 根结点是⿊⾊的
3. 如果⼀个结点是红⾊的，则它的两个孩⼦结点必须是⿊⾊的，也就是说任意⼀条路径不会有连续的红⾊结点。
4. 对于任意⼀个结点，从该结点到其所有NULL结点的简单路径上，均包含相同数量的⿊⾊结点
思考⼀下，红⿊树如何确保最⻓路径不超过最短路径的2倍的？
• 由规则4可知，从根到NULL结点的每条路径都有相同数量的⿊⾊结点，所以极端场景下，最短路径就就是全是⿊⾊结点的路径，假设最短路径⻓度为bh(black height)。
• 由规则2和规则3可知，任意⼀条路径不会有连续的红⾊结点，所以极端场景下，最⻓的路径就是⼀⿊⼀红间隔组成，那么最⻓路径的⻓度为2*bh。
• 综合红⿊树的4点规则⽽⾔，理论上的全⿊最短路径和⼀⿊⼀红的最⻓路径并不是在每棵红⿊树都存在的。假设任意⼀条从根到NULL结点路径的⻓度为x，那么bh <= h <= 2*bh。
红⿊树的效率
假设N是红⿊树树中结点数量，h最短路径的⻓度，那么 , 由此推出 ，也就是意味着红⿊树增删查改最坏也就是⾛最⻓路径 ，那么时间复杂度还是 。 2^h − 1 <= N < 2^(2∗h) − 1 由此推出h ≈ logN 也就是意味着红黑树增删查改最坏也就是走最长路径2 ∗ logN 那么时间复杂度还是O(logN)
红⿊树的表达相对AVL树要抽象⼀些，AVL树通过⾼度差直观的控