红黑树从概念到手撕实现：平衡树的折中智慧

红黑树的概念

概念：红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是 Red 或 Black

红黑树的性质

1. 每个结点不是红色就是黑色

2. 根节点是黑色的

3. 任何路径没有连续的红节点

4. 各路径黑节点的个数相同

5. 每个叶子结点都是黑色的 (此处的叶子结点指的是那个空结点)

这些性质让红黑树的最长路径长度不超过最短路径长度的 2 倍

–因为一红后面必会跟一黑，各路径黑节点的个数又是一样的

关于路径：从根节点到空节点算一条路径 (默认是这样的)

路径长度这一块的话，空节点不算上，根节点要算上

红黑树增删查改的时间复杂度也是 O(logN) --N 是节点个数

空树也可以是红黑树

AVL 树跟红黑树的比较

AVL 树和红黑树的在查找时的性能是同一量级的

但是 AVL 的平衡的控制在插入和删除时的旋转使用的次数很多

所以红黑树比 AVL 树好些，但是其实也大差不差

AVL 的话大量查找要优于红黑树 但是红黑树在各方面更加均衡一点

红黑树的模拟实现

enum Colour { RED, BLACK };
template <class K, class V>
struct RBTreeNode {
    RBTreeNode<K, V>* _left;
    RBTreeNode<K, V>* _right;
    RBTreeNode<K, V>* _parent;
    pair<K, V> _kv;
    Colour _col;

    RBTreeNode(const pair<K, V>& kv) :_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED) {}
};

template <class K, class V>
struct RBTree {
    typedef RBTreeNode<K, V> Node;
public:
    bool Insert( pair<K, V>& kv) {
         (_root == ) {
            _root =  (kv);
            _root->_col = BLACK;
             ;
        }
        Node* parent = ;
        Node* cur = _root;
         (cur) {
             (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            }   (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            }  {
                 ;
            }
        }
        cur =  (kv);
        cur->_col = RED; 
         (parent->_kv.first < kv.first) {
            parent->_right = cur;
        }  {
            parent->_left = cur;
        }
        cur->_parent = parent;

         (parent && parent->_col == RED) {
            Node* grandfather = parent->_parent;
             (parent == grandfather->_left) {
                Node* uncle = grandfather->_right; 
                 (uncle && uncle->_col == RED) {
                    
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    
                    cur = grandfather;
                    parent = cur->_parent;
                }  
                {
                     (cur == parent->_left) {
                        
                        (grandfather);
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    }  {
                        
                        (parent);
                        (grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    ;
                }
            }  
            {
                Node* uncle = grandfather->_left; 
                 (uncle && uncle->_col == RED) {
                    
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;
                    
                    cur = grandfather;
                    parent = cur->_parent;
                }  {
                     (cur == parent->_right) {
                        
                        (grandfather);
                        grandfather->_col = RED;
                        parent->_col = BLACK;
                    }  {
                        
                        (parent);
                        (grandfather);
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    ;
                }
            }
        }
        _root->_col = BLACK; 
         ;
    }
:
    Node* _root = ;
};