关于红黑树的删除方式,网络上是众说纷纭,自己总结整理了一下,关于红黑树的性质不再重述,直接上代码,请查看删除部分的注释(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 : 兄弟节点为黑色,但是,兄弟节点的子节点存在为红色的情况,该种情况下,可通过旋转的方式解决R蛭婊唤诘闶亲蠼诘悖韵氩捎米笮姆绞嚼创恚矗? // 判断红色子节点是不是兄弟节点的右子节点,如果是则直接处理,否则,要先将其旋转到右侧,所以
// 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
相关推荐
实验1:实现红黑树的基本算法, 对n的取值分别为 12、24、36、48、60,随机生成n 个互异的正整数(K1, K2, K3, ……, Kn)作为节点的关键字,向一棵初始空的红黑树中依次插入这n 个节点,统计算法运行所需时间 ,画...
描述: 实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋右旋等),删除,搜索(指定Key值节点)。 另外,红黑树实现计算树黑高的算法。 1).插入测试,输入 8,11,17,15,6,1,22,25,27,...
通常使用一个结构体来表示红黑树节点,包含数据值、颜色(红/黑)、父节点指针以及左右子节点指针。 3. 插入操作 插入新节点时,需要先将其着色为红色,然后通过旋转和重新着色操作来修复可能违反的红黑树性质。这个...
红黑树的链接实现,完成增加,删除结点,寻找前缀后缀节点等。
描述: 实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋、右旋等),删除,搜索(指定Key值节点)。 另外,红黑树实现计算树黑高的算法。 1).插入测试,输入 8,11,17,15,6,1,22,25,27...
问题描述: 实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋、右旋等),删除,搜索(指定Key值节点)。 另外,红黑树实现计算树黑高的算法。 实验要求: 1).插入测试,输入 8,11,17,15,6,...
详细的红黑树C++模板实现,调试后运行正确。 template class RBTree { private: static node<T> *nil;//哨兵,静态成员,被整个RBTree类所共有 node<T> *root; RBTree(const RBTree&);//禁止复制构造 RBTree ...
通过Java实现红黑树,包括红黑树的插入操作、删除操作、维护红黑树性质的操作以及常用的方法函数(打印、清空、搜索、旋转等操作) 同时通过调用JFrame框架实现了对红黑树的可视化,包括插入的可视化、删除的可视化...
实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋、右旋等),删除,搜索(指定Key值节点)。 另外,红黑树实现计算树黑高的算法。
根据算法导论中红黑树的讲解,用C写了一个关于红黑树的建立,查询节点,插入,删除操作
资源包括红黑树源码(VC2008动态库形式)、调用示例源码、用户开发文档。实现以下强大功能: 1、 支持自定义键值比较函数 2、 支持删除节点回调函数 3、 支持插入节点 4、 支持根据键值进行精确查询节点 5、 支持...
Java写的红黑树,按照《算法导论》上的算法写的,包括建树、删除节点、插入节点、计算黑高、打印等,只包括源码,需要自己建工程
描述: 实现红黑树、二叉搜索树相关算法:插入(红黑树涉及树的调整:左旋、右旋等),删除,搜索(指定Key值节点)。 另外,红黑树实现计算树黑高的算法。 1).插入测试,输入 8,11,17,15,6,1,22,25,27...
程序完美运行!!! 实现功能: 1.建立一个100个节点的红黑树 2.删除节点 3.前序遍历输出红黑树 4.中序遍历输出红黑树 5.查找节点
红黑树是一种自平衡的二叉查找树,是一种高效的查找树。它是由 Rudolf Bayer 于1978年发明,在当时被称为平衡二叉 B 树(symmetric binary B-trees)。...C语言实现红黑树的创建,包括节点的插入删除操作以及红黑树输出
红黑树的建立,插入节点,删除节点
资源包括红黑树源码(VC2008动态库形式)、调用示例源码、用户开发文档。实现以下强大功能: 1、 支持自定义键值比较函数 2、 支持删除节点回调函数 3、 支持插入节点 4、 支持根据键值进行精确查询节点 5、 支持...
红黑树的节点插入和删除的程序,执行过,较好实现。
RedBlack树的Matlab使用面向对象的编程方法实现。 实现以下方法: 树的构造函数添加新节点从树中删除节点画树在树中找到最小条目在树中找到最大条目在树中搜索条目 k。
因为看内核的时候感觉红黑树挺有意思的,所以利用周末的时间来实现一下玩玩。红黑树的操作主要是插入和删除,而删除的时候需要考虑的情况更多一些。具体的操作就不在这里罗嗦了,百度文库里面有一个比较有好的文章,...