免费：三天三夜整理最难数据结构（红黑树）之理论篇

三天三夜整理最难数据结构（红黑树）之理论篇

前言

同学们都非常好奇校园的门禁系统、车站中的身份证识别系统和我们经常使用的查单词，背单词（百词斩，百度翻译）的软件是怎么设计出来的，其底层就是红黑树的K_Val模型，现在机会来了，阅读完本文，你将达到设计诸如此类系统的入门要求
其实，如果有学过数据结构的小伙伴肯定会说，顺序表和链表也可以用来存储数据然后来做这个呀，其实不然，如果采用顺序表或者链表来做这个的话，那么效率就会特别低，举个例子：如果用顺序表或者链表来做这个的话，那么如果需要存储1亿个单词及其中文意思，那么我们在查找的时候，系统就需要去内存中查找1亿次，才能得出结果，但是利用红黑树来做的话，只需要查找几十次就可以得出结果了，其所需要的时候是非常短的，因此，学习红黑树就显得非常重要了。

二话不说，先上一棵红黑树示意图！！！

本节主要内容

红黑树的性质

红黑树中数据的插入（分类讨论）

总结

红黑树的性质

1. 树中的结点的颜色不是红色就是黑色
2. 树的根节点一定是黑色
3. 红色结点的两个孩子一定是黑色的（红黑树中不能出现连续的红色结点）
4. 树中的任意结点到叶子结点的所有简单路径的黑色结点的数量都是一样的
5. 树中的叶子结点（空结点）的颜色是黑色的

思考：为什么满足上面的性质，红黑树就能保证：其最长路径中节点个数不会超过最短路径节点个数的两倍？
答：由红黑树的性质，我们不难得出：
树中的最长路径就是红色结点比较多的路径，又由于红色结点的两个孩子的颜色一定是黑色的（不能出现连续的红色结点），因此最极端的红黑树中最长的路径的情况就应该是红色与黑色的结点交替出现的情况
最极端的红黑树中的最短路径就应该是黑色结点比较多的路径，那么最极端的情况就是最短路径中的结点都是黑色的
我们这里处理最极端的最长路径与最短路径的情况：
最短路径的情况：路径中只有黑色的结点，数量记为x,因为红黑树的性质，从一个结点出发到叶子结点的所有简单路径的黑色结点的数量是一样的，因此，在最长的路径中所包含的黑色结点的数量和最短路径的黑色结点的数量是相同的,即为x,那么由于最长路径的情况就是红色结点和黑色结点是交替出现的，因此，最长路径中红色结点的数量和黑色结点的数量是相同的，也为x。
因此，
最短路径中结点的数量 = 黑色结点的数量+红色结点的数量 = x + 0 = x
最长路径中结点的数量 = 黑色结点的数量+红色结点的数量 = x + x = 2x
故
最长路径中结点的数量 / 最短路径中结点的数量 = 2x / x = 2
其他情况就是，最长路径中的黑色结点的数量会增加，最短路径中红色结点的数量会增加，其比值小于2