学习了LLRB有感，手撸了一个LLRB尝尝咸淡。(才不是ai神力呢)

#include <iostream>

template <typename T>  //T是类型名，可以是int, double, string
struct RBNode{
    T data;
    RBNode* left;
    RBNode* right;
    RBNode* parent;
    int color;   //define red as 1, black as 0

    RBNode(const T& d, int col = 1):data(d), left(nullptr), right(nullptr), 
    parent(nullptr), color(col){}
};

template <typename T>
class RBTree{
    private:
        RBNode<T>* root;
        RBNode<T>* nil;  // nil是叶子指向的空指针
       
        void initNil(){
            nil = new RBNode<T>(T(), 0);
            nil -> left = nil -> right = nil -> parent = nil;
        }

        RBNode<T>* rotateLeft(RBNode<T>* node){
            RBNode<T>* temp = node -> right;
            node -> right = temp -> left;
            
            if(node -> right != nil){
                node -> right -> parent = node;
            }
            
            temp -> parent = node -> parent;
            if(node -> parent == nil){
                root = temp;
            }
            else if(node == node -> parent -> left){
                node -> parent -> left = temp;
            }
            else{
                node -> parent -> right = temp; 
            }

            node -> parent = temp;
            temp -> left = node;
            int old_color = node -> color;
            node -> color = temp -> color;
            temp -> color = old_color;
            return temp;
        }


         RBNode<T>* rotateRight(RBNode<T>* node){
            RBNode<T>* temp = node -> left;
            node -> left = temp -> right;
            
            if(node -> left != nil){
                node -> left -> parent = node;
            }
            
            temp -> parent = node -> parent;
            if(node -> parent == nil){
                root = temp;
            }
            else if(node == node -> parent -> left){
                node -> parent -> left = temp;
            }
            else{
                node -> parent -> right = temp;
            }

            node -> parent = temp;
            temp -> right = node;
            int old_color = node -> color;
            node -> color = temp -> color;
            temp -> color = old_color;
            return temp;
        }

        void flipColor(RBNode<T>* node){
            node -> left -> color = 0;
            node -> right -> color = 0;     
            node -> color = 1;
        }

        void fixNode(RBNode<T>* node){
            RBNode<T>* temp = node -> parent;
            while(temp != nil){
                RBNode<T>* current_parent = temp -> parent;
                
                // 右边子节点为红，左边子节点为黑，作为左倾红黑树需要把节点向左转 
                if(temp -> left -> color == 0 && temp -> right -> color == 1){
                    temp = rotateLeft(temp);
                }
                
                // 子节点和孙节点都是红， 需要向右旋转
                if(temp -> left -> color == 1 && temp -> left -> left -> color == 1){
                    temp = rotateRight(temp);
                }
                
                // 右边子节点和左边子节点都是红，需要flipColor使两个子节点为黑，现在节点变红
                if(temp -> left -> color == 1 && temp -> right -> color == 1){
                    flipColor(temp);
                }

                temp = current_parent;
            }
            root -> color = 0;    
        }


    public:
        RBTree(){
            initNil();
            root = nil;
        }

        void addNode(const T& d){
            RBNode<T>* newNode = new RBNode<T>(d, 1);
            newNode -> left = newNode -> right = newNode -> parent = nil;

            RBNode<T>* x = root;
            RBNode<T>* y = nil;
            
            if(root == nil){
                root = newNode;
                root -> color = 0;
                return;
            }
            
            while(x != nil){
                y = x;
                if(x -> data > d){
                    x = x -> left;
                }
                else if(x -> data < d){
                    x = x -> right;
                }
                else{
                    std::cout << "already has a same node" << std::endl;
                    delete newNode;
                    return;
                } 
            }

            newNode -> parent = y;
            if(y -> data > d){
                y -> left = newNode;
            }
            else{
                y -> right = newNode;
            }

            fixNode(newNode);
        }
        // 有序输出
        void inorderPrint(RBNode<T>* node) {
            if (node == nil) return;
            inorderPrint(node -> left);
            std::cout << node -> data << "(" << (node -> color ? "R" : "B") << ") " ;
            inorderPrint(node -> right);
        }

        void printTree() { 
            inorderPrint(root);
        }

        void printRoot(){
            std::cout << root -> data << std::endl;
        }
};

int main(){
    RBTree<int> tree;//7, 3, 1, 5, 2, 4, 6
    tree.addNode(7);
    tree.addNode(3);
    tree.addNode(1);
    tree.addNode(5);
    tree.addNode(2);
    tree.addNode(4);
    tree.addNode(6);
    tree.printTree(); 
    return 0;
}