红黑树的小小心得【插入】

刚刚学了二叉树，突然又蹦出来一个“红黑树”，这里就是学习红黑树的一些小心得。
红黑树，从名字就可以看出来，这种数是由红和黑两种颜色来表示的。
首先需要了解红黑树的五个重要性质。
1.每一个节点要么是黑色要么就是红色；
2.根节点一定是黑色；
3.每一个叶子节点一定是黑色；
4.如果一个节点是红色，那么它的两个子节点都是黑色；
5.任一节点到其每个叶子的所有路径，都包含相同数目的黑色节点。
关于黑高度的定义：
从任何一个节点，向下到底部的路径中，包含的黑节点的个数，称为这个节点的黑高度。从红黑树的第５条性质可以看出，黑高度是唯一的、确定的。
只要同时满足红黑树的这些条件，就一定会有“红黑树可以保证任何两条从根部到树叶的路径节点个数相差不超过２倍”这个平衡的性质。
红黑树是一种特殊的二叉树，与普通的二叉树不同就是它的每一个节点都必须满足上面的五个性质，通过对于每条路径上节点颜色的规则进行限定，红黑树可以保证任何两条从根部到树叶的路径节点个数相差不超过２倍。所以，红黑树是一种近似平衡的二叉搜索树。
红黑树的查找、最大值、最小值、前趋、后继等操作，与普通的二叉搜索树没有什么区别。插入和删除操作需要重新实现。仅仅用普通的二叉搜索树的插入和删除动作，可能会破坏红黑树本身的一些性质，因此，需要进行额外的处理。这些额外的处理主要是改变树节点的颜色，或是改变树的结构。
红黑树的插入：
在插入节点时，首先将插入的节点设为红色，用普通二叉树的方法，将此节点插入到红黑树中，然后再想办法把被破坏的性质一一进行恢复。当一个红色的节点被插入时，只有两条性质可能被破坏，即性质2和性质4，如果插入后，其父节点是黑色，那么不需要进行改变，如果插入后发现其父节点是红色或者没有父节点（即在根节点上），那么就要对其进行调整。由此可见，其主要的恢复部分是性质4，那么接下来主要讨论下关于性质4的恢复情况分析。
情况1：插入的地方是根节点
这种情况下，直接把此节点改为黑色即可。
情况2：插入的节点的父节点是黑色
这种情况下没有任何错误。
情况3：插入的节点的父节点是红色，且其祖父节点的另一个子节点（叔叔节点）也是红色
这种情况下，又可以分为父节点是左儿子还是右儿子，根据其对称性，这里只考虑是左儿子的情况。
首先，把插入的节点的父节点和叔叔节点改为黑色，把祖父节点改为红色，再根据祖父节点的情况，往上继续检查，看是否符合红黑树的性质。
情况4：插入的节点的父节点是红色，其叔叔节点是黑色，并且插入节点为父节点的右儿子
这种情况下，不考虑插入的节点，以此节点的父节点为支点，进行左旋变化。
情况5：插入的节点的父节点是红色，其叔叔节点是黑色，并且插入节点为父节点的左儿子
这种情况下，将插入节点的父节点变为黑色，其祖父节点变为红色，并以祖父节点为支点，进行右旋改变。

 

不得不吐槽一下，找了一些图片说明，但是。。。插入图片太麻烦了，就不想插入了！留着下次写【删除】的时候再用吧！！