樹绿聘，二叉樹，二叉查找樹以及紅黑樹

本文主講二叉樹系列

樹的概念

鏈表通炒∩郑可以提供比數(shù)組更大的靈活性杈抢，但由于鏈表是線性結(jié)構(gòu)，所以很難使用它們來組織對象的分層表示仑性。雖然隊列反映了某些層次惶楼，但它們是一維的，為了避免這種限制诊杆，創(chuàng)建了一個新型數(shù)據(jù)類型歼捐，稱為樹，樹由節(jié)點和弧組成晨汹。
樹在計算機科學(xué)里豹储，是一種十分基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)。幾乎所有操作系統(tǒng)都將文件存放在樹狀結(jié)構(gòu)里淘这；幾乎所有的編譯器都需要實現(xiàn)一個表達式樹剥扣；文件壓縮所用的哈夫曼算法需要用到哈夫曼樹；數(shù)據(jù)庫所使用的B樹铝穷，以及map,set等容器底層數(shù)據(jù)結(jié)構(gòu)紅黑樹朦乏。

圖1.png

圖 1(A) 是使用樹結(jié)構(gòu)存儲的集合 {A,B,C,D,E,F,G,H,I,J,K,L,M} 的示意圖。對于數(shù)據(jù) A 來說氧骤，和數(shù)據(jù) B呻疹、C、D 有關(guān)系；對于數(shù)據(jù) B 來說刽锤，和 E镊尺、F 有關(guān)系。這就是“一對多”的關(guān)系并思。

將具有“一對多”關(guān)系的集合中的數(shù)據(jù)元素按照圖 1（A）的形式進行存儲庐氮，整個存儲形狀在邏輯結(jié)構(gòu)上看，類似于實際生活中倒著的樹（圖 1（B）倒過來）宋彼，所以稱這種存儲結(jié)構(gòu)為“樹型”存儲結(jié)構(gòu)弄砍。

什么是二叉樹

簡單地理解，滿足以下兩個條件的樹就是二叉樹：
1.本身是有序樹输涕；
2.樹中包含的各個節(jié)點的度不能超過 2音婶，即只能是 0、1 或者 2莱坎；

圖2.gif

經(jīng)過前人的總結(jié)衣式，二叉樹具有以下幾個性質(zhì)：
1.二叉樹中，第 i 層最多有 2^(i-1) 個結(jié)點檐什。
2.如果二叉樹的深度為 K碴卧，那么此二叉樹最多有 2^K-1 個結(jié)點。
3.二叉樹中乃正，終端結(jié)點數(shù)（葉子結(jié)點數(shù)）為 n0住册，度為 2 的結(jié)點數(shù)為 n2，則 n0=n2+1瓮具。

性質(zhì) 3 的計算方法為：對于一個二叉樹來說荧飞，除了度為 0 的葉子結(jié)點和度為 2 的結(jié)點，剩下的就是度為 1 的結(jié)點（設(shè)為 n1）搭综，那么總結(jié)點 n=n0+n1+n2。
同時划栓，對于每一個結(jié)點來說都是由其父結(jié)點分支表示的兑巾，假設(shè)樹中分枝數(shù)為 B，那么總結(jié)點數(shù) n=B+1忠荞。而分枝數(shù)是可以通過 n1 和 n2 表示的蒋歌，即 B=n1+2 * n2。所以委煤，n 用另外一種方式表示為 n=n1+2 * n2+1堂油。
兩種方式得到的 n 值組成一個方程組，就可以得出 n0=n2+1碧绞。
二叉樹還可以繼續(xù)分類府框，衍生出滿二叉樹和完全二叉樹

滿二叉樹

如果二叉樹中除了葉子結(jié)點，每個結(jié)點的度都為 2讥邻，則此二叉樹稱為滿二叉樹迫靖。

滿二叉樹.gif

如圖所示就是一棵滿二叉樹院峡。

滿二叉樹除了滿足普通二叉樹的性質(zhì)，還具有以下性質(zhì)：
1.)滿二叉樹中第 i 層的節(jié)點數(shù)為 2^（n-1）個系宜。
2.)深度為 k 的滿二叉樹必有 2^k-1 個節(jié)點照激，葉子數(shù)為 2^(k-1)。
3.)滿二叉樹中不存在度為 1 的節(jié)點盹牧，每一個分支點中都兩棵深度相同的子樹俩垃，且葉子節(jié)點都在最底層。
4.)具有 n 個節(jié)點的滿二叉樹的深度為 log2(n+1)汰寓。

完全二叉樹

如果二叉樹中除去最后一層節(jié)點為滿二叉樹口柳，且最后一層的結(jié)點依次從左到右分布，則此二叉樹被稱為完全二叉樹踩寇。

完全二叉樹.gif

如圖 a) 所示是一棵完全二叉樹啄清，圖 b) 由于最后一層的節(jié)點沒有按照從左向右分布，因此只能算作是普通的二叉樹俺孙。

對于任意一個完全二叉樹來說辣卒，如果將含有的結(jié)點按照層次從左到右依次標號（如圖 3a)）(從1開始標號，即根節(jié)點標號為1睛榄，若從0開始標號荣茫，則結(jié)論有所不同），對于任意一個結(jié)點 i 场靴，完全二叉樹還有以下幾個結(jié)論成立：
1)當 i>0 時啡莉，父親結(jié)點為結(jié)點 [i/2] 。（i=1 時魄咕，表示的是根結(jié)點膏秫，無父親結(jié)點）
2)如果 2i>n（總結(jié)點的個數(shù)），則結(jié)點 i 肯定沒有左孩子（為葉子結(jié)點）；否則其左孩子是結(jié)點 2i 。
3)如果 2i+1>n ，則結(jié)點 i 肯定沒有右孩子；否則右孩子是結(jié)點 2i+1 。

二叉樹的遍歷

在這里給出二叉樹的非遞歸遍歷算法
以下圖為例：

可在leetcode的探索中去刷關(guān)于樹的遍歷的題桑涎。（以下給出遍歷代碼皆在LeetCode中通過）

前序遍歷

前序遍歷結(jié)果：[1,2,4,5,3,6,7]
用棧來存儲節(jié)點：
1）節(jié)點1等曼，2篙程，4依次入棧渴肉，節(jié)點4 的左孩子為空乌奇，停止入棧；[1,2,4]
2）節(jié)點4 出棧，其右孩子為空携御，則不操作接著節(jié)點2出棧誓军，其右孩子不為空則進棧袱讹，節(jié)點5進棧捷雕，其左孩子為空停止進棧救巷；[1,5]
3)節(jié)點5 出棧妻枕，右孩子為空；接著節(jié)點1（根節(jié)點）出棧晴氨，右孩子不為空則節(jié)點3進棧亭珍，節(jié)點6為其左孩子則繼續(xù)進棧；[3,6]
4)節(jié)點6,3出棧枝哄，節(jié)點7進棧肄梨；[7]
5）最后節(jié)點7出棧，左右孩子皆為空挠锥，棧也為空众羡，則遍歷結(jié)束。
具體代碼如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root==nullptr) return result;
        stack<TreeNode*> s;
        TreeNode* p=root;
        while(!s.empty() || p!=nullptr) //當回到根節(jié)點蓖租，判斷右節(jié)點粱侣，此時 棧是空的，因此加一個p不為空的判斷n
        {
            while(p!=nullptr)
            {
                //前序遍歷蓖宦，先保存遍歷結(jié)果
                result.push_back(p->val);
                s.push(p);
                p=p->left;
            }
            TreeNode* t=s.top();
            s.pop();
            if(t->right!=nullptr)
            {
                p=t->right;
            }
        }
        return result;
    }
};

中序遍歷

中序遍歷結(jié)果：[4,2,5,1,6,3,7]
步驟和前序遍歷相同齐婴，不在贅述，只是打印結(jié)果位置不同稠茂，中序遍歷在節(jié)點出棧時打印結(jié)果柠偶，前序遍歷在節(jié)點進棧時打印結(jié)果。
具體代碼如下：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:

    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root==nullptr)
        {
            return result;
        }
        TreeNode* p=root;
        stack<TreeNode*> s;
        while(!s.empty() || p!=nullptr)
        {
            while(p!=nullptr)
            {
                s.push(p);
                p=p->left;
            }
            TreeNode* t=s.top();
            s.pop();
            //出棧時打印結(jié)果
            result.push_back(t->val);
            if(t->right!=nullptr) p=t->right;
        }
        return result;
    }
};

后序遍歷

后序遍歷結(jié)果：[4,5,2,6,7,3,1]
過程稍微有些不同睬关，類似于中序遍歷诱担，左邊的節(jié)點都是要第一個進行訪問，在這里只是右節(jié)點和根節(jié)點的區(qū)別电爹，同樣采用一個棧來解決這個問題蔫仙。
只是后序遍歷在決定是否可以輸出當前節(jié)點的值的時候，需要考慮其左右子樹是否都已經(jīng)遍歷完成藐不。
所以需要設(shè)置一個lastVisit游標匀哄。
若lastVisit等于當前考查節(jié)點的右子樹，表示該節(jié)點的左右子樹都已經(jīng)遍歷完成雏蛮，則可以輸出當前節(jié)點涎嚼。
并把lastVisit節(jié)點設(shè)置成當前節(jié)點，將當前游標節(jié)點node設(shè)置為空挑秉，下一輪就可以訪問棧頂元素
具體代碼：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> postorderTraversal(TreeNode* root) {
        vector<int> result;
        if(root==nullptr)
        {
            return result;
        }
        TreeNode* p=root;
        TreeNode* lastvisit=nullptr;
        stack<TreeNode*> s;
        while(!s.empty() || p!=nullptr)
        {
            while(p!=nullptr)
            {
                s.push(p);
                p=p->left;
            }
            TreeNode* t=s.top();
            if(t->right!=nullptr && lastvisit!=t->right)
            {
                p=t->right;
            }
            else
            {
                result.push_back(t->val);
                lastvisit=t;
                s.pop();
            }
        }
        return result;
    }
};

層序遍歷

層序遍歷結(jié)果：[1,2,3,4,5,6,7]
層序遍歷相對簡單法梯，用一個隊列來完成，首先根節(jié)點入隊列犀概，當節(jié)點處隊列的時候判斷左右子節(jié)點是否為空立哑，不為空則依次入隊列，直到隊列為空則遍歷完畢姻灶。

class Solution {
    public:
        vector<int> levelOrder(TreeNode* root) 
        {
            vector<int> ret;
            queue<TreeNode*> q;
            if(root)
                q.push(root);
            while(!q.empty())
            {
                TreeNode* temp = q.front();
                ret.push_back(temp->val);
                q.pop();
                if(temp->left)
                    q.push(temp->left);
                if(temp->right)
                    q.push(temp->right);
            }
            return ret;
        }
    };

如果層序遍歷按層打印結(jié)果：[ [1],[2,3],[4,5,6,7] ],則需要記錄每層節(jié)點的數(shù)量铛绰，具體代碼如下：

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> result;
        if(root==nullptr) return result;
        vector<int> t;
        queue<TreeNode*> q;
        TreeNode* p=root;
        int levelcount=1;
        int nextlevelcount=0;//記錄每層的節(jié)點數(shù)目
        q.push(root);
        while(!q.empty())
        {
            TreeNode* tmp=q.front();
            t.push_back(tmp->val);
            levelcount--;
            q.pop();
            if(tmp->left!=nullptr) 
            {
                q.push(tmp->left);
                nextlevelcount++;
            }
            if(tmp->right!=nullptr) 
            {
                q.push(tmp->right);
                nextlevelcount++;
            }
            if(levelcount==0)
            {
                result.push_back(t);
                t.clear();
                levelcount=nextlevelcount;
                nextlevelcount=0;
            }
        }
        return result;
    }
};

二叉搜索樹

完整代碼：https://github.com/songqiyuan/DataStruct/blob/master/Tree/searchTree.hpp
二叉搜索樹（BST）是二叉樹的一種特殊表示形式，它滿足如下特性：

1.每個節(jié)點中的值必須大于（或等于）存儲在其左側(cè)子樹中的任何值产喉。
2每個節(jié)點中的值必須小于（或等于）存儲在其右子樹中的任何值捂掰。

二叉搜索樹.png

二叉排序樹的操作主要有：
1.查找：遞歸查找是否存在key。
2.插入：原樹中不存在key曾沈，插入key返回true这嚣，否則返回false。
3.構(gòu)造：循環(huán)的插入操作塞俱。
4.刪除：（1）葉子節(jié)點：直接刪除姐帚，不影響原樹。
（2）僅僅有左或右子樹的節(jié)點：節(jié)點刪除后障涯，將它的左子樹或右子樹整個移動到刪除節(jié)點的位置就可以罐旗，子承父業(yè)。
（3）既有左又有右子樹的節(jié)點：找到須要刪除的節(jié)點p的直接前驅(qū)或者直接后繼s（尋找前驅(qū)和后繼節(jié)點）唯蝶，用s來替換節(jié)點p尤莺，然后再刪除節(jié)點s

具體實現(xiàn)代碼如下：

    void  _deleteNode(int y)
    {
        TreeNode* node = findKey(y);
        if (node == nullptr) return ;
    
        if (node->right == nullptr)
        {
            TransPlant( node, node->left); //情況1,情況2
        }
        else if (node->left == nullptr)
        {
                        //輔助函數(shù)
            TransPlant( node, node->right);//情況1,情況2
        }
        else
        {
                        //情況3
            //查找后繼節(jié)點
            TreeNode* tmp=increment(node);
            if (tmp->parent != node)// && tmp->right!=nullptr)
            {
                TransPlant(tmp, tmp->right);
                tmp->right = node->right;
                tmp->right->parent = tmp;
            }
            TransPlant(node, tmp);
            tmp->left = node->left;
            tmp->left->parent = tmp;
        }
        resetNode(node);
    }

紅黑樹

完整代碼：https://github.com/songqiyuan/DataStruct/blob/master/Tree/rbtree.hpp
在學(xué)習(xí)紅黑樹前先理解旋轉(zhuǎn)的概念：
也許因為輸入的值不夠隨機，也許因為經(jīng)過某些插入刪除操作二叉搜索樹可能會失去平衡生棍，搜索效率降低颤霎，如圖：

平衡與不平衡.png

所謂平衡與否，并沒有一個絕對的測量標準涂滴，“平衡”的大致意義是：沒有任何一個節(jié)點深度過大友酱，不同的平衡條件造就出不同的效率表現(xiàn)以及不同的實現(xiàn)復(fù)雜度。AVL-tree,RB-tree均可實現(xiàn)出平衡二叉樹柔纵。
由于刪除和添加操作對樹做了修改缔杉，結(jié)果可能違反了紅黑樹的性質(zhì)，為了維護這些性質(zhì)搁料，必須要修改樹中某些節(jié)點的顏色以及指針結(jié)構(gòu)或详。
指針結(jié)構(gòu)的修改是通過旋轉(zhuǎn)來完成的系羞，這是能保持二叉搜索樹性質(zhì)的搜索樹局部操作。如圖的左旋和右旋：

左右旋轉(zhuǎn).png

當在某個節(jié)點x上做左旋時霸琴，假設(shè)它的右孩子為y而不是NULL(x可以為其右孩子節(jié)點不是NULL節(jié)點的樹內(nèi)任意節(jié)點）椒振，左旋以x到y(tǒng)的鏈為“支軸”進行。它使y成為樹的新的根節(jié)點梧乘，x成為y的左孩子澎迎，y的左孩子成為x的右孩子，右旋轉(zhuǎn)類似选调，具體代碼如下：

//左旋和右旋
//左旋
void RotateLeft(TreeNode* node)
{
    TreeNode* y = node->right;
    node->right = y->left;
    if (y->left != nullptr)
    {
        y->left->parent = node;
    }
    y->parent = node->parent;
    if (node->parent == nullptr)
    {
        _root = y;
    }
    else if (node == node->parent->left)
    {
        node->parent->left = y;
    }
    else if (node == node->parent->right)
    {
        node->parent->right = y;
    }
    y->left = node;
    node->parent = y;
}
//右旋
void RotateRight(TreeNode* node)
{
    TreeNode* y = node->left;
    node->left = y->right;
    if (y->right != nullptr)
    {
        y->right->parent = node;
    }
    y->parent = node->parent;
    if (node->parent == nullptr)
    {
        _root = y;
    }
    else if (node == node->parent->left)
    {
        node->parent->left = y;
    }
    else if (node == node->parent->right)
    {
        node->parent->right = y;
    }
    y->right = node;
    node->parent = y;
}

紅黑樹的性質(zhì)

1.每個節(jié)點是紅色或者黑色夹供；
2.根節(jié)點是黑色的；
3.每個葉節(jié)點是黑色的仁堪；
4.如果一個節(jié)點是紅色的哮洽，則它的兩個子節(jié)點都是黑色的；
5.對于每個節(jié)點弦聂，從該節(jié)點到其所有后代葉節(jié)點的簡單路徑上袁铐，均包含相同數(shù)目的黑節(jié)點。

下面主要講講可能破壞紅黑樹性質(zhì)的刪除和插入操作横浑。

紅黑樹的插入操作

紅黑樹的插入操作和二叉搜索樹的插入過程是類似的剔桨，只是插入的最后有所改變：將插入的節(jié)點著為紅色（為什么是紅色，因為要保持紅黑樹的性質(zhì)5徙融，如果插入的顏色為黑色洒缀，則必然改變某條路徑上的黑節(jié)點的個數(shù)，破壞紅黑樹的性質(zhì)）欺冀，然后調(diào)整紅黑樹（插入的節(jié)點為紅色树绩，可能違背性質(zhì)1或4）。

為了理解RBInsertFixup()函數(shù)是如何工作的隐轩，首先饺饭，要確定當節(jié)點被插入并著色后，紅黑樹的性質(zhì)哪些是被破壞的职车。當插入為根節(jié)點時性質(zhì)2（根節(jié)點為黑色）被破壞瘫俊，當插入節(jié)點的父節(jié)點為紅色是性質(zhì)4被破壞。下圖是一個修正過程：

插入節(jié)點.png

情況1：z的叔父節(jié)點y是紅色的（由性質(zhì)4知悴灵，祖父節(jié)點為黑色）
情況2：z的叔父節(jié)點y是黑色的且z是一個右孩子
情況3：z的叔父節(jié)點y是黑色的且z是一個左孩子
代碼如下：

//插入操作
void _Insert(int key)
{
    TreeNode* node = _root;
    TreeNode* pNode = nullptr;
    while (node != nullptr)
    {
        pNode = node;
        if (key > node->val)
        {
            node = node->right;
        }
        else
        {
            node = node->left;
        }
    }
    TreeNode* pInsertNode = new TreeNode(key);
    //根節(jié)點為空扛芽，此時無數(shù)據(jù)
    if (pNode == nullptr)
    {
        _root = pInsertNode;
    }
    else if (pNode->val < key)
    {
        pNode->right = pInsertNode;
        pInsertNode->parent = pNode;
    }
    else
    {
        pNode->left = pInsertNode;
        pInsertNode->parent = pNode;
    }
        //修正紅黑樹
    RBInsertFixup(pInsertNode);
}
    //修正插入紅黑性質(zhì)
void RBInsertFixup(TreeNode* node)
{
    //當前插入節(jié)點 ，其父節(jié)點為紅色
    while (node->parent != nullptr && node->parent->color == RED)
    {
        if (node->parent->parent->left == node->parent)
        {
            TreeNode* uncle = node->parent->parent->right;
            if (uncle!=nullptr && uncle->color == RED)
            {
                //若父節(jié)點為紅色或叔父節(jié)點為紅色积瞒，則祖父節(jié)點一定為黑色
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            }
            else
            {
                if (node->parent->right == node)
                {
                    node = node->parent;
                    RotateLeft(node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                RotateRight(node->parent->parent);
            }
        }
        else if(node->parent->parent->right==node->parent)
        {
            TreeNode* uncle = node->parent->parent->left;
            if (uncle != nullptr && uncle->color == RED)
            {
                node->parent->color = BLACK;
                uncle->color = BLACK;
                node->parent->parent->color = RED;
                node = node->parent->parent;
            }
            else 
            {
                if (node == node->parent->left)
                {
                    node = node->parent;
                    RotateRight(node);
                }
                node->parent->color = BLACK;
                node->parent->parent->color = RED;
                RotateLeft(node->parent->parent);
            }
        }
    }
    _root->color = BLACK;
}

紅黑樹的刪除

刪除修正.png

下面所有情況都在真實刪除的節(jié)點的顏色為黑的前提下川尖，刪除節(jié)點顏色為紅色并不違反紅黑樹性質(zhì)。
情況1：x的兄弟節(jié)點w是紅色的
由于刪除節(jié)點為黑色茫孔，而w為紅色叮喳，則w必定有黑色子節(jié)點（性質(zhì)4）被芳，所以可以改變w和x.p的顏色，并做一次左旋（如圖中的(a)）,而不違反紅黑樹的任何性質(zhì)馍悟。旋轉(zhuǎn)后x的新兄弟節(jié)點為w的一個子節(jié)點畔濒，其顏色為黑色。這樣就將情況轉(zhuǎn)換為2,3或4處理赋朦。

情況2:x的兄弟節(jié)點w是黑色的，而且w的兩個子節(jié)點都是黑色的
如圖中(b)所示李破，將兄弟節(jié)點w著色為紅色宠哄，這樣以父節(jié)點為根的子樹到葉節(jié)點的黑色節(jié)點是相同的，但比其他路徑少一個黑色節(jié)點嗤攻，因此將父節(jié)點設(shè)置為為新的x節(jié)點毛嫉。此時父節(jié)點的顏色未知紅色或黑色，當為紅色時可以看出違背了性質(zhì)4妇菱，不過此時我們只需將當前x節(jié)點設(shè)置為黑色就可以了承粤，此時紅黑樹性質(zhì)全部恢復(fù)。當為黑色節(jié)點時闯团，轉(zhuǎn)換為其他情況辛臊。

情況3：x的兄弟節(jié)點w是黑色，w的左孩子是紅色房交，w的右孩子是黑色
如圖中(c)彻舰，可以交換w和其左孩子的顏色，然后對w進行右旋而不違反紅黑樹的性質(zhì)（不理解的話可以畫圖驗證一下）候味，現(xiàn)在x新的兄弟節(jié)點刃唤，w的左孩子。這樣我們就把情況3轉(zhuǎn)換為了情況4.

情況4：x的兄弟節(jié)點w是黑色的白群，且w的右孩子是紅色的
如圖中(d)所示尚胞，想辦法用紅色節(jié)點來來填補左子樹（x.p.left）中減少的黑節(jié)點數(shù),通過改變一些節(jié)點的顏色來實現(xiàn)：a.將w著色為其父節(jié)點的顏色；b.將w.right由紅色改為黑色帜慢；c.將x.p的顏色改為黑色（用該節(jié)點來填補左子樹中缺失的黑色節(jié)點數(shù)）笼裳；d.將x.p節(jié)點左旋，到此紅黑樹性質(zhì)恢復(fù)粱玲，將x設(shè)置為根節(jié)點侍咱，結(jié)束修正。

代碼實現(xiàn)：

    void  _deleteNode(int y)
    {
        TreeNode* node = findKey(y);
        if (node == nullptr) return;
        //記錄刪除節(jié)點的顏色
        int DeleteNodeColor = node->color;
        //需要調(diào)整的節(jié)點
        TreeNode* FixNode = nullptr;
        if (node->right == nullptr)
        {
            FixNode = node->left;
            TransPlant(node, node->left);
        }
        else if (node->left == nullptr)
        {
            FixNode = node->right;
            TransPlant(node, node->right);
        }
        else
        {
            //查找后繼節(jié)點
            TreeNode* tmp = increment(node);
            DeleteNodeColor = tmp->color;
            FixNode = tmp->right;
            if (tmp->parent == node)
            {
                FixNode->parent = tmp;
            }
            if (tmp->parent != node)// && tmp->right!=nullptr)
            {
                TransPlant(tmp, tmp->right);
                tmp->right = node->right;
                tmp->right->parent = tmp;
            }
            TransPlant(node, tmp);
            tmp->left = node->left;
            tmp->left->parent = tmp;
            tmp->color = node->color;
        }
        if (DeleteNodeColor == BLACK)
        {
            //處理平衡
            RBDeleteFixUp(FixNode);
        }
        resetNode(node);
    }
    void RBDeleteFixUp(TreeNode* node)
    {
        while (node != nullptr && node->color == BLACK && node != _root)
        {
            if (node == node->parent->left)
            {
                TreeNode* bnode = node->parent->right;
                //如果node為黑色節(jié)點密幔，怎為了保持紅黑樹性質(zhì)怎楔脯，其兄弟節(jié)點必定存在，即bnode不為空
                if (bnode->color == RED)
                {
                    //此時父節(jié)點一定為黑色
                    bnode->color = BLACK;
                    node->parent->color = RED;
                    RotateLeft(node->parent);
                    bnode = node->parent->right;
                }
                if (bnode->left->color == BLACK && bnode->right->color == BLACK)
                {
                    bnode->color = RED;
                    node = node->parent;
                }
                else
                {
                    if (bnode->right->color == BLACK)
                    {
                        //根據(jù)上一個條件判斷胯甩，則此時左節(jié)點必為紅色,父節(jié)點必為黑色
                        bnode->left->color = BLACK;
                        bnode->parent->color = RED;
                        RotateRight(bnode);
                        bnode = node->parent->right;
                    }
                    //如果兄弟節(jié)點的右節(jié)點為紅色
                    bnode->color = node->parent->color;
                    node->parent->color = BLACK;
                    bnode->right->color = BLACK;
                    RotateLeft(node->parent);
                    node = _root;//結(jié)束循環(huán)昧廷，達到平衡
                }
            }
            else if (node == node->parent->right)
            {
                TreeNode* bnode = node->parent->left;
                if (bnode->color == RED)
                {
                    bnode->color = BLACK;
                    node->parent->color = RED;
                    RotateRight(node->parent);
                    bnode = node->parent->left;
                }
                if (bnode->left->color == BLACK && bnode->right->color == BLACK)
                {
                    bnode->color = RED;
                    node = node->parent;
                }
                else
                {
                    if (bnode->left->color == BLACK)
                    {
                        bnode->color = RED;
                        bnode->right->color = BLACK;
                        RotateLeft(bnode);
                        bnode = node->parent->left;
                    }
                    bnode->color = node->parent->color;
                    node->parent->color = BLACK;
                    bnode->left->color = BLACK;
                    RotateLeft(node->parent);
                    node = _root;
                }
            }
        }
        if (node != nullptr)
        {
            node->color = BLACK;
        }
    }

紅黑樹測試結(jié)果：

紅黑樹測試結(jié)果.png

樹，二叉樹淹朋，二叉查找樹以及紅黑樹

樹笙各，二叉樹，二叉查找樹以及紅黑樹