碼圖並茂紅黑樹

05-01

轉眼就快畢業了，既然準備找工作聽說最好發點帖子，那麼第一篇就拿數據結構開刀吧！

當初自己想寫紅黑樹時候參考了網上的代碼，最後發現還是<<演算法導論>中的偽代碼最好懂，所以代碼完全按照<<演算法導論>>偽代碼來編寫，方便對照<<演算法導論>>來學習紅黑樹。

寫紅黑樹的文章很多，這篇文章和其他寫紅黑樹的區別：

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 <queue>#include <assert.h>#include <iostream>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<PTreeNode> 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<PTreeNode> 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 <iostream>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;}