红黑树构建,插入,删除以及代码-Go服务器开发

以下是关于红黑树（Red-Black Tree）的构建、插入、删除操作的详细说明及代码实现（C++示例）。红黑树是一种自平衡的二叉搜索树，通过颜色标记和旋转操作维持平衡，确保最坏情况下时间复杂度为 O(log n)。

1. 红黑树的性质

红黑树满足以下性质：

每个节点是红色或黑色。
根节点是黑色。
所有叶子节点（NIL节点）是黑色。
红色节点的子节点必须是黑色（即不能有连续红色节点）。
从任一节点到其每个叶子节点的路径包含相同数量的黑色节点（黑高相同）。

2. 红黑树的节点定义

enum Color { RED, BLACK };

template <typename T>
struct RBNode {
    T data;
    Color color;
    RBNode* left;
    RBNode* right;
    RBNode* parent;

    RBNode(T val) : data(val), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

3. 插入操作

步骤：

普通BST插入：按二叉搜索树规则插入新节点，初始颜色为红色。
颜色修正与旋转：若违反红黑树性质（如连续红色节点），通过变色和旋转修复。

代码实现：

template <typename T>
class RedBlackTree {
private:
    RBNode<T>* root;
    RBNode<T>* nil; // 哨兵NIL节点

    void leftRotate(RBNode<T>* x) {
        RBNode<T>* y = x->right;
        x->right = y->left;
        if (y->left != nil) y->left->parent = x;
        y->parent = x->parent;
        if (x->parent == nil) root = y;
        else if (x == x->parent->left) x->parent->left = y;
        else x->parent->right = y;
        y->left = x;
        x->parent = y;
    }

    void rightRotate(RBNode<T>* y) {
        // 对称实现类似左旋
    }

    void fixInsert(RBNode<T>* z) {
        while (z->parent->color == RED) {
            if (z->parent == z->parent->parent->left) {
                RBNode<T>* uncle = z->parent->parent->right;
                if (uncle && uncle.color == RED) { // Case 1: Uncle is red
                    z.parent.color = BLACK;         // Recolor parent and uncle
                    uncle.color = BLACK;           // Recolor grandpa to red and move up the tree.
                    z.parent.parent.color=RED;      // Move up to grandpa for further checks.
                    z=z.parent.parent;              // Continue fixing from grandpa upwards.
                } 
                else {                              // Case2/3: Uncle is black or NIL.
                    if(z==z.parent.right){          // Case2: Left-Right case - convert it into Left-Left case via rotation.
                        z=z.parent;                  
                        leftRotate(z);              
                    }                               // Now it's Left-Left case handled by case3.

                   /*Case3*/
                   swapColors(z.parent,z.grandParent);
                   rightRotate(grandParent);
               }
           } 
           else { /* Symmetric cases for right child */ }
       }
       root.color=BLACK;                            // Ensure root remains black after any insertion!
   }

public:
   void insert(T val){
       auto newNode=new Node(val,RED,nil,nil,nil);   // New nodes are always inserted as red initially!

       /* Standard BST Insertion */
       auto current=root,*prev=nil;

       while(current!=nil){
           prev=current;

           if(newVal < current.data)
               current=current.leftChild;

           else 
               current=current.rightChild;

       }

       newNode.parent=prev;

       if(prev==nil)
           root=new_node;

       else if(newVal < prev.data)
           prev.leftChild=new_node;

      else 
          prev.rightChild=new_node;

     /* Fix Red-Black Properties After Insertion */
     fixInsert(new_node);

     return true ;                                    
   }
};

4.删除操作

步骤:

1.Standard BST Deletion: Find the node to delete based on key value.

2.Fix Violations: If deleted node was black, perform rotations & recoloring to restore properties.

####Code Implementation:

void deleteFix(Node *x){

while(x!=root && x.colour==BLACK){

if(x==x.p.left){

auto w=x.p.right;//Sibling of X.

if(w.colour==RED){//Case1:Sibling is red.Make sibling black & rotate.

swapColors(w,x.p);

leftRotate(x.p);

w=x.p.right;//New sibling after rotation which will be black now.

}

if(w.left.colour==BLACK && w.right.colour==BLACK){//Case2:Sibling has two black children.Recolor sibling & move up.

w.colour=RED;

x=x.p;//Move up to parent for further checks.

}else{

if(w.right.colour==BLACK){//Case3:Convert into case4 via rotation & recolorings...

swapColors(w.left,w);

rightRotate(w);

w=x.p.right;//New sibling after rotation which will have a red right child now...

}

/*Case4*/

swapColors(w,x.p);//Final step where we make sure that extra blackness gets resolved properly via appropriate rotations/recolorings...

w.right.colour=BLACK;//Ensure no violation occurs at this level before moving upwards again...

leftRotate(x.p);//Perform final rotation around original parent of X...

break;//Terminate loop since all violations have been resolved here itself without needing further iterations upwards in tree hierarchy anymore now onwards too! :)

}}else{/*Symmetric Cases For Right Child*/}}

x.colour=BLACK;//Ensure final node being fixed becomes explicitly colored as such regardless its initial state prior entering this function call initially earlier on during execution time frame scope duration period etcetera... :) 

}

###5.Complexity Analysis