红黑树|定义、左旋函数、右旋函数和对插入结点的修复

1.红黑树类的定义

enum class Color
{RED,BLACK
};template<typename Key ,typename Value>
class RedBlackTree
{class Node {public:Key key;Value value;Color color;Node* left;Node* right;Node* parent;Node():color(Color::BLACK),left(NULL),right(NULL),parent(NULL){}Node(const Key&key,const Value&value,Color color,Node*p=NULL):key(key),value(value),color(color),left(NULL),right(NULL),parent(p){}};private:Node* root;size_t size;Node* Nil;};

2.左旋函数和右旋函数

//右旋函数
void rightRotate(Node* node)
{Node* p = node->left;//处理p的右孩子node->left = p->right;if (p->right != NULL)p->right->parent->node;//把p置为老大p->parent = node->parent;if (node->parent == NULL)root = p;if (node == node->parent->left)node->parent->left = p;else if (node == node->parent->right)node->parent->right = p;//让node成为p的右孩子p->right = node;node->parent = p;
}//左旋函数
void leftRotate(Node* node)
{Node* p = node->right;node->right = p->left;if (p->left != NULL)p->left->parent = node;p->parent = node->parent;if (node->parent == NULL)root = p;if (node == node->parent->left)node->parent->left = p;else if (node == node->parent->right)node->parent->right = p;p->left = node;node->parent = p;
}

3.对插入结点的修复

void insertFixup(Node*target)
{while (target->parent != NULL && target->parent->color == Color::RED){//父为祖左节点if (target->parent = target->parent->parent->left){Node* uncle = target->parent->parent->right;//红叔if (uncle && uncle->color == Color::RED){uncle->color == Color::BLACK;target->parent->color == Color::BLACK;target->parent->parent->color = Color::RED;target = target->parent->parent;}//黑叔else{//LRif (target == target->parent->right){leftRotate(target->parent);rightRotate(target->parent);target->color = Color::BLACK;target->right->color = Color::RED;}//LLelse if (target == target->parent->left){rightRotate(target->parent->parent);target->parent->color = Color::BLACK;target->parent->right->color = Color::RED;}}}//父为祖的右节点else{Node* uncle = target->parent->left;//红叔if (uncle && uncle->color == Color::RED){uncle->color == Color::BLACK;target->parent->color == Color::BLACK;target->parent->parent->color = Color::RED;target = target->parent->parent;}//黑叔else{//RLif (target == target->parent->left){rightRotate(target->parent);leftRotate(target->parent);target->color = Color::BLACK;target->left->color = Color::RED;}//RRelse if (target == target->parent->right){leftRotate(target->parent->parent);target->parent->color = Color::BLACK;target->parent->left->color = Color::RED;}}	}}root->color = Color::BLACK;
}