二叉搜索树-红黑树

前面介绍了AVL树，虽然AVL树将二叉树的高度差保证在1，但是实现的太过复杂，因为要不断调整平衡因子。故而要来介绍另外一个用途比较广的结构-红黑树。

红黑树

先来看来红黑树的特性：
1、每个节点非红即黑
2、根节点为黑色
3、不能有连续的红节点
4、每条路径上的黑色节点数相等
5、空节点为黑色

先来想一个问题，红黑树的定义保证它最长路径不会超过最短路径的二倍，那么来想想为什么？

节点的结构

因为搜索结构在实际运用当中都是采用这种Key,Value模型，所以这里就先这样实现，后面对RBTree进行封装时，会做一些小的调整。

enum COLOUR{RED,BLACK};

template <class K,class V>
struct RBTreeNode
{
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;//因为要涉及到调平衡，所以定义为三叉链
    K _key;
    V _value;
    COLOUR _colour;//枚举类型的颜色属性，每一个节点非红即黑
};

插入

基本的插入和之前的普通搜索树，AVL树都是一样的，先找到待插入位置，然后进行插入即可，主要的不同就是在动态调整。
至于旋转的过程，红黑树和AVL树都是一样的。
插入时需要注意的是，第四条规则：每条路径上的黑色节点数相等，所以我们可以在初始化节点的时候直接默认是红色的节点，这样就可以避免冲突这条规则。

下面这段代码在实现普通搜索树，AVL树，红黑树都是一样的。

        if (_root == NULL)//先判断空树的场景
        {
            Node* _root = new Node(key, value);
            _root->_colour = BLACK;
            return true;
        }

        Node* cur = _root;
        Node* parent = NULL;
        while (cur)
        {
            if (key < cur->_key)
            {
                parent = cur->_parent;
                cur = cur->_left;
            }
            else if (key > cur->_key)
            {
                parent = cur;
                cur = cur->_right;
            }
            else
            {
                assert(false);
            }
        }
        //走到这里，找到待插入点
        cur = new Node(key, value);
        if (key < cur->_key)
        {
            parent->_left = cur;
            cur->_parent = parent;
        }
        else if (key > cur->_key)
        {
            parent->_right = cur;
            cur->_parent = parent;
        }
        //走到这里说明节点插入进入了，核心的思想就是下面要进行的动态调整

动态调整

下面图示中cur代表当前节点，parent/p代表父节点，uncle/u代表叔叔节点，grandfather/g代表祖父节点。

一共分三种情况：

一：叔叔存在且为红