上一篇中我们讲述了红黑树的插入, 以及删除时需要进行的各种调整的情况, 根据这些情况, 我们可以用代码实现红黑树的插入与删除操作.
节点的定义
一颗红黑树的定义如下:
// 定义颜色枚举类型
enum Color { RED, BLACK };
template <class T>
struct Red_Black_Node {
Red_Black_Node* left;
Red_Black_Node* right;
Red_Black_Node* parent;
//记录坐标, 用于打印
int x, y;
T value; // 节点的值, 红黑树中节点的值是必须可以改变的
Color node_color; // 节点的颜色
bool NIL; // 该节点是否是 NIL 节点
Red_Black_Node(T value, Color node_color, bool NIL); // 构造函数
void Set_Color(Color new_color);
void SetValue(T new_value);
// 将当前节点的父节点指向新的对应的孩子节点 new_child
void SetNewChild(Red_Black_Node* new_child);
Red_Black_Node* LeftRotate();
Red_Black_Node* RightRotate();
Red_Black_Node* GetUncle();
Red_Black_Node* GetSibling();
Red_Black_Node* GetCloseNephew();
Red_Black_Node* GetFarNephew();
};
为了在删除操作中简单化, 我们在节点的旋转与调整中引入了一些额外的操作, 例如 SetNewChild 函数, 表示替换当前节点的父节点的孩子节点为新的节点, 在后续删除当前节点的时候十分有用, 实现如下:
template <class T>
void Red_Black_Node<T>::SetNewChild(Red_Black_Node* new_child) {
if (this->parent == nullptr) {
return;
}
if (this == this->parent->left) {
this->parent->left = new_child;
}
else {
this->parent->right = new_child;
}
new_child->parent = this->parent;
}
还有, 在旋转的操作中, 我们也将旋转后的根节点的与父节点进行了连接, 实现如下:
// 以当前节点为根节点进行左旋转
template <class T>
Red_Black_Node<T>* Red_Black_Node<T>::LeftRotate() {
Red_Black_Node* temp_parent = this->parent;
Red_Black_Node* temp = this->right;
this->right->left->parent = this;
this->right = this->right->left;
this->parent = temp;
temp->left = this;
if (temp_parent != nullptr) {
if (this == temp_parent->left) {
temp_parent->left = temp;
}
else {
temp_parent->right = temp;
}
temp->parent = temp_parent;
}
else {
temp->parent = nullptr;
}
return temp;
}
这些操作极大的简化了后续插入与删除的过程中的调整操作.
红黑树的插入操作
红黑树也是二叉查找树的一种, 其插入的开始步骤与普通的二叉查找树相同, 只有在插入这个节点之后, 才需要对树的结构进行调整, 插入操作的整体步骤如下:
template <class T>
void Red_Black_Tree<T>::insert(T value) {
Red_Black_Node<T>* direct = this->root;
Red_Black_Node<T>* pre_direct = this->root;
// 找到插入的位置
while (direct != nullptr && direct->value != value && !direct->NIL) {
pre_direct = direct;
if (direct->value < value) {
direct = direct->right;
}
else {
direct = direct->left;
}
}
// 新建插入的节点
Red_Black_Node<T>* new_node = new Red_Black_Node<T>(value, Color::RED, false);
// 如果是空树, 设置新建节点为根节点
if (this->root == nullptr) {
// 根节点为黑色
new_node->Set_Color(Color::BLACK);
this->root = new_node;
Red_Black_Node<T>* new_left_node = new Red_Black_Node<T>(0, Color::BLACK, true);
Red_Black_Node<T>* new_right_node = new Red_Black_Node<T>(0, Color::BLACK, true);
this->root->left = new_left_node;
this->root->right = new_right_node;
return;
}
// 如果这个节点不是NIL节点, 该值已存在
if (!direct->NIL) {
return;
}
// 在正确的位置插入新建的节点
if (direct == pre_direct->left) {
Red_Black_Node<T>* new_right_node = new Red_Black_Node<T>(0, Color::BLACK, true);
new_node->left = pre_direct->left;
new_node->right = new_right_node;
pre_direct->left = new_node;
}
else {
Red_Black_Node<T>* new_left_node = new Red_Black_Node<T>(0, Color::BLACK, true);
new_node->right = pre_direct->right;
new_node->left = new_left_node;
pre_direct->right = new_node;
}
new_node->parent = pre_direct;
// 插入节点之后调整红黑树的结构
InsertBalanceAdjust(new_node);
}
红黑树结构的调整
将一个节点插入到红黑树中, 需要对树的结构进行调整, 按照 上一篇博客 所示, 我们列出了各种不同的情况下需要进行的调整操作, 这些情况如下:
template <class T>
int Red_Black_Tree<T>::InsertBalanceAction(Red_Black_Node<T>* node) {
// 走到根节点了, 将该节点设为根节点, 为黑色
if (node->parent == nullptr) {
return 0;
}
// 如果当前节点的父节点存在并且为黑色
if (node->parent->node_color == Color::BLACK) {
return 1;
}
// 如果父节点是红色
if (node->parent->node_color == Color::RED) {
// 因为父亲节点是红色节点, 就一定不是根节点, 所以当前节点一定存在叔叔节点
// 如果叔叔节点为红色
if (node->GetUncle()->node_color == Color::RED) {
return 2;
}
else {
// 如果叔叔节点为黑色, 需要判断该节点的旋转方向
if (node == node->parent->left && node->parent == node->parent->parent->left) {
return 3;
}
else if (node == node->parent->right && node->parent == node->parent->parent->right) {
return 4;
}
else if (node == node->parent->right && node->parent == node->parent->parent->left) {
return 5;
}
else if (node == node->parent->left && node->parent == node->parent->parent->right) {
return 6;
}
return -1;
}
}
return -1;
}
然后是我们后续进行调整的步骤, 我们列出每种调整步骤如下:
template <class T>
void Red_Black_Tree<T>::InsertBalanceAdjust(Red_Black_Node<T>* node) {
Red_Black_Node<T>* temp_node = nullptr;
switch (this->InsertBalanceAction(node))
{
case 0:
node->Set_Color(Color::BLACK);
break;
case 1:
node->Set_Color(Color::RED);
break;
case 2:
node->Set_Color(Color::RED);
node->parent->Set_Color(Color::BLACK);
node->GetUncle()->Set_Color(Color::BLACK);
InsertBalanceAdjust(node->parent->parent);
break;
case 3:
node->Set_Color(Color::RED);
node->parent->Set_Color(Color::BLACK);
node->parent->parent->Set_Color(Color::RED);
temp_node = node->parent->parent->RightRotate();
if (temp_node->parent == nullptr) {
this->root = temp_node;
}
break;
case 4:
node->Set_Color(Color::RED);
node->parent->Set_Color(Color::BLACK);
node->parent->parent->Set_Color(Color::RED);
temp_node = node->parent->parent->LeftRotate();
if (temp_node->parent == nullptr) {
this->root = temp_node;
}
break;
case 5:
node->Set_Color(Color::RED);
// node->parent->parent->Set_Color(Color::RED);
node->parent->parent->left = node->parent->LeftRotate();
// 实际问题被转换为case3 解决
InsertBalanceAdjust(node->left);
break;
case 6:
node->Set_Color(Color::RED);
node->parent->parent->Set_Color(Color::RED);
node->parent->parent->right = node->parent->RightRotate();
// 实际问题被转换为case4 解决
InsertBalanceAdjust(node->right);
default:
break;
}
}
请注意在 case5 与 case6中我们进行了转换, 但是转换之后, 需要调整的节点不是新插入的节点, 而是插入节点的孩子节点.
标签：node,parent,实现,Color,Black,红黑树,节点,Red From： https://www.cnblogs.com/wevolf/p/18406622