首先我们了解一下红黑树的性质:
在我们编写红黑树添加函数ADDRBT()之前 我们先编写几个工具函数
RBT* GetFather(RBT* pRoot, int id) 获得当前节点的父亲
RBT* GetFather(RBT* pRoot, int id)
{
if (pRoot == NULL)
{
return nullptr;
}
while (pRoot != NULL)
{
if (pRoot->id > id)
{
if (pRoot->pLeft == NULL)
{
return pRoot;
}
pRoot = pRoot->pLeft;
}
else if (pRoot->id < id)
{
if (pRoot->pRight == NULL)
{
return pRoot;
}
pRoot = pRoot->pRight;
}
else
{
break;
}
}
return nullptr;
}
RBT* GetUncle(RBT* pRoot) 获得当前节点的叔叔
RBT* GetUncle(RBT* pRoot)
{
if (pRoot == NULL || pRoot->pFather == NULL || pRoot->pFather->pFather == NULL)
{
return nullptr;
}
else
{
if (pRoot->pFather->pFather->pLeft == pRoot->pFather)
{
return pRoot->pFather->pFather->pRight;
}
else
{
return pRoot->pFather->pFather->pLeft;
}
}
}
void RightRotate(RBT* pRBT,RBT*& pBoot) 右旋当前节点
void RightRotate(RBT* pRBT, RBT*& pBoot)
{
if (pRBT == nullptr || pRBT->pLeft == nullptr)
{
return;
}
//标记不平衡节点 A
RBT* pMark = pRBT;
//标记不平衡节点的左 B
RBT* pTemp = pRBT->pLeft;
//x pMark->pFather E pTemp->pRight
//三个孩子
//不平衡节点的左->不平衡节点的 左的右 A->左=E
pMark->pLeft = pTemp->pRight;
//不平衡节点左的右->不平衡节点 B->右=A
pTemp->pRight = pMark;
//不平衡节点是不是根
//是 不平衡的节点变为根
if (pMark->pFather == nullptr)
{
pBoot = pTemp;
}
//不是 判断不平衡节点是父亲的左还是右 (A是父亲的左还是右)
else
{
//左:
//不平衡节点的父亲的左孩子->不平衡节点 X->左=B
if (pMark->pFather->pLeft == pMark)
{
pMark->pFather->pLeft = pTemp;
}
//右:
//不平衡节点的父亲的右孩子->不平衡节点 X->右=B
else
{
pMark->pFather->pRight = pTemp;
}
}
if (pMark->pLeft != nullptr)
{
pMark->pLeft->pFather = pMark;
}
pTemp->pFather = pMark->pFather;
pMark->pFather = pTemp;
}
void LeftRotate(RBT* pRBT, RBT*& pBoot) 左旋当前节点
void LeftRotate(RBT* pRBT, RBT*& pBoot)
{
if (pRBT == nullptr || pRBT->pRight == nullptr)
{
return;
}
RBT* pMark = pRBT;
RBT* pTemp = pRBT->pRight;
pMark->pRight = pTemp->pLeft;
pTemp->pLeft = pMark;
if (pMark->pFather == nullptr)
{
pBoot = pTemp;
}
else
{
if (pMark->pFather->pLeft == pMark)
{
pMark->pFather->pLeft = pTemp;
}
else
{
pMark->pFather->pRight = pTemp;
}
}
if (pMark->pRight != nullptr)
{
pMark->pRight->pFather = pMark;
}
pTemp->pFather = pMark->pFather;
pMark->pFather = pTemp;
}
然后我们开始定义 void AddRBT(RBT*& rpBoot, int id)函数
思想:
首先 我们把思路列出来 如下列代码注释
void AddRBT(RBT*& rpBoot, int id)
{
RBT* pFather = GetFather(rpBoot, id);
RBT* pMark = new RBT;
pMark->color = RED;
pMark->id = id;
pMark->pFather = pFather;
pMark->pLeft = NULL;
pMark->pRight = NULL;
//判断根是否为空
//空 pMark赋给根
if (rpBoot == NULL)
{
pMark->color = BLACK;
rpBoot = pMark;
return;
}
//非空 添加
if (pFather->id > pMark->id)
{
pFather->pLeft = pMark;
}
else
{
pFather->pRight = pMark;
}
//分析
while (1)
{
//先给pFather和pUncle重新赋值
pFather = pMark->pFather;
//判断父亲的颜色
//黑 直接加
if (pFather->color == BLACK)
{
return;
}
RBT* pUncle = GetUncle(pMark);
//父亲为红 判断叔叔的颜色
//叔叔为红
//父亲和叔叔都变黑
//爷爷变红
//判断爷爷是否为根
//为根 爷爷变黑
//不为根 爷爷赋给标记 结束当前循环 重新对爷爷进行分析
if (pUncle != nullptr && pUncle->color == RED)
{
pFather->color = BLACK;
pUncle->color = BLACK;
pFather->pFather->color = RED;
pMark = pFather->pFather;
if (pMark->pFather == NULL)
{
pMark->color = BLACK;
return;
}
continue;
}
//叔叔为黑 (包含空)
if (pUncle == NULL||pUncle->color==BLACK)
{
//判断父亲是爷爷的左还是右孩子
//左 判断标记是父亲的左还是由节点
//左 爷爷变红 父亲变黑 对爷爷节点右旋 结束
//右 爷爷变红 父亲赋值给标记 对标记左旋
//右 判断标记是父亲的左还是由节点
//右 爷爷变红 父亲变黑 对爷爷节点左旋 结束
//左 爷爷变红 父亲赋值给标记 对标记右旋
if (pFather == pFather->pFather->pLeft)
{
if (pFather->pRight == pMark)
{
pMark = pFather;
LeftRotate(pMark, rpBoot);
}
else
{
pMark->pFather->pFather->color = RED;
pMark->pFather->color = BLACK;
RightRotate(pMark->pFather->pFather, rpBoot);
return;
}
}
//右
if (pFather == pFather->pFather->pRight)
{
if (pFather->pLeft == pMark)
{
pMark = pFather;
RightRotate(pMark, rpBoot);
}
else
{
pMark->pFather->pFather->color = RED;
pMark->pFather->color = BLACK;
LeftRotate(pMark->pFather->pFather, rpBoot);
return;
}
}
}
}
}
delete函数思想:
代码
RBT* GetDeleteNode(RBT* rpBoot, int id)
{
while (rpBoot)
{
if (id > rpBoot->id)
{
rpBoot = rpBoot->pRight;
}
else if (id < rpBoot->id)
{
rpBoot = rpBoot->pLeft;
}
else if(id == rpBoot->id)
{
return rpBoot;
}
}
return NULL;
}
void DeteleRBT(RBT*& rpBoot, int nId)
{
RBT* pDel = GetDeleteNode(rpBoot, nId);
if (pDel == NULL)
{
return;
}
if (pDel->pLeft != NULL && pDel->pRight != NULL)
{
RBT* pMark = pDel;
pDel = pDel->pRight;
while (pDel->pLeft!=NULL)
{
pDel = pDel->pLeft;
}
pMark->id = pDel->id;
}
if (pDel->pFather == NULL)
//根
{
if (pDel->pLeft == NULL && pDel->pRight == NULL)
//判断有没有一个孩子
{
rpBoot = NULL;
//没有孩子
}
else
{
//有孩子
rpBoot = pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight;
rpBoot->color = BLACK;
rpBoot->pFather = NULL;
}
delete pDel;
pDel = NULL;
return;
}
RBT* pFather =pDel->pFather;
//非根
//分析节点颜色
if (pDel->color == RED)
//红 直接删
{
if (pDel == pFather->pLeft)
{
pFather->pLeft = NULL;
}
else
{
pFather->pRight = NULL;
}
delete pDel;
pDel = NULL;
return;
}
//黑 判断节点是否有孩子
if (pDel->pLeft != NULL || pDel->pRight != NULL)
//有孩子 一定是红孩子
{
//红孩子变黑 与爷爷相连
RBT* pChild = pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight;
pChild->color = BLACK;
pChild->pFather = pFather;
if (pFather->pLeft==pDel)
{
pFather->pLeft = pChild;
}
else
{
pFather->pRight = pChild;
}
delete pDel;
pDel = NULL;
return;
}
//没孩子
//先获得兄弟 删除节点
RBT* pBrother = GetBrother(pDel);
if (pFather->pLeft == pDel)
{
pFather->pLeft = NULL;
}
else
{
pFather->pRight = NULL;
}
//分析兄弟颜色 loop
while (1)
{
if (pBrother->color == RED)
//兄弟为红
{
//父亲变红 兄弟变黑 分析兄弟方向
pFather->color = RED;
pBrother->color = BLACK;
if (pFather->pLeft == pBrother)//兄弟为父亲的左
{
//以父亲为支点 右旋
RightRotate(pFather, rpBoot);
pBrother = pFather->pLeft;
}
else //兄弟为父亲的右
{
//以父亲为支点 左旋
LeftRotate(pFather, rpBoot);
pBrother = pFather->pRight;
}
continue;
}
if (pBrother->color == BLACK)
//兄弟为黑
// 分析两个侄子的颜色
{
if ((pBrother->pLeft == NULL && pBrother->pRight == NULL) ||
((pBrother->pLeft != NULL && pBrother->pLeft->color == BLACK) &&
(pBrother->pRight != NULL && pBrother->pRight->color == BLACK)))
{
//两个侄子全黑(包括全为空) 分析父亲颜色
if (pFather->color == RED)
{
//父亲为红 :父亲变黑 兄弟变红 结束
pFather->color = BLACK;
pBrother->color = RED;
return;
}
else
{
//父亲为黑 : 兄弟变红 父亲为新的标记 更换兄弟 标记为根的时候结束 不为根继续分析
pBrother->color = RED;
pDel = pFather;
if (pDel->pFather == NULL)
{
return;
}
continue;
}
}
//左侄子红右侄子黑(空) 分析兄弟方向
if ((pBrother->pLeft != NULL && pBrother->pLeft->color == RED) &&
(pBrother->pRight == NULL || pBrother->pRight->color == BLACK))
{
//兄弟是父亲的右 兄弟变红 左侄子变黑 一兄弟为支点右旋 继续分析
if (pBrother == pFather->pRight)
{
pBrother->color = RED;
pBrother->pLeft->color = BLACK;
RightRotate(pBrother, rpBoot);
pBrother = pFather->pRight;
continue;
}
//兄弟是父亲的左 父亲的颜色给兄弟 父亲变黑 左侄子变黑 以父亲为支点右旋 结束
if (pFather->pLeft == pBrother)
{
pBrother->color = pFather->color;
pFather->color = BLACK;
pBrother->pLeft->color = BLACK;
RightRotate(pFather, rpBoot);
return;
}
}
//右侄子红 分析兄弟方向
if (pBrother->pRight != NULL && pBrother->pRight->color == RED)
//兄弟是父亲的左 兄弟变红 右侄子变黑 以兄弟为支点左旋 继续分析
if (pBrother == pFather->pLeft)
{
pBrother->color = RED;
pBrother->pRight->color = BLACK;
LeftRotate(pBrother, rpBoot);
pBrother = pFather->pLeft;
continue;
}
//兄弟是父亲的右 父亲的颜色给兄弟 父亲变黑 右侄子变黑 以父亲为支点左旋 结束
if (pFather->pRight == pBrother)
{
pBrother->color = pFather->color;
pFather->color = BLACK;
pBrother->pRight->color = BLACK;
LeftRotate(pFather, rpBoot);
return;
}
}
}
}
主函数中我们进行测试:
RBT* Boot = NULL;
int arr[] = { 11,2,14,1,7,15,5 ,8};
for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
{
AddRBT(Boot, arr[i]);
}
inorder(Boot);
cout << "----------" << endl;
AddRBT(Boot, 4);
inorder(Boot);
cout << "----------" << endl;
//DeteleRBT(Boot, 1);
DeteleRBT(Boot,8);
inorder(Boot);
return 0;
这里我们添加了节点4 删除了节点8
执行结果如下:
完整代码如下
#include#include using namespace std; //1.红黑树中所有的节点但不是红的就是黑的 //2. enum COLOR { RED, BLACK }; struct RBT { int id; RBT* pLeft; RBT* pRight; RBT* pFather; COLOR color; }; RBT* GetFather(RBT* pRoot, int id) { if (pRoot == NULL) { return nullptr; } while (pRoot != NULL) { if (pRoot->id > id) { if (pRoot->pLeft == NULL) { return pRoot; } pRoot = pRoot->pLeft; } else if (pRoot->id < id) { if (pRoot->pRight == NULL) { return pRoot; } pRoot = pRoot->pRight; } else { cout << "不允许添加值相同的节点,数据有误" << endl; break; } } return nullptr; } RBT* GetUncle(RBT* pRoot) { if (pRoot == NULL || pRoot->pFather == NULL || pRoot->pFather->pFather == NULL) { return nullptr; } if (pRoot->pFather->pFather->pLeft == pRoot->pFather) { return pRoot->pFather->pFather->pRight; } else { return pRoot->pFather->pFather->pLeft; } } void RightRotate(RBT* pRBT, RBT*& pBoot) { if (pRBT == nullptr || pRBT->pLeft == nullptr) { return; } //标记不平衡节点 A RBT* pMark = pRBT; //标记不平衡节点的左 B RBT* pTemp = pRBT->pLeft; //x pMark->pFather E pTemp->pRight //三个孩子 //不平衡节点的左->不平衡节点的 左的右 A->左=E pMark->pLeft = pTemp->pRight; //不平衡节点左的右->不平衡节点 B->右=A pTemp->pRight = pMark; //不平衡节点是不是根 //是 不平衡的节点变为根 if (pMark->pFather == nullptr) { pBoot = pTemp; } //不是 判断不平衡节点是父亲的左还是右 (A是父亲的左还是右) else { //左: //不平衡节点的父亲的左孩子->不平衡节点 X->左=B if (pMark->pFather->pLeft == pMark) { pMark->pFather->pLeft = pTemp; } //右: //不平衡节点的父亲的右孩子->不平衡节点 X->右=B else { pMark->pFather->pRight = pTemp; } } if (pMark->pLeft != nullptr) { pMark->pLeft->pFather = pMark; } pTemp->pFather = pMark->pFather; pMark->pFather = pTemp; } void LeftRotate(RBT* pRBT, RBT*& pBoot) { if (pRBT == nullptr || pRBT->pRight == nullptr) { return; } RBT* pMark = pRBT; RBT* pTemp = pRBT->pRight; pMark->pRight = pTemp->pLeft; pTemp->pLeft = pMark; if (pMark->pFather == nullptr) { pBoot = pTemp; } else { if (pMark->pFather->pLeft == pMark) { pMark->pFather->pLeft = pTemp; } else { pMark->pFather->pRight = pTemp; } } if (pMark->pRight != nullptr) { pMark->pRight->pFather = pMark; } pTemp->pFather = pMark->pFather; pMark->pFather = pTemp; } void AddRBT(RBT*& rpBoot, int id) { RBT* pFather = GetFather(rpBoot, id); RBT* pMark = new RBT; pMark->color = RED; pMark->id = id; pMark->pFather = pFather; pMark->pLeft = NULL; pMark->pRight = NULL; //判断根是否为空 //空 pMark赋给根 if (rpBoot == NULL) { pMark->color = BLACK; rpBoot = pMark; return; } //非空 添加 if (pFather->id > pMark->id) { pFather->pLeft = pMark; } else { pFather->pRight = pMark; } //分析 while (1) { //先给pFather和pUncle重新赋值 pFather = pMark->pFather; //判断父亲的颜色 //黑 直接加 if (pFather->color == BLACK) { return; } RBT* pUncle = GetUncle(pMark); //父亲为红 判断叔叔的颜色 //叔叔为红 //父亲和叔叔都变黑 //爷爷变红 //判断爷爷是否为根 //为根 爷爷变黑 //不为根 爷爷赋给标记 结束当前循环 重新对爷爷进行分析 if (pUncle != nullptr && pUncle->color == RED) { pFather->color = BLACK; pUncle->color = BLACK; pFather->pFather->color = RED; pMark = pFather->pFather; if (pMark->pFather == NULL) { pMark->color = BLACK; return; } continue; } //叔叔为黑 (包含空) if (pUncle == NULL||pUncle->color==BLACK) { //判断父亲是爷爷的左还是右孩子 //左 判断标记是父亲的左还是由节点 //左 爷爷变红 父亲变黑 对爷爷节点右旋 结束 //右 爷爷变红 父亲赋值给标记 对标记左旋 //右 判断标记是父亲的左还是由节点 //右 爷爷变红 父亲变黑 对爷爷节点左旋 结束 //左 爷爷变红 父亲赋值给标记 对标记右旋 if (pFather == pFather->pFather->pLeft) { if (pFather->pRight == pMark) { pMark = pFather; LeftRotate(pMark, rpBoot); } else { pMark->pFather->pFather->color = RED; pMark->pFather->color = BLACK; RightRotate(pMark->pFather->pFather, rpBoot); return; } } //右 if (pFather == pFather->pFather->pRight) { if (pFather->pLeft == pMark) { pMark = pFather; RightRotate(pMark, rpBoot); } else { pMark->pFather->pFather->color = RED; pMark->pFather->color = BLACK; LeftRotate(pMark->pFather->pFather, rpBoot); return; } } } } } RBT* GetBrother(RBT* rpBoot) { if (rpBoot == NULL || rpBoot->pFather == NULL) { return NULL; } return rpBoot == rpBoot->pFather->pLeft ? rpBoot->pFather->pRight : rpBoot->pFather->pLeft; } RBT* GetDeleteNode(RBT* rpBoot, int id) { while (rpBoot) { if (id > rpBoot->id) { rpBoot = rpBoot->pRight; } else if (id < rpBoot->id) { rpBoot = rpBoot->pLeft; } else if(id == rpBoot->id) { return rpBoot; } } return NULL; } void DeteleRBT(RBT*& rpBoot, int nId) { RBT* pDel = GetDeleteNode(rpBoot, nId); if (pDel == NULL) { return; } if (pDel->pLeft != NULL && pDel->pRight != NULL) { RBT* pMark = pDel; pDel = pDel->pRight; while (pDel->pLeft!=NULL) { pDel = pDel->pLeft; } pMark->id = pDel->id; } if (pDel->pFather == NULL) //根 { if (pDel->pLeft == NULL && pDel->pRight == NULL) //判断有没有一个孩子 { rpBoot = NULL; //没有孩子 } else { //有孩子 rpBoot = pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight; rpBoot->color = BLACK; rpBoot->pFather = NULL; } delete pDel; pDel = NULL; return; } RBT* pFather =pDel->pFather; //非根 //分析节点颜色 if (pDel->color == RED) //红 直接删 { if (pDel == pFather->pLeft) { pFather->pLeft = NULL; } else { pFather->pRight = NULL; } delete pDel; pDel = NULL; return; } //黑 判断节点是否有孩子 if (pDel->pLeft != NULL || pDel->pRight != NULL) //有孩子 一定是红孩子 { //红孩子变黑 与爷爷相连 RBT* pChild = pDel->pLeft != NULL ? pDel->pLeft : pDel->pRight; pChild->color = BLACK; pChild->pFather = pFather; if (pFather->pLeft==pDel) { pFather->pLeft = pChild; } else { pFather->pRight = pChild; } delete pDel; pDel = NULL; return; } //没孩子 //先获得兄弟 删除节点 RBT* pBrother = GetBrother(pDel); if (pFather->pLeft == pDel) { pFather->pLeft = NULL; } else { pFather->pRight = NULL; } //分析兄弟颜色 loop while (1) { if (pBrother->color == RED) //兄弟为红 { //父亲变红 兄弟变黑 分析兄弟方向 pFather->color = RED; pBrother->color = BLACK; if (pFather->pLeft == pBrother)//兄弟为父亲的左 { //以父亲为支点 右旋 RightRotate(pFather, rpBoot); pBrother = pFather->pLeft; } else //兄弟为父亲的右 { //以父亲为支点 左旋 LeftRotate(pFather, rpBoot); pBrother = pFather->pRight; } continue; } if (pBrother->color == BLACK) //兄弟为黑 // 分析两个侄子的颜色 { if ((pBrother->pLeft == NULL && pBrother->pRight == NULL) || ((pBrother->pLeft != NULL && pBrother->pLeft->color == BLACK) && (pBrother->pRight != NULL && pBrother->pRight->color == BLACK))) { //两个侄子全黑(包括全为空) 分析父亲颜色 if (pFather->color == RED) { //父亲为红 :父亲变黑 兄弟变红 结束 pFather->color = BLACK; pBrother->color = RED; return; } else { //父亲为黑 : 兄弟变红 父亲为新的标记 更换兄弟 标记为根的时候结束 不为根继续分析 pBrother->color = RED; pDel = pFather; if (pDel->pFather == NULL) { return; } continue; } } //左侄子红右侄子黑(空) 分析兄弟方向 if ((pBrother->pLeft != NULL && pBrother->pLeft->color == RED) && (pBrother->pRight == NULL || pBrother->pRight->color == BLACK)) { //兄弟是父亲的右 兄弟变红 左侄子变黑 一兄弟为支点右旋 继续分析 if (pBrother == pFather->pRight) { pBrother->color = RED; pBrother->pLeft->color = BLACK; RightRotate(pBrother, rpBoot); pBrother = pFather->pRight; continue; } //兄弟是父亲的左 父亲的颜色给兄弟 父亲变黑 左侄子变黑 以父亲为支点右旋 结束 if (pFather->pLeft == pBrother) { pBrother->color = pFather->color; pFather->color = BLACK; pBrother->pLeft->color = BLACK; RightRotate(pFather, rpBoot); return; } } //右侄子红 分析兄弟方向 if (pBrother->pRight != NULL && pBrother->pRight->color == RED) //兄弟是父亲的左 兄弟变红 右侄子变黑 以兄弟为支点左旋 继续分析 if (pBrother == pFather->pLeft) { pBrother->color = RED; pBrother->pRight->color = BLACK; LeftRotate(pBrother, rpBoot); pBrother = pFather->pLeft; continue; } //兄弟是父亲的右 父亲的颜色给兄弟 父亲变黑 右侄子变黑 以父亲为支点左旋 结束 if (pFather->pRight == pBrother) { pBrother->color = pFather->color; pFather->color = BLACK; pBrother->pRight->color = BLACK; LeftRotate(pFather, rpBoot); return; } } } } ostream& operator <<(ostream& os, COLOR color) { if (color == RED) { os << "红"; } if (color == BLACK) { os << "黑"; } return os; } void inorder(RBT*& Boot) { if (Boot == NULL) { return; } inorder(Boot->pLeft); cout << Boot->id << " " << Boot->color << endl; inorder(Boot->pRight); } int main() { RBT* Boot = NULL; int arr[] = { 11,2,14,1,7,15,5 ,8}; for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) { AddRBT(Boot, arr[i]); } inorder(Boot); cout << "----------" << endl; AddRBT(Boot, 4); inorder(Boot); cout << "----------" << endl; //存疑 : // Add节点4 之后 8的节点的父亲应该是11 代码中的8 的父亲是7 未能找到原因 ?? // 解决这个问题 代码就差不多没问题了 //DeteleRBT(Boot, 1); DeteleRBT(Boot,7); inorder(Boot); return 0; }
