算法导论ch13红黑树笔记与相应数据结构算法c++实现（上）-CSDN博客

本文链接：https://blog.csdn.net/Yunhandu/article/details/142849395

作者：Claude Du

本文主要内容来源于算法导论2022年第四版英文版与17年第三版中文版，13.3节和13.4节除了对英文原文进行了翻译，还自行修改了原书中部分描述性的错误，以及自行大量补充了原书中本要求读者自行求证的内容。这很可能是您在互联网上能够找到的第一篇如此诚意满满的，基于算法导论英文原书，手把手式的中文红黑树C++实现教程资料。（抱歉，本人师从Lebron，最近在钻研goat定制化奥义—疯狂加限定定语）

红黑树在算法中属于比较难的一个topic, 写这篇文章也充满了挑战与困难，也难免会各种各样的犯错，如果大家发现本文中的错误, 欢迎在评论中指出。如果觉得本文有用的话，还是希望大家能点赞，收藏，转发与订阅的方式来支持一下。

由于该篇章文章内容过长，所以我现在想想要不要把这个篇章分成上下两篇笔记，来方便大家阅读。

以下是各个小篇章简介与阅读建议：

13.1节给红黑树下了定义并提供了红黑树的大体代码框架。

13.2节讲解了红黑树中核心指针修改操作——旋转与其代码实现细节。

这两章节可以在1天读完并检验旋转操作。

13.3节讲解红黑树的插入操作与代码实现细节，难度较大，建议单独花一天阅读与尝试实现插入功能。

13.4节讲解红黑树的删除操作与代码实现细节，难度比13.3节大，建议单独花1~3天阅读与尝试实现删除功能。

13.1红黑树性质

红黑树是一棵二叉搜索树，它在每个节点增加了一个存储位来表示节点的颜色，RED或BLACK。红黑树中的节点c++实现如下：

typedef enum {
   RB_RED, RB_BLACK} RBColor;
template <typename T>
struct RBNode {
   
    T data_;
    RBNode<T>* parent_;
    RBNode<T>* lc_; // left child
    RBNode<T>* rc_; // right child
    RBColor color_;
    RBNode(T data = 0, RBNode<T>* parent = nullptr, RBNode<T>* lc = nullptr,
            RBNode<T>* rc = nullptr, RBColor color = RB_RED) : 
            data_(data), parent_(parent), lc_(lc), rc_(rc), color_(color) {
   }
};

通过对任何一条从根到叶子的简单路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出2倍。因而可以近似认为是平衡的。

一棵红黑树满足下面红黑性质的二叉树：

每个节点或是红色的，或是黑色的。
根节点是黑色的。
每个叶节点（Nil）是黑色的
如果一个节点是红色的，则它的两个子节点都是黑色的。
对每个节点，从该节点到其所有后代叶结点的简单路径上，均包含相同数目的黑色节点。

图13-1(a)显示了一个红黑树的例子。

在这里插入图片描述

为了便于处理红黑树代码中的边界条件，使用一个哨兵tNil来代表Nil（Nil在二叉搜索树的c++实现里，我直接用nullptr表示）。对于1棵红黑树，哨兵tNil是1个与树中普通节点有相同属性的对象。它的color属性为Black, 而其他属性parent, left child, right child 可以设置成任意值，我个人在c++实现里为了避免歧义，初始化tNil时将其指针属性全设置成nullptr, 后续tNil的parent属性是可以设置成其他值的。

红黑树中tNil相关的c++实现如下：

template <typename T> 
class RBTree {
   
private:
    RBNode<T>* root_;
    RBNode<T>* tNil;
    // other private attributes and function
public:
    RBTree() {
   
        tNil = new RBNode<T>();
        tNil->color_ = RB_BLACK;
        root_ = tNil;
    }
    ~RBTree() {
    
        std::cout << "Hi, my job is done. " << "\n";
        int toBeDel = 0;
        auto del =[&toBeDel](RBNode<T>* cur) {
   
            delete cur;
            cur = nullptr;
            ++toBeDel;
        };
        TravelPreRecursive(root_, del);
        delete tNil;
        tNil = nullptr;
        std::cout << "Here is the total num of Deleted internal nodes : " << toBeDel << std::endl;
        
    }
	// other public attributes and function
};