关于红黑树的删除方式，网络上是众说纷纭，自己总结整理了一下，关于红黑树的性质不再重述，直接上代码，请查看删除部分的注释（delete_node_adjust函数）：
#include <vector>
#include <iostream>
const int red_node = 2;
const int black_node = 1;
struct Node
{
Node(int key) : data_value(key), node_color(red_node), parent(NULL), left_child(NULL), right_child(NULL)
{
std::cout << "Node Construct" << key << std::endl;
}
~Node()
{
std::cout << "Node Destruct" << data_value << std::endl;
}
int data_value;
int node_color;
Node* parent;
Node* left_child;
Node* right_child;
};
class RedBlackTree
{
public:
RedBlackTree() : pRoot(NULL)
{
}
~RedBlackTree()
{
release();
}
public:
void insert_node(int key);
void release();
Node* search(int key);
void delete_node(int key);
void print_pre_order();
void left_rotate(int key);
void right_rotate(int key);
private:
void release(Node** pNode);
void insert_node(int key, Node** pNode, Node* pParent);
void insert_node_adjust(Node* pNode);
Node* search(int key, Node* pNode);
void delete_node(Node* pNode);
void delete_node_adjust(Node* pNode);
void print_pre_order(Node** pNode);
void left_rotate(Node* pNode);
void right_rotate(Node* pNode);
private:
Node* pRoot;
};
void RedBlackTree::delete_node(int key)
{
Node* pNode = search(key);
if (!pNode)
{
std::cout << "no node value is " << key << std::endl;
return;
}
delete_node(pNode);
return;
}
void RedBlackTree::delete_node(Node* pNode)
{
Node* pDeleteNode = pNode;
if (pNode->left_child && pNode->right_child)
{
Node* pLeftNode = pNode->right_child;
while (pLeftNode->left_child)
{
pLeftNode = pLeftNode->left_child;
}
pDeleteNode = pLeftNode;
int temp_value = pNode->data_value;
pNode->data_value = pLeftNode->data_value;
pLeftNode->data_value = temp_value;
delete_node(pLeftNode);
return;
}
else if (pNode->left_child)
{
if (pNode->parent)
{
if (pNode == pNode->parent->left_child)
{
pNode->parent->left_child = pNode->left_child;
}
else
{
pNode->parent->right_child = pNode->left_child;
}
}
else
{
pRoot = pNode->left_child;
}
}
else if (pNode->right_child)
{
if (pNode->parent)
{
if (pNode == pNode->parent->left_child)
{
pNode->parent->left_child = pNode->right_child;
}
else
{
pNode->parent->right_child = pNode->right_child;
}
}
else
{
pRoot = pNode->right_child;
}
}
else
{
if (pNode->parent)
{
if (pNode == pNode->parent->left_child)
{
pNode->parent->left_child = NULL;
}
else
{
pNode->parent->right_child = NULL;
}
}
else
{
pRoot = NULL;
}
}
delete_node_adjust(pDeleteNode);
if (pRoot)
{
pRoot->node_color = black_node;
}
delete pDeleteNode;
return;
}
void RedBlackTree::delete_node_adjust(Node* pDeleteNode)
{
if (red_node == pDeleteNode->node_color || !pDeleteNode->parent)
{
// 替换节点是红色或者黑色根节点
return;
}
// 替换节点是黑色、非根节点
Node* pParent = pDeleteNode->parent;
if (pDeleteNode == pParent->left_child)
{
Node* pBrotherNode = pParent->right_child;
if (red_node == pBrotherNode->node_color)
{
// 场景1 : 兄弟节点是红色，则父节点和其子节点均为黑色，处理方式是：
// step 1 : 将兄弟节点置黑，父节点置红
pParent->node_color = red_node;
pBrotherNode->node_color = black_node;
// step 2 : 对父节点左旋
left_rotate(pParent);
// step 3 : 重置兄弟节点，进入下一轮的判断
pBrotherNode = pParent->right_child;
}
if ((!pBrotherNode->left_child || black_node == pBrotherNode->left_child->node_color) && (!pBrotherNode->right_child || black_node == pBrotherNode->right_child->node_color))
{
// 场景 2 : 兄弟节点为黑色，并且，兄弟节点的子节点要么不存在、要么为黑，但不会为红色，该种情况下，只能向上传递、迭代处理父节点，无论通过旋转方式解决，所以：
// step 1 : 兄弟节点置红
pBrotherNode->node_color = red_node;
// step 2 : 此时替换节点和兄弟节点平衡，然后对父节点迭代处理
pDeleteNode = pParent;
delete_node_adjust(pDeleteNode);
return;
}
else
{
// 场景 3 : 兄弟节点为黑色，但是，兄弟节点的子节点存在为红色的情况，该种情况下，可通过旋转的方式解决Ｒ蛭婊唤诘闶亲蠼诘悖韵氩捎米笮姆绞嚼创恚矗? // 判断红色子节点是不是兄弟节点的右子节点，如果是则直接处理，否则，要先将其旋转到右侧，所以
// step 1 : 判断发现兄弟节点只有一个红色的子节点，并且是左节点，则着色、右旋处理
if (!pBrotherNode->right_child || black_node == pBrotherNode->right_child->node_color)
{
// 黑兄弟有红色左子节点，通过旋转，转换为红色右子节点，最后更新兄弟节点
pBrotherNode->node_color = red_node;
pBrotherNode->left_child->node_color = black_node;
right_rotate(pBrotherNode);
pBrotherNode = pParent->right_child;
}
// step 2 : 对于红色的右子节点，兄弟节点先继承父节点颜色，再置黑，旋转
pBrotherNode->node_color = pBrotherNode->parent->node_color;
pBrotherNode->parent->node_color = black_node;
pBrotherNode->right_child->node_color = black_node;
left_rotate(pBrotherNode->parent);
return;
}
}
else
{
Node* pBrotherNode = pParent->left_child;
if (red_node == pBrotherNode->node_color)
{
// parent and brother's childs must be black
pParent->node_color = red_node;
pBrotherNode->node_color = black_node;
right_rotate(pParent);
pBrotherNode = pParent->left_child;
}
if ((!pBrotherNode->left_child || black_node == pBrotherNode->left_child->node_color) && (!pBrotherNode->right_child || black_node == pBrotherNode->right_child->node_color))
{
pBrotherNode->node_color = red_node;
pDeleteNode = pParent;
delete_node_adjust(pDeleteNode);
return;
}
else
{
if (!pBrotherNode->left_child || black_node == pBrotherNode->left_child->node_color)
{
// 黑兄弟有红色右子节点
pBrotherNode->node_color = red_node;
pBrotherNode->right_child->node_color = black_node;
left_rotate(pBrotherNode);
pBrotherNode = pParent->left_child;
}
// 黑兄弟有红色左子节点
pBrotherNode->node_color = pBrotherNode->parent->node_color;
pBrotherNode->parent->node_color = black_node;
pBrotherNode->left_child->node_color = black_node;
right_rotate(pBrotherNode->parent);
return;
}
}
return;
}
void RedBlackTree::release()
{
release(&pRoot);
return;
}
void RedBlackTree::release(Node** pNode)
{
if (*pNode)
{
release(&(*pNode)->left_child);
release(&(*pNode)->right_child);
delete *pNode;
*pNode = NULL;
}
return;
}
void RedBlackTree::insert_node(int key)
{
insert_node(key, &pRoot, NULL);
return;
}
void RedBlackTree::insert_node(int key, Node** pNode, Node* pParent)
{
if (!*pNode)
{
*pNode = new Node(key);
(*pNode)->parent = pParent;
insert_node_adjust(*pNode);
}
else
{
if (key > (*pNode)->data_value)
{
// insert right node
insert_node(key, &((*pNode)->right_child), *pNode);
}
else if (key < (*pNode)->data_value)
{
// insert left node
insert_node(key, &((*pNode)->left_child), *pNode);
}
}
return;
}
void RedBlackTree::insert_node_adjust(Node* pNode)
{
// adjust inserted node's color
if (!pNode->parent)
{
// root node must be black
pNode->node_color = black_node;
}
else
{
if (black_node == pNode->parent->node_color)
{
// do nothing
}
else
{
Node* pGParent = pNode->parent->parent ? pNode->parent->parent : NULL;
if (pGParent)
{
Node* pUnic = pGParent->left_child == pNode->parent ? pGParent->right_child : pGParent->left_child;
if (pUnic && red_node == pUnic->node_color)
{
// parent and uncle to be black, gparent to be red
pGParent->node_color = red_node;
pUnic->node_color = black_node;
pNode->parent->node_color = black_node;
insert_node_adjust(pGParent);
return;
}
else if (!pUnic || black_node == pUnic->node_color)
{
if (pNode == pNode->parent->right_child && pNode->parent == pGParent->left_child)
{
// right node to left rotate
left_rotate(pNode->parent);
}
else if (pNode == pNode->parent->left_child && pNode->parent == pGParent->right_child)
{
right_rotate(pNode->parent);
}
else
{
pGParent->node_color = red_node;
pNode->parent->node_color = black_node;
if (pNode == pNode->parent->left_child && pNode->parent == pGParent->left_child)
{
right_rotate(pGParent);
}
else
{
left_rotate(pGParent);
}
}
}
}
}
}
return;
}
Node* RedBlackTree::search(int key)
{
return search(key, pRoot);
}
Node* RedBlackTree::search(int key, Node* pNode)
{
if (pNode)
{
if (pNode->data_value == key)
{
return pNode;
}
else if (pNode->data_value > key)
{
return search(key, pNode->left_child);
}
else
{
return search(key, pNode->right_child);
}
}
return NULL;
}
void RedBlackTree::print_pre_order()
{
print_pre_order(&pRoot);
std::cout << " root = " << (pRoot ? pRoot->data_value : -1) << std::endl;
return;
}
void RedBlackTree::print_pre_order(Node** pNode)
{
if (*pNode)
{
std::cout << (*pNode)->data_value << "(" << (*pNode)->node_color << ")" << " ";
print_pre_order(&(*pNode)->left_child);
print_pre_order(&(*pNode)->right_child);
}
return;
}
void RedBlackTree::left_rotate(int key)
{
Node* pNode = search(key);
if (pNode)
{
left_rotate(pNode);
}
return;
}
void RedBlackTree::left_rotate(Node* pNode)
{
Node* pRightNode = pNode->right_child;
if (!pRightNode)
{
return;
}
// left rotate has three steps, x is targeting node; y is x's right subnode; three steps's order must't be adjusted
// step 1 : y to x->parent's subnode
if (pNode->parent)
{
if (pNode == pNode->parent->left_child)
{
pNode->parent->left_child = pRightNode;
}
else if (pNode == pNode->parent->right_child)
{
pNode->parent->right_child = pRightNode;
}
}
else
{
*(&pRoot) = pRightNode;
}
pRightNode->parent = pNode->parent;
// step 2 : y's left_child to x's rightnode
pNode->right_child = pRightNode->left_child;
if (pRightNode->left_child)
{
pRightNode->left_child->parent = pNode;
}
// step 3 : y to x's parent
pNode->parent = pRightNode;
pRightNode->left_child = pNode;
return;
}
void RedBlackTree::right_rotate(int key)
{
Node* pNode = search(key);
if (pNode)
{
right_rotate(pNode);
}
return;
}
void RedBlackTree::right_rotate(Node* pNode)
{
Node* pLeftNode = pNode->left_child;
if (!pLeftNode)
{
return;
}
// right rotate has three steps, x is targeting node; y is x's left subnode; three steps's order must't be adjusted
// step 1 : y to x->parent's subnode
if (pNode->parent)
{
if (pNode == pNode->parent->left_child)
{
pNode->parent->left_child = pLeftNode;
}
else if (pNode == pNode->parent->right_child)
{
pNode->parent->right_child = pLeftNode;
}
}
else
{
*(&pRoot) = pLeftNode;
}
pLeftNode->parent = pNode->parent;
// step 2 : y's right subnode to x's left subnode
if (pLeftNode->right_child)
{
pLeftNode->right_child->parent = pNode;
}
pNode->left_child = pLeftNode->right_child;
// step 3 : y to x's parent, x to y's right subnode
pNode->parent = pLeftNode;
pLeftNode->right_child = pNode;
return;
}
int main()
{
RedBlackTree rbt;
std::vector<int> vec = {10, 6, 14, 5, 8, 11, 18, 19};
for (auto& element : vec)
{
rbt.insert_node(element);
}
rbt.print_pre_order();
rbt.delete_node(6);
rbt.print_pre_order();
return 0;
}
参考网址：
http://www.iteye.com/topic/1119331
相关推荐
总结，红黑树通过特定的颜色规则和旋转策略，实现了在插入和删除操作后的快速平衡，从而保证了查找、插入和删除的高效性。理解这些原则对于理解和实现红黑树至关重要，特别是在STL等高级库中，红黑树常用于实现高效...
`RBTree.h`是头文件，其中会定义红黑树节点的结构体（通常命名为`Node`）和红黑树类（如`RedBlackTree`）。结构体中，每个节点可能包含以下成员： 1. `int key`: 存储节点的关键值，用于比较和查找。 2. `bool ...
红黑树的插入、删除和查找操作都是基于节点的颜色和结构进行的。红黑树的颜色可以是红色或黑色，红色节点表示它的子节点都是黑色，黑色节点表示它的子节点都是红色。 插入操作中，首先需要找到合适的插入位置，然后...
- 删除节点时可能破坏红黑树的性质，需要通过复杂的步骤来恢复，包括替换、重新着色和旋转。 - 删除黑色节点可能导致某些路径上的黑色节点数量减少，需要通过调整来保持平衡。 5. **查找操作**： - 红黑树的查找...
1. 数据结构：首先，我们需要定义一个表示红黑树节点的结构体，它通常包含键值、颜色、左子节点、右子节点以及父节点等字段。例如： ```c typedef enum {RED, BLACK} Color; struct Node { int key; Color ...
1. **myrbtree.c**：这是红黑树的主要实现文件，包含了红黑树节点的定义、插入、删除和查找等操作的代码。其中，节点通常包含键值、颜色、左子节点、右子节点以及父节点等字段。插入和删除操作需要保证红黑树的性质...
在"红黑树代码实现及分析"这个主题中，你可以找到关于红黑树的具体实现细节，包括如何初始化树、插入和删除节点的步骤，以及如何进行颜色翻转和旋转等操作。通过分析这些代码，你可以更好地理解红黑树的工作原理，并...
实现红黑树通常涉及到定义节点结构，包括颜色字段、键值、指针等。同时，需要编写插入、删除和查找的函数，以及维护红黑性质的调整代码。在提供的“红黑树.txt”文件中，可能包含了红黑树的具体源代码实现，可以...
在实际的C++实现中，我们通常会定义一个红黑树类，封装节点的创建、插入、删除、查找等方法，并提供友好的接口供用户使用。同时，为了提高代码的可读性和可维护性，可以采用模板类的方式，使红黑树可以处理不同类型...
在给定的文件中，"rbtree.cpp"很可能是实现红黑树节点定义和操作的代码，包括旋转、颜色调整、插入和删除等功能。"main.cpp"则是测试和驱动程序，用于验证红黑树实现的正确性。"rbtree.h"可能包含了红黑树的类定义和...
红黑树的平衡策略主要依赖于旋转操作：左旋、右旋、颜色翻转等，这些操作用于在插入和删除节点后调整树的结构，以确保红黑树的性质得以保持。 在"红黑树完整实现文件"中，可能包含了以下内容： 1. **节点结构**：...
实验1：实现红黑树的基本算法， 对n的取值分别为 12、24、36、48、60，随机生成n 个互异的正整数（K1, K2, K3, ……, Kn）作为节点的关键字，向一棵初始空的红黑树中依次插入这n 个节点，统计算法运行所需时间 ，画...
在实际编程中，红黑树的删除操作往往伴随着复杂的逻辑判断和树结构调整，因此理解和实现红黑树的删除操作对提升数据结构和算法能力非常有帮助。通过阅读开源代码，如Java的`java.util.TreeMap`源码，可以深入理解这...
红黑树的链表实现意味着每个节点都通过指针连接，形成链式结构，这与数组实现相比，可以动态地调整大小并支持高效的插入和删除操作，但需要额外的空间来存储指针。 在实际编程中，理解红黑树的工作原理及其插入、...
- 在C++中，红黑树的实现通常会定义一个包含颜色属性的节点结构体，如`struct Node { int key; bool color; Node* left; Node* right; Node* parent; }`。 - `RedBlackTree.cpp`文件可能包含了红黑树的所有操作...
- `Node`结构体：定义红黑树节点，包括键值、颜色、左右子节点和父节点。 - `RedBlackTree`类：包含插入操作的方法，以及可能的旋转和颜色翻转函数。 - 主函数`main`：用于测试红黑树的插入功能，可以调整数据量以...
在实际应用中，红黑树常用于实现STL中的`std::map`和`std::set`，以及内存管理的哈希表等数据结构，因为它提供了高效的查找、插入和删除操作。在C++中，理解和实现红黑树可以帮助开发者深入掌握数据结构和算法，提升...
2. **删除红色节点**：可以通过调整相邻节点的颜色来恢复红黑树的性质。 3. **删除黑色内部节点**：这是最复杂的情况，需要通过一系列操作，如替换、重新着色、旋转等，来恢复红黑树的平衡。 在实际编程实现中，...
通过动态演示，学习者能够直观地理解红黑树的操作过程，如节点的插入、删除和旋转等，从而更好地掌握红黑树的工作原理。 总的来说，这篇《红黑树的算法实现与改进》论文是理解红黑树及其优化的宝贵资源，它不仅涵盖...
描述： 实现红黑树、二叉搜索树相关算法：插入（红黑树涉及树的调整：左旋右旋等），删除，搜索（指定Key值节点）。 另外，红黑树实现计算树黑高的算法。 1).插入测试，输入 8，11，17，15，6，1，22，25，27，...