红黑树与AVL树的比较：
1.AVL树的时间复杂度虽然优于红黑树，但是对于现在的计算机，cpu太快，可以忽略性能差异2.红黑树的插入删除比AVL树更便于控制操作3.红黑树整体性能略优于AVL树（红黑树旋转情况少于AVL树）红黑树的性质：红黑树是一棵二叉搜索树，它在每个节点增加了一个存储位记录节点的颜色，可以是RED,也可以是BLACK；通过任意一条从根到叶子简单路径上颜色的约束，红黑树保证最长路径不超过最短路径的二倍，因而近似平衡。具体性质如下：每个节点颜色不是黑色，就是红色根节点是黑色的如果一个节点是红色，那么它的两个子节点就是黑色的（没有连续的红节点）对于每个节点，从该节点到其后代叶节点的简单路径上，均包含相同数目的黑色节点那么为什么当满足以上性质时，就能保证最长路径不超过最短路径的二倍了呢？我们分析一下：这里写图片描述你的最短路径就是全黑节点，最长路径就是一个红节点一个黑节点，最后黑色节点相同时，最长路径刚好是最短路径的两倍红黑树的插入：红黑树插入节点过程大致分析：RBTree为二叉搜索树，我们按照二叉搜索树的方法对其进行节点插入RBTree有颜色约束性质，因此我们在插入新节点之后要进行颜色调整具体步骤如下：根节点为NULL，直接插入新节点并将其颜色置为黑色根节点不为NULL，找到要插入新节点的位置插入新节点判断新插入节点对全树颜色的影响，更新调整颜色首先红黑树的插入其实不是那么容易实现的，以前搜索树的插入我们很容易理解现在我们首先思考一个问题，你插入节点的默认颜色是RED或BLACK？ 这里我们需要根据性质来思考，首先如果插入黑节点，这个可以直接插入无论它的父亲是什么颜色，但是红黑树的性质是每条路径的黑色节点数目相同这个时候你再想想那其他路径的黑色节点数目一定比你现在少一个节点，所以调整起来是非常繁琐的. 插入红节点不需要调整其他路径，如果它的父亲为黑，那么直接插入，如果他的父亲为红那么在该路径上面开始分情况调整. 所以插入节点默认颜色一定要为红.如果为黑调节成本太大了.接下来开始插入节点如果插入节点的父亲为黑那么直接插入后返回不需要做任何调整. 但是如果插入节点的父亲为红，那么就需要调整了.具体的调整过程可以分为三个情况：1.第一种情况cur为红，parent为红，pParent为黑，uncle存在且为红则将parent,uncle改为黑，pParent改为红，然后把pParent当成cur，继续向上调整。此时对该子树进行操作，parent节点和uncle节点变为黑，pParent节点变为红，这样我们就保证该子树中每条路径中黑色节点相同并且没有连续的红节点，然后再让cur等于pParent节点继续往上继续调整。这里写图片描述2. 第二种情况cur为红，parent为红，pParent为黑，uncle不存在/u为黑parent为pParent的左孩子，cur为parent的左孩子，则进行右单旋转；uncle不存在：这里写图片描述uncle存在且为黑：这里写图片描述相反，parent为pParent的右孩子，cur为parent的右孩子，则进行左单旋转；p、g变色–p变黑，g变红.uncle不存在：这里写图片描述uncle存在且为黑：这里写图片描述3.第三种情况cur为红，p为红，g为黑，u不存在/u为黑p为g的左孩子，cur为p的右孩子，则针对p做左单旋转则转换成了情况2uncle不存在：这里写图片描述uncle存在且为黑：这里写图片描述相反，p为g的右孩子，cur为p的左孩子，则针对p做右单旋转