红黑树的添加
参考文章：高性能服务器开发公众号历史文章
本文只是个人的学习笔记
大致步骤：
首先将红黑树当作一棵二叉搜索树，将节点插入。
二叉搜索树的插入：就是要先确定节点的插入位置，依次从根节点开始比较，小就往左子树找，大就往右子树找，直到找到合适的位置，再更新待插入元素的父结点的孩子信息，和该元素的孩子信
息。
息。
然后，将节点着色为红色 why?
最后，通过旋转和重新着色等方法来修正该树，使之重新成为一棵红黑树（注：旋转和重新着色不会改变树的二叉搜索树的特性）
将节点着色为红色 why?
红黑树的特性之一：从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点
将节点着色为红色，就绝对不会打破这条特性。这样接下来就只要让树满足其他红黑树的特性即可
再列举一下红黑树的五个特性：
1.根节点是黑色
2.叶子节点是黑色（NULL）
3.每个红色节点的孩子一定是黑色
4.每个节点要么是红色，要么是黑色
5.从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点
注：二叉搜索树的插入操作不会改变根节点（这个....）
所以步骤的第二步不会改变根节点是黑色这一特性
在特性里的叶子节点和我们平时说二叉树的叶子节点不同，这里的叶子节点指的是空的叶子节点，插入有值的节点不会改变叶子节点是黑色这一特性
每个节点要么是红色，要么是黑色这一特性显然也不会被影响，因为我们第二步已经将节点着色为红色
综上，第二步骤可能改变的就是：不一定能保证每个红色节点的孩子一定是黑色。
插入分为三种情况来处理：
1.被插入的节点是根节点: 直接涂黑
2.被插入的节点的父节点是黑色：不用处理，节点插入后仍然是红黑树
3.被插入的节点的父节点是红色：违背了
投递腾讯等公司10个岗位 >
，校友加油