轉眼就快畢業了，既然準備找工作聽說最好發點帖子，那麼第一篇就拿數據結構開刀吧！
當初自己想寫紅黑樹時候參考了網上的代碼，最後發現還是<中的偽代碼最好懂，所以代碼完全按照<>偽代碼來編寫，方便對照<>來學習紅黑樹。
寫紅黑樹的文章很多，這篇文章和其他寫紅黑樹的區別：
1. 完全按照<>中偽代碼邏輯編寫，網上很多代碼都經歷過優化或者加工，對照<>的偽代碼看著很難受。
2. 後面提供插入和刪除調整樹的圖，對著代碼單步調試更好理解。
直接上代碼
RBTree.h
#pragma once
//紅黑樹
class RBTree
{
private:
typedef enum
{
E_TREE_BLACK,
E_TREE_RED,
E_TREE_COLOR_MAX
}ETreeColor;
const static char *s_pszColor[E_TREE_COLOR_MAX];
typedef struct __TreeNode
{
__TreeNode* pParent;
__TreeNode* pLeft;
__TreeNode* pRight;
ETreeColor eColor;
int nValue;
}TreeNode, *PTreeNode;
public:
RBTree();
~RBTree();
//插入數據
void InsertData(int nValue); //插入數據
bool Empty(); //判空
bool GetMax(PTreeNode pNode, int &nMax); // 獲取最大值
bool GetMin(PTreeNode pNode, int &nMin); //獲取最小值
void DeleteElement(int nDelete); //刪除指定的元素
bool FindElement(int nFindValue); //查找數據,如果查找到返回true，否則返回false
void BreadthEnum(); //廣度遍歷
private:
void InsertFixUp(PTreeNode pInsertNode); //插入pInsertNode點後調整紅黑樹
void DeleteFixUp(PTreeNode pFixNode); //刪除後重新調整
void SingleL(PTreeNode &pNode, PTreeNode &newTop); //左旋轉,並且返回新的頂點
void SingleR(PTreeNode &pNode, PTreeNode &newTop); //右旋轉
void ReplaceParent(PTreeNode pBeReplacedNode, PTreeNode pReplaceNode); //把pReplaceNode的父節點修改為pBeReplacedNode的
bool GetMinNode(PTreeNode pNode, PTreeNode &pMinNode);//獲取最小的節點
private:
PTreeNode m_pRoot; //根節點指針
PTreeNode m_pNil; //空節點
};
RBTree.cpp
#include "RBTree.h"
#include
#include
#include
const char * RBTree::s_pszColor[E_TREE_COLOR_MAX] = {"黑", "紅"};
RBTree::RBTree()
{
m_pRoot = nullptr;
//
m_pNil = new TreeNode();
m_pNil->pLeft = nullptr;
m_pNil->pRight = nullptr;
m_pNil->pParent = nullptr;
m_pNil->eColor = E_TREE_BLACK;
m_pNil->nValue = 0xFFFFFFFF;
}
RBTree::~RBTree()
{
if (!Empty())
{
std::queue nodeQue;
nodeQue.push(m_pRoot);
//廣度遍歷
while (!nodeQue.empty())
{
PTreeNode pNode = nodeQue.front();
PTreeNode pLeft = pNode->pLeft;
PTreeNode pRight = pNode->pRight;
//出隊列釋放資源
nodeQue.pop();
delete pNode;
if (pLeft != m_pNil) nodeQue.push(pLeft);
if (pRight != m_pNil) nodeQue.push(pRight);
}
}
if (m_pNil)
{
delete m_pNil;
m_pNil = nullptr;
}
}
void RBTree::InsertData(int nValue)
{
//1.如果是第一個節點
if (Empty())
{
m_pRoot = new TreeNode();
m_pRoot->eColor = E_TREE_BLACK;
m_pRoot->nValue = nValue;
m_pRoot->pLeft = m_pNil;
m_pRoot->pRight = m_pNil;
m_pRoot->pParent = m_pNil;
return;
}
//2. 找到需要插入的位置pPreNode
PTreeNode pPreNode = m_pRoot->pParent;
PTreeNode pCurrent = m_pRoot;
while (m_pNil != pCurrent)
{
pPreNode = pCurrent;
if (nValue <= pCurrent->nValue)
{
pCurrent = pCurrent->pLeft;
}
else
{
pCurrent = pCurrent->pRight;
}
}
//3. 把數據插入到正確的位置
PTreeNode pInsertNode = new TreeNode();
pInsertNode->eColor = E_TREE_RED;
pInsertNode->nValue = nValue;
pInsertNode->pLeft = m_pNil;
pInsertNode->pRight = m_pNil;
pInsertNode->pParent = pPreNode;
//
if (nValue <= pPreNode->nValue)
{
pPreNode->pLeft = pInsertNode;
}
else
{
pPreNode->pRight = pInsertNode;
}
//4. 從插入點開始調整紅黑樹
InsertFixUp(pInsertNode);
}
bool RBTree::Empty()
{
return nullptr == m_pRoot;
}
bool RBTree::GetMax(PTreeNode pNode, int &nMax)
{
if (nullptr == pNode)
{
return false;
}
while (pNode)
{
nMax = pNode->nValue;
pNode = pNode->pRight;
}
return true;
}
bool RBTree::GetMin(PTreeNode pNode, int &nMin)
{
if (nullptr == pNode)
{
return false;
}
while (pNode)
{
nMin = pNode->nValue;
pNode = pNode->pLeft;
}
return true;
}
void RBTree::DeleteElement(int nDelete)
{
if (Empty())
return;
//1.先找到位置
PTreeNode pCurrent = m_pRoot;
PTreeNode pNeedDelNode = nullptr;
while (m_pNil != pCurrent)
{
if (nDelete < pCurrent->nValue)
{
pCurrent = pCurrent->pLeft;
}
else if (nDelete > pCurrent->nValue)
{
pCurrent = pCurrent->pRight;
}
else
{
pNeedDelNode = pCurrent;
break;
}
}
//2. 如果未找到直接退出
if (nullptr == pNeedDelNode) return;
//3.執行刪除,計算出pNeedDeleteNode，pRealDeleteNode，pFixUpNode
/*
上面傳入刪除點記著：pNeedDeleteNode
實際刪除點記著：pRealDeleteNode
調整點位pRealDeleteNode的後繼記著:pFixUpNode
*/
PTreeNode pRealDeleteNode = nullptr;
PTreeNode pFixUpNode = nullptr;
ETreeColor eRealDeleteColor = E_TREE_COLOR_MAX;
//3.1 如果左子樹為空
if (m_pNil == pNeedDelNode->pLeft)
{
pRealDeleteNode = pNeedDelNode;
eRealDeleteColor = pRealDeleteNode->eColor;
pFixUpNode = pRealDeleteNode->pRight;
//
ReplaceParent(pRealDeleteNode, pRealDeleteNode->pRight);
}
//3.2 如果右子樹為空
else if (m_pNil == pNeedDelNode->pRight)
{
pRealDeleteNode = pNeedDelNode;
eRealDeleteColor = pRealDeleteNode->eColor;
pFixUpNode = pRealDeleteNode->pLeft;
//
ReplaceParent(pRealDeleteNode, pRealDeleteNode->pLeft);
}
//3.3 如果左右子樹都不為空
else
{
//獲取準備刪除點的右子樹最小節點，pRealDeleteNode一定不是m_nil
bool bGetMinRet = GetMinNode(pNeedDelNode->pRight, pRealDeleteNode);
assert(bGetMinRet);
assert(pRealDeleteNode != m_pNil);
eRealDeleteColor = pRealDeleteNode->eColor;
//最小點左子樹一定為m_nil,所以pRight是它的後繼
pFixUpNode = pRealDeleteNode->pRight;
//主要是用最小點（pRealDeleteNode）來替換需要刪除點（pNeedDelNode）的位置，分兩種情況
if (pRealDeleteNode->pParent == pNeedDelNode)
{
//情況一：
/*
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
pNeedDelNode
/ \
/ \
nodex pRealDeleteNode
/ \
/ \
nil 這個節點一定是紅色節點或者空節點（X）(根據紅黑樹性質5)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
如果是紅色節點：在調整的時候直接變黑
如果是空節點：X就是調整的開始點
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
最關鍵的問題是：為什麼使用X點作為調整點而不是直接使用pRealDeleteNode作為調整點?
1. X點和pRealDeleteNode都可以作為調整點
2. 這裡選pRealDeleteNode可能更好理解，但是選擇X作為調整點有一個好處和情況2統一的處理方式
*/
//因為pFixUpNode可能為m_pNil，m_Nil公用的所以需要調整下
pFixUpNode->pParent = pRealDeleteNode;
}
else
{
//情況二：
/*
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
pNeedDelNode
/ \
/ \
nodex node1
/ \
/ \
pRealDeleteNode node2
/ \
/ \
m_nil 這個節點一定是紅色節點或者空節點（X）(根據紅黑樹性質5)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
*/
//讓pRealDeleteNode父節點指向 pRealDeleteNode->pRight
ReplaceParent(pRealDeleteNode, pRealDeleteNode->pRight);
//讓pRealDeleteNode的右節點接管原來pNeedDelNode的右節點
pRealDeleteNode->pRight = pNeedDelNode->pRight;
//讓pRealDeleteNode的右節點的父節點指向pRealDeleteNode(右子樹一定不為m_pNil)
pRealDeleteNode->pRight->pParent = pRealDeleteNode;
}
//讓pNeedDelNode父節點指向pRealDeleteNode
ReplaceParent(pNeedDelNode, pRealDeleteNode);
//讓pRealDeleteNode的左節點接管原來pNeedDelNode的右節點
pRealDeleteNode->pLeft = pNeedDelNode->pLeft;
//讓pRealDeleteNode的左節點的父節點指向pRealDeleteNode(左子樹一定部位m_pNil)
pRealDeleteNode->pLeft->pParent = pRealDeleteNode;
// 使用pNeedDelNode的顏色
pRealDeleteNode->eColor = pNeedDelNode->eColor;
}
//4. 在pFixUpNode點執行調整
if (E_TREE_BLACK == eRealDeleteColor)
{
DeleteFixUp(pFixUpNode);
}
//5. 處理根節點問題
if (m_pRoot == m_pNil) m_pRoot = nullptr;
//6. 清理掉刪除的節點
delete pNeedDelNode;
}
bool RBTree::FindElement(int nFindValue)
{
if (Empty())
return false;
PTreeNode pCurrent = m_pRoot;
while (m_pNil != pCurrent)
{
if (nFindValue < pCurrent->nValue)
{
pCurrent = pCurrent->pLeft;
}
else if (nFindValue > pCurrent->nValue)
{
pCurrent = pCurrent->pRight;
}
else
{
return true;
}
}
return false;
}
void RBTree::BreadthEnum()
{
if (Empty()) return;
std::queue nodeQue;
nodeQue.push(m_pRoot);
//廣度遍歷
int nHeight = 0;
while (!nodeQue.empty())
{
int nCurrentLevelSize = nodeQue.size(); // 記錄當前層元素個數
int nCnt = 0;
std::cout << "第" << nHeight + 1 << "層:";
while (nCnt < nCurrentLevelSize)
{
PTreeNode acessNode = nodeQue.front();
nodeQue.pop();
if (acessNode == m_pRoot)
{
std::cout << acessNode->nValue << "(根節點，顏色:" << s_pszColor[acessNode->eColor] << ")" << " ";
}
else
{
if (acessNode->pParent->pLeft == acessNode)
{
std::cout << "[(" << acessNode->nValue << "顏色:" << s_pszColor[acessNode->eColor] << ")"
<< "(" << acessNode->pParent->nValue << "的左孩子)]"<< " ";
}
else if (acessNode->pParent->pRight == acessNode)
{
std::cout << "[(" << acessNode->nValue << "顏色:" << s_pszColor[acessNode->eColor] << ")"
<< "(" << acessNode->pParent->nValue << "的右孩子)]" << " ";
}
}
//把下一層的元素放進來
PTreeNode pLeft = acessNode->pLeft;
PTreeNode pRight = acessNode->pRight;
if (pLeft !=m_pNil)
{
nodeQue.push(pLeft);
}
if (pRight != m_pNil)
{
nodeQue.push(pRight);
}
++nCnt;
}
nHeight++;
std::cout << std::endl;
}
std::cout << std::endl;
}
void RBTree::InsertFixUp(PTreeNode pInsertNode)
{
PTreeNode pFixNode = pInsertNode;
//如果父親是紅節點(根節點的父親節點為nil，一定為黑)
while (E_TREE_RED == pFixNode->pParent->eColor)
{
//1. 如果調整節點的父親為祖父節點的左孩子
if (pFixNode->pParent == pFixNode->pParent->pParent->pLeft)
{
//獲取叔叔節點(祖父節點的右孩子)
PTreeNode pUncle = pFixNode->pParent->pParent->pRight;
//1.1.如果叔叔節點為紅色
if (E_TREE_RED == pUncle->eColor)
{
//把父親節點和叔叔節點都改為黑色
pFixNode->pParent->eColor = E_TREE_BLACK;
pUncle->eColor = E_TREE_BLACK;
//把祖父節點改為紅色
pFixNode->pParent->pParent->eColor = E_TREE_RED;
//重新計算調整節點為祖父節點
pFixNode = pFixNode->pParent->pParent;
}
//1.2. 叔叔節點不為紅色，且調整節點為父節點的右孩子,處理後會轉化為1.3
else if (pFixNode == pFixNode->pParent->pRight)
{
//從調整節點的父節點開始旋轉
pFixNode = pFixNode->pParent;
//記錄下新的頂點
PTreeNode pNewTop = nullptr;
SingleL(pFixNode->pParent->pLeft, pNewTop);
//重新設置調整節點
pFixNode = pNewTop->pLeft;
}
//1.3. 叔叔節點不為紅色，且調整節點為父節點的左孩子
else if (pFixNode == pFixNode->pParent->pLeft)
{
//把父親節點變為黑色
pFixNode->pParent->eColor = E_TREE_BLACK;
//把祖父節點變為紅色
pFixNode->pParent->pParent->eColor = E_TREE_RED;
//以祖父節點右旋轉(注意到為根節點的情況)
pFixNode = pFixNode->pParent->pParent;
//記錄下新的頂點
PTreeNode pNewTop = nullptr;
if (m_pRoot == pFixNode)
{
SingleR(m_pRoot, pNewTop);
}
else if (pFixNode == pFixNode->pParent->pLeft)
{
SingleR(pFixNode->pParent->pLeft, pNewTop);
}
else if (pFixNode == pFixNode->pParent->pRight)
{
SingleR(pFixNode->pParent->pRight, pNewTop);
}
//重新設置調整點
pFixNode = pNewTop->pLeft;
}
}
//2. 如果調整節點的父親為祖父節點的右孩子
else if (pFixNode->pParent == pFixNode->pParent->pParent->pRight)
{
//獲取叔叔節點(祖父節點的左孩子)
PTreeNode pUncle = pFixNode->pParent->pParent->pLeft;
//2.1 如果叔叔節點為紅色
if (E_TREE_RED == pUncle->eColor)
{
//把父親節點和叔叔節點都改為黑色
pFixNode->pParent->eColor = E_TREE_BLACK;
pUncle->eColor = E_TREE_BLACK;
//把祖父節點改為紅色
pFixNode->pParent->pParent->eColor = E_TREE_RED;
//重新計算調整節點為祖父節點
pFixNode = pFixNode->pParent->pParent;
}
//2.2 叔叔節點不為紅色，且調整節點為父親節點的左孩子,變為情況2.3
else if (pFixNode == pFixNode->pParent->pLeft)
{
//從調整節點的父節點開始旋轉
pFixNode = pFixNode->pParent;
//記錄下新的頂點
PTreeNode pNewTop = nullptr;
SingleR(pFixNode->pParent->pRight, pNewTop);
//重新設置調整節點
pFixNode = pNewTop->pRight;
}
//2.3 叔叔節點不為紅色，且調整節點為父親節點的右邊孩子
else if (pFixNode == pFixNode->pParent->pRight)
{
//把父親節點變為黑色
pFixNode->pParent->eColor = E_TREE_BLACK;
//把祖父節點變為紅色
pFixNode->pParent->pParent->eColor = E_TREE_RED;
//以祖父節點左旋轉(注意到為根節點的情況)
pFixNode = pFixNode->pParent->pParent;
//記錄下新的頂點
PTreeNode pNewTop = nullptr;
if (m_pRoot == pFixNode)
{
SingleL(m_pRoot, pNewTop);
}
else if (pFixNode == pFixNode->pParent->pLeft)
{
SingleL(pFixNode->pParent->pLeft, pNewTop);
}
else if (pFixNode == pFixNode->pParent->pRight)
{
SingleL(pFixNode->pParent->pRight, pNewTop);
}
//重新設置調整點
pFixNode = pNewTop->pRight;
}
}
}
//在調整的過程中有可能修改了根節點的顏色為紅色，需要修改為黑色
m_pRoot->eColor = E_TREE_BLACK;
}
......代碼過長，點擊閱讀原文去原帖查看完整代碼
main.cpp
#include "RBTree.h"
#include
int main(int argc, char * argv[])
{
RBTree rbTree;
//插入序列
int nArryInsertValue[] = { 12, 1, 9, 2, 0, 11, 7, 19, 4, 15, 18, 5, 14, 13, 10, 16, 6, 3, 8, 17 };
for (int i = 0; i < sizeof(nArryInsertValue) / sizeof(nArryInsertValue[0]); i++)
{
rbTree.InsertData(nArryInsertValue[i]);
}
//廣度遍歷
rbTree.BreadthEnum();
std::cout << "------------------------------" << std::endl;
//刪除序列
for (int i = 0; i < sizeof(nArryInsertValue) / sizeof(nArryInsertValue[0]); i++)
{
std::cout << "刪除" << nArryInsertValue[i] << "後" << std::endl;
rbTree.DeleteElement(nArryInsertValue[i]);
rbTree.BreadthEnum();
}
//插入任意序列
std::cout << "插入任意序列" << std::endl;
for (int i = 0; i < 100; i++)
{
rbTree.InsertData(i);
}
//查找3
std::cout << "查找3" << std::endl;
std::cout << "結果:"<< rbTree.FindElement(3) << std::endl;
//廣度遍歷
rbTree.BreadthEnum();
std::cout << "------------------------------" << std::endl;
//刪除任意序列,只留三個
for (int i = 99; i >= 3; i--)
{
rbTree.DeleteElement(i);
}
//廣度遍歷
rbTree.BreadthEnum();
std::cout << "------------------------------" << std::endl;
return 0;
}
運行結果
插入結果(後面有圖解)
刪除結果(後面有單步圖解)
插入圖解
插入結點：12、1、9、2、0、11、7、19、4、15、18、5、14、13、10、16、6、3、8、17 全程演示
1、插入節點12
2、插入節點1
3、插入結點9（左-情況2）
4、插入結點2（左-情況1）
5、插入結點0
6、插入結點11
7、插入結點7（右-情況1）
8、插入結點19
9、插入結點4（右-情況2）
10、插入結點15（右-情況1）
11、插入結點18（左-情況2）
12、插入結點5（右-情況1）
13、插入結點14（左-情況1）
14、插入結點13（左-情況3）
15、插入結點10
16-1、插入結點16（右-情況1）
17、插入結點6（左-情況2）
18、插入結點3（左-情況2）
19、插入節點8
20、插入結點17（右-情況3）
刪除圖解
1、刪除結點12（右-情況4）
2、刪除結點1（左-情況4）
3、刪除結點9（左-情況2）
5、刪除結點0
6、刪除結點11
7、刪除結點7
8、刪除結點19（右-情況4）
9、刪除結點4（左-情況2）
10、刪除結點15（左-情況3）
11、刪除結點18（右-情況2）
12、刪除結點5（左-情況4）
13、刪除結點14（左-情況3）
14、刪除結點13（左-情況2）
15、刪除結點10
16、刪除結點16（右-情況1）
17、刪除結點6
18、刪除結點3（左-情況2）
19、刪除結點8
20、刪除結點17
關注看雪學院公眾號，獲取更多幹貨哦！
閱讀更多 看雪學院 的文章
