RBTree::RBTree() { _root = new RBTreeRoot(); } RBTree::~RBTree() { delete _root; } /* * 对红黑树的节点(x)进行左旋转 * * 左旋示意图(对节点x进行左旋)： * px px * / / * x y * / \ --(左旋)--> / \ # * lx y x ry * / \ / \ * ly ry lx ly * * */ void RBTree::_left_rotate(struct RBTreeRoot *root, struct RBTreeNode *node) { struct RBTreeNode *right = node->rb_right, *parent = rb_parent(node); // 第一步：将ly连接到x的右结点上 rb_set_right(node, right->rb_left); // 第二步：将x设置为y的左子结点 rb_set_left(right, node); // 第三步：将y设置为px的子结点 if (parent) { if (rb_is_left(node, parent)) { rb_set_left(right, parent); } else { rb_set_right(right, parent); } } else { root->rb_node = right; // 根结点 } } /* * 对红黑树的节点(y)进行右旋转 * * 右旋示意图(对节点y进行左旋)： * py py * / / * y x * / \ --(右旋)--> / \ # * x ry lx y * / \ / \ # * lx rx rx ry * */ void RBTree::_right_rotate(struct RBTreeRoot *root, struct RBTreeNode *node) { struct RBTreeNode *left = node->rb_left, *parent = rb_parent(node); // 第一步：将rx设置为y的左子结点 rb_set_left(node, left->rb_right); // 第二步：将y设置为x的右子结点 rb_set_right(left, node); // 第三步：将x设置为py的子结点 if (parent) { if (rb_is_left(node, parent)) { rb_set_left(parent, left); } else { rb_set_right(parent, left); } } } void RBTree::_insert_node(struct RBTreeNode *node) { struct RBTreeNode *parent, *g_parent; // 满足性质4 while ((parent = rb_parent(node)) && rb_is_red(parent)) { g_parent = rb_parent(parent); if (rb_is_left(parent, g_parent)) { { // case 1：叔叔结点是红色 // 寄存器变量，提高效率 struct RBTreeNode *uncle = g_parent->rb_right; // 无法满足性质4 if (uncle && rb_is_red(uncle)) { // step1：将父亲和叔叔结点设置成黑色 rb_set_blacks(2, parent, uncle); // step2：将祖父设置成红色（因为之前必然为黑色，不然无法满足性质4） rb_set_red(g_parent); // step3：递归检查祖父结点 node = g_parent; continue; } } // 无法满足性质5 // case 2：叔叔结点是黑色，并且当前结点在右边，必然要进行双旋转 if (rb_is_right(node, parent)) { struct RBTreeNode *temp; // step 1：将父亲结点进行左旋 _left_rotate(_root, parent); // 此时父结点为当前结点的左子结点 // step 2：将当前结点和父结点进行交换 temp = parent; parent = node; node = temp; } // 此时父亲结点和当前结点均是红色，无法满足性质4和性质5 // case 3：叔叔结点是黑色，并且当前结点在左边，只用单旋转 // step 1：将父亲结点改成改成黑色，祖父结点改成红色，以便后面进行旋转后， // 红色的左子结点和祖父结点为黑色的父结点的子结点 rb_set_black(parent); rb_set_red(g_parent); // step 2：右旋转 _right_rotate(_root, g_parent); // 经过右旋转后，红色均分布在两边 } else { // 顺序相反而已 { // case 4：叔叔结点是红色 // 寄存器变量，提高效率 struct RBTreeNode *uncle = g_parent->rb_left; // 无法满足性质4 if (uncle && rb_is_red(uncle)) { // step1：将父亲和叔叔结点设置成黑色 rb_set_blacks(2, parent, uncle); // step2：将祖父设置成红色（因为之前必然为黑色，不然无法满足性质4） rb_set_red(g_parent); // step3：递归检查祖父结点 node = g_parent; continue; } } // 无法满足性质5 // case 5：叔叔结点是黑色，并且当前结点在左边，必然要进行双旋转 if (rb_is_left(node, parent)) { struct RBTreeNode *temp; // step 1：将父亲结点进行左旋 _right_rotate(_root, parent); // 此时父结点为当前结点的右子结点 // step 2：将当前结点和父结点进行交换 temp = parent; parent = node; node = temp; } // 此时父亲结点和当前结点均是红色，无法满足性质4和性质5 // case 3：叔叔结点是黑色，并且当前结点在右边，只用单旋转 // step 1：将父亲结点改成改成黑色，祖父结点改成红色，以便后面进行旋转后， // 红色的左子结点和祖父结点为黑色的父结点的子结点 rb_set_black(parent); rb_set_red(g_parent); // step 2：左旋转 _left_rotate(_root, g_parent); // 经过左旋转后，红色均分布在两边 } } } // 参照BST的插入方法 RBTreeNode* RBTree::insert_node(struct RBTreeNode *node) { struct RBTreeNode* temp = _root->rb_node; struct RBTreeNode* temp_parent = nullptr; while (temp != nullptr) { temp_parent = temp; if (node->rb_key < temp->rb_key) { temp = temp->rb_left; } else { temp = temp->rb_right; } } // 设置子结点 if (temp_parent != nullptr) { if (node->rb_key < temp_parent->rb_key) { rb_set_left(temp_parent, node); } else { rb_set_right(temp_parent, node); } } else { _root->rb_node = node; // 根结点 } return node; } void RBTree::insert(int val) { struct RBTreeNode* node = new RBTreeNode(val); node = this->insert_node(node); this->_insert_node(node); } void RBTree::_print(struct RBTreeNode* root) { if (root->rb_left) { _print(root->rb_left); } std::cout << root->rb_key << " "; if (root->rb_right) { _print(root->rb_right); } } void RBTree::print() { _print(_root->rb_node); }