红黑树及其C语言实现
红黑树及其性质
红黑树是一棵二叉搜索树,它在每个节点上存储了一位来表示结点的颜色,然后通过每个结点到叶子结点的颜色数目来约束以达到自平衡。它必须满足以下性质:
- 每个结点要不是红色,要不是黑色。
- 根结点是黑色。
- 叶子结点是黑色。(这里的叶子结点指的是T.Nil)
- 如果一个结点是红色的,那么它的子结点必须是黑色的。
- 从树中的任一结点到所有叶子结点的简单路径上,均包含同样数目的黑色结点。(即其黑高相同)
红黑树的操作
红黑树数据结构定义:
//红黑树结点颜色定义
typedef enum rb_tree_color
{
RB_TREE_COLOR_BLACK = 0, //黑色
RB_TREE_COLOR_RED = 1, //红色
}eRbTreeColor;
//红黑结结构定义
typedef struct rb_tree_node
{
struct rb_tree_node* parent; //父结点
struct rb_tree_node* left; //左结点
struct rb_tree_node* right; //右结点
eRbTreeColor nodeColor; //结点颜色
int data; //数据
}stRbTreeNode;
红黑树的操作有查询,添加和删除。当从红黑树添加或删除结点时,会破坏红黑树的性质。这时需要用到红黑树的旋转操作,以保持红黑树的平衡。
红黑树的旋转
红黑树的左旋就是把红黑树的结点变为其右结点的左子树,右旋就是将结点变为其左结点的右子树。
代码实现:
//左旋
static void rbTreeLeftRotate(stRbTreeNode** root, stRbTreeNode* node)
{
stRbTreeNode* rNode = node->right;
node->right = rNode->left;
if (rNode->left != NULL)
rNode->left->parent = node;
rNode->parent = node->parent;
//父结点为空代表 node 结点为根结点
if (node->parent == NULL)
*root = rNode;
else if (node->parent->left == node)
node->parent->left = rNode;
else
node->parent->right = rNode;
rNode->left = node;
node->parent = rNode;
}
//右旋
static void rbTreeRightRotate(stRbTreeNode** root, stRbTreeNode* node)
{
stRbTreeNode* rNode = node->left;
node->left = rNode->right;
if (rNode->right != NULL)
rNode->right->parent = node;
rNode->parent = node->parent;
//父结点为空代表 node 结点为根结点
if (node->parent == NULL)
*root = rNode;
else if (node->parent->left == node)
node->parent->left = rNode;
else
node->parent->right = rNode;
rNode->right = node;
node->parent = rNode;
}
红黑树查找
因为红黑树是一棵二叉搜索树,因此可以利用二叉搜索树的性质,如果要查找的值小于当前结点的值,则查找当前结点的左子树,如果大于,则查找右子树,直到与结点值相等或找到叶子结点。
代码实现:
//查找
stRbTreeNode* rbTreeSearch(stRbTreeNode* root, int data)
{
stRbTreeNode* node = root;
while (node != NULL)
{
if (data < node->data)
node = node->left;
else if (data > node->data)
node = node->right;
else
break;
}
return node;
}
红黑树添加结点
红黑树添加结点可以分为三步:
- 查找结点的插入位置。
根据二叉搜索树的性质,可以很容易的找到要插入结点的位置,即找到其父结点。 - 将结点着为红色并插入相应位置。
这里把结点着为红色,不会影响其黑高,即红黑树性质 5,这样当其父节点为黑色时,不需要进行调整即可完成插入。 - 通过旋转和着色等操作,使其满足红黑树的性质。
当插入结点的父结点为黑色时,红黑树的性质并没有被破坏,因此不需要进行调整。当插入结点的父结点是红色时,红黑树性质 4 被破坏了,这时就需要调整红黑树。
插入结点代码实现:
//插入
int rbTreeInsert(stRbTreeNode** root, stRbTreeNode* node)
{
stRbTreeNode* parent = NULL;
//查找结点插入位置
stRbTreeNode* next = *root;
while (next != NULL)
{
parent = next;
if (node->data < next->data)
next = next->left;
else if (node->data > next->data)
next = next->right;
else
return 1;
}
if (parent == NULL)
{
//parent为NULL代表红黑树为空,要插入的结点即为根结点
node->nodeColor = RB_TREE_COLOR_BLACK;
node->parent = NULL;
node->left = NULL;
node->right = NULL;
*root = node;
return 0;
}
//将结点着为红色并插入到红黑树中
node->left = NULL;
node->right = NULL;
node->parent = parent;
if (parent->data > node->data)
parent->left = node;
else
parent->right = node;
node->nodeColor = RB_TREE_COLOR_RED;
//调整红黑树,使其满足红黑树性质
if (parent->nodeColor == RB_TREE_COLOR_RED)
rbTreeInsertFixUp(root, node);
return 0;
}
当插入结点父结点为红色时,这时违反了红黑树的性质 4,出现了两个连续的红色结点,此时需要对红黑树进行调整,调整方法分为三种情况:
1). 当插入结点的叔叔结点为红色时,因为根据红黑树的性质可知,插入结点的爷爷结点,即父结点的父结点肯定是黑色,这时需要将爷爷结点的颜色下移,即将其父结点和叔叔结点着为黑色,将爷爷结点着为红色,这样整棵树的黑高未改变,将爷爷结点当做新插入结点,再判断是否违反了红黑树的性质 4,从爷爷结点开始调整。如下图:
调整后:
2). 当插入结点的叔叔结点为黑色时,这时不可以同步骤 1) 一样将颜色下移,因为下移后会改变红黑树的黑高。此时可以判断插入结点是父结点的左结点还是右结点。如果同父结点的左右位置不相同(即父结点是爷爷结点的左结点,插入结点是父结点的右结点,或父结点是爷爷结点的右结点,插入结点是父结点的左结点),此时可以通过对父结点进行左旋/右旋,使两个结点左右位置相同。然后将插入结点指向旋转后的子结点,将其当做插入结点进行操作。如下图:
图中 x 是其父结点的右结点,x.p 是其父结点的左结点,则可以将 x.p 进行左旋,然后将左旋前的父结点当做插入结点。调整后:
3). 当插入结点的叔叔结点为黑色且插入结点同父结点的位置相同时(即父结点是爷爷结点的左结点,插入结点是父结点的左结点,或父结点是爷爷结点的右结点,插入结点是父结点的右结点),根据红黑树的性质,其爷爷结点必定是黑色,可以将其爷爷结点的颜色传递给其父结点,然后对其爷爷结点进行右旋/左旋,这样必定可以使原红黑树达到平衡。如下图:
图中 x 是其父结点的左结点,x.p 也是其父结点的左结点,则可以将其父结点着为黑色,将其爷爷结点着为红色,然后将 x.p.p 进行右旋,使树达到平衡:
插入结点后调整方法代码实现:
//插入结点后调整树
static void rbTreeInsertFixUp(stRbTreeNode** root, stRbTreeNode* node)
{
while (node->parent != NULL && node->parent->nodeColor == RB_TREE_COLOR_RED)
{
stRbTreeNode* parent = node->parent;
if (parent == parent->parent->left)
{
stRbTreeNode* uncle = parent->parent->right;
//情况 1
if (uncle != NULL && uncle->nodeColor == RB_TREE_COLOR_RED)
{
parent->nodeColor = RB_TREE_COLOR_BLACK;
uncle->nodeColor = RB_TREE_COLOR_BLACK;
parent->parent->nodeColor = RB_TREE_COLOR_RED;
node = parent->parent;
}
//情况 2
else if (node == parent->right)
{
node = parent;
rbTreeLeftRotate(root, node);
}
//情况 3
else
{
parent->parent->nodeColor = RB_TREE_COLOR_RED;
parent->nodeColor = RB_TREE_COLOR_BLACK;
rbTreeRightRotate(root, parent->parent);
}
}
else
{
stRbTreeNode* uncle = parent->parent->left;
//情况 1
if (uncle->nodeColor == RB_TREE_COLOR_RED)
{
parent->nodeColor = RB_TREE_COLOR_BLACK;
uncle->nodeColor = RB_TREE_COLOR_BLACK;
parent->parent->nodeColor = RB_TREE_COLOR_RED;
node = parent->parent;
}
//情况 2
else if (node == parent->left)
{
node = parent;
rbTreeRightRotate(root, node);
}
//情况 3
else
{
parent->parent->nodeColor = RB_TREE_COLOR_RED;
parent->nodeColor = RB_TREE_COLOR_BLACK;
rbTreeLeftRotate(root, parent->parent);
}
}
}
(*root)->nodeColor = RB_TREE_COLOR_BLACK;
}
红黑树删除结点
红黑树删除结点也需要三个步骤:
- 查找到需要删除的结点。
- 删除该结点。
删除结点需要注意,为了不使树断掉,需要找到能代替删除结点的结点。如果要删除的结点只有一个子结点,则直接用该结点代替要删除的结点。如果要删除的结点有两个结点,则需要找到该结点的后继,将其代替该结点(继承该结点的颜色和位置)。(当然使用该结点的前驱也可以,这里使用后继) - 对删除结点后的树进行调整,使其保持红黑树性质。
如果删除的结点是红色的,则红黑树仍然保持其性质,此时不需要调整。但是如果删除的结点是黑色的,那么红黑树的性质 5 肯定是不满足了,此时需要对红黑树进行调整。这里需要注意的是,如果删除结点的替代结点是其后继/前驱,则相当于删除了其后继/前驱结点,此时删除结点的颜色应该是其后继/前驱结点的颜色。
删除结点代码实现:
//红黑树结点后继
static stRbTreeNode* rbTreeSuccessor(stRbTreeNode* node)
{
stRbTreeNode* suc = node->right;
while (suc->left != NULL)
suc = suc->left;
return suc;
}
//以now结点代替ori
static void rbTreeTransplant(stRbTreeNode** root, stRbTreeNode* ori, stRbTreeNode* now)
{
if (ori->parent == NULL)
*root = now;
else if (ori->parent->left == ori)
ori->parent->left = now;
else
ori->parent->right = now;
if (now != NULL)
now->parent = ori->parent;
}
//删除
stRbTreeNode* rbTreeDelete(stRbTreeNode** root, int data)
{
//查找要删除的结点
stRbTreeNode* node = *root;
while (node != NULL)
{
if (node->data == data)
break;
else if (node->data > data)
node = node->left;
else
node = node->right;
}
if (node == NULL)
return NULL;
//删除结点,如果结点只有一个子结点,则直接替代该结点,
eRbTreeColor oriColor = node->nodeColor;
stRbTreeNode* adjNode = node;
stRbTreeNode* parentNode = node->parent;
if (node->left == NULL)
{
adjNode = node->right;
rbTreeTransplant(root, node, node->right);
}
else if (node->right == NULL)
{
adjNode = node->left;
rbTreeTransplant(root, node, node->left);
}
else
{
stRbTreeNode* suc = rbTreeSuccessor(node);
oriColor = suc->nodeColor;
parentNode = suc->parent;
if (suc->parent == node)
parentNode = node->parent;
stRbTreeNode* sucRight = suc->right;
rbTreeTransplant(root, suc, sucRight);
rbTreeTransplant(root, node, suc);
suc->left = node->left;
suc->right = node->right;
suc->nodeColor = node->nodeColor;
if (node->left != NULL)
node->left->parent = suc;
if (node->right != NULL)
node->right->parent = suc;
adjNode = sucRight;
}
if (oriColor == RB_TREE_COLOR_BLACK)
rbTreeDeleteFixUp(root, adjNode, parentNode);
return node;
}
如果删除的结点是黑色,则肯定会破坏红黑树的性质 5,其删除结点路径的黑高会产生变化,此时需要对红黑树进行调整,使其满足红黑树性质。以删除结点为其父结点的左结点为例,将调整分为以下几种情况(删除结点为其父结点的右结点时与此情况操作正好相反,左右结点相反,左旋改为右旋等):
1). 当其兄弟结点颜色为红色时,其父结点肯定为黑色,此时对其父结点进行左旋,旋转后的父结点的右结点变为其兄弟结点,再进行之后的操作。如图:
2). 当其兄弟结点颜色为黑色,且其兄弟结点的左右两个结点也都为黑色时,将其兄弟结点着色为红色,将当前结点指向其父结点,再进行之后的操作。如图:
3). 当其兄弟结点颜色为黑色,兄弟结点的右结点为黑色且兄弟结点的左结点为红色时,可以将其兄弟结点的左结点着色为黑色,将其兄弟结点着色为红色,然后把兄弟结点进行右旋。右旋后就会转换成情况 4。如图:
4). 当其兄弟结点颜色为黑色,且兄弟结点的右结点为红色时。可以将兄弟结点着色为父结点的颜色,父结点着色为黑色,兄弟结点的右结点着色为黑色,然后对父结点进行左旋。左旋后的红黑树即满足性质 5。如图:
其实,删除结点后调整红黑树的基本思想就是向其兄弟树借结点,为满足红黑树的性质,兄弟树上的黑色结点肯定是不能借的,只能借红色结点。所以会判断其兄弟结点或其兄弟结点的子结点是否有红色结点。当出现情况 4 时,只需要调整一次即可使红黑树达到平衡的效果。情况 3 可以通过一次旋转转换为情况 4。当都没有红色结点时,为保持其黑高,将其兄弟结点着色为红色,此时相当于删除了其父结点,将当前结点置为其父结点,再向上继续调整(情况 2 )。
删除结点调整代码实现:
//红黑树删除结点后调整
static void rbTreeDeleteFixUp(stRbTreeNode** root, stRbTreeNode* node, stRbTreeNode* parent)
{
while (node != *root && (node == NULL || node->nodeColor == RB_TREE_COLOR_BLACK))
{
if (parent->left == node)
{
stRbTreeNode* brother = parent->right;
//情况 1
if (brother->nodeColor == RB_TREE_COLOR_RED)
{
parent->nodeColor = RB_TREE_COLOR_RED;
brother->nodeColor = RB_TREE_COLOR_BLACK;
rbTreeLeftRotate(root, parent);
brother = parent->right;
}
//情况 2
if ((brother->left == NULL ||
brother->left->nodeColor == RB_TREE_COLOR_BLACK) &&
(brother->right == NULL ||
brother->right->nodeColor == RB_TREE_COLOR_BLACK))
{
brother->nodeColor = RB_TREE_COLOR_RED;
node = parent;
parent = node->parent;
}
else
{
//情况 3
if (brother->right != NULL &&
brother->right->nodeColor == RB_TREE_COLOR_RED)
{
brother->nodeColor = parent->nodeColor;
brother->right->nodeColor = RB_TREE_COLOR_BLACK;
parent->nodeColor = RB_TREE_COLOR_BLACK;
rbTreeLeftRotate(root, parent);
node = *root;
}
//情况 4
else
{
brother->nodeColor = RB_TREE_COLOR_RED;
brother->left->nodeColor = RB_TREE_COLOR_BLACK;
rbTreeRightRotate(root, brother);
brother = parent->right;
}
}
}
else
{
stRbTreeNode* brother = parent->left;
//情况 1
if (brother->nodeColor == RB_TREE_COLOR_RED)
{
parent->nodeColor = RB_TREE_COLOR_RED;
brother->nodeColor = RB_TREE_COLOR_BLACK;
rbTreeRightRotate(root, parent);
brother = parent->left;
}
//情况 2
if ((brother->left == NULL ||
brother->left->nodeColor == RB_TREE_COLOR_BLACK) &&
(brother->right == NULL ||
brother->right->nodeColor == RB_TREE_COLOR_BLACK))
{
brother->nodeColor = RB_TREE_COLOR_RED;
node = parent;
parent = node->parent;
}
else
{
//情况 3
if (brother->left != NULL &&
brother->left->nodeColor == RB_TREE_COLOR_RED)
{
brother->nodeColor = parent->nodeColor;
brother->left->nodeColor = RB_TREE_COLOR_BLACK;
parent->nodeColor = RB_TREE_COLOR_BLACK;
rbTreeRightRotate(root, parent);
node = *root;
}
//情况 4
else
{
brother->nodeColor = RB_TREE_COLOR_RED;
brother->right->nodeColor = RB_TREE_COLOR_BLACK;
rbTreeLeftRotate(root, brother);
brother = parent->left;
}
}
}
}
if (node != NULL)
node->nodeColor = RB_TREE_COLOR_BLACK;
}
参考:
<算法导论> 第三版中文版 P13 算法导论>- 版权声明: