CPP基础|简单实现红黑树

发布于 2024-07-18  1138 次阅读

CPP|简单实现红黑树

引言

为什么要叫红黑树?为什么红黑树是红黑树,不是蓝白树,或者黄绿树,是不是歧视其他颜色

红黑树

红黑树是什么?,红黑树一种二叉树,是一种自近似平衡的,二叉搜索树,也是set和map的底层数据结构.

红黑树选择红色和黑色作为颜色主要是为了简化描述和实现,便于直观理解和操作.颜色本身没有特定的意义:

  • 节点颜色： 每个节点要么是红色,要么是黑色.
  • 根节点颜色： 根节点是黑色的.
  • 叶子节点（NIL 节点）颜色： 所有叶子节点（NIL 节点）都是黑色的.
  • 相邻节点颜色： 如果一个节点是红色的,则它的两个子节点都是黑色的.
  • 路径黑高度相等： 从任意节点到其每个叶子节点的简单路径上,黑色节点的数量相同.

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长.结果是这个树大致上是平衡的(近似平衡).

因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树.

是性质4导致路径上不能有两个连续的红色结点确保了这个结果.最短的可能路径都是黑色结点,最长的可能路径有交替的红色和黑色结点.因为根据性质5所有最长的路径都有相同数目的黑色结点,这就表明了没有路径能多于任何其他路径的两倍长.

因为红黑树是一种特化的二叉查找树,所以红黑树上的只读操作与普通二叉查找树相同.

为了保持红黑树的性质,我们可以对相关结点做一系列的调整,通过对树进行旋转（例如左旋和右旋操作）,即修改树中某些结点的颜色及指针结构,以达到对红黑树进行插入、删除结点等操作时,红黑树依然能保持它特有的性质（五点性质）

以上!引经据典完了,初次了解红黑树是啥的大伙是不是有点懵. 那我们就从 二叉树是啥 这样的宝宝巴士开始发车.

RST到RBT

二叉树是啥,二叉树就是一棵树,这棵树呢,从一个根节点开始,分裂出两个子节点,也只能有两个,一左一右.而二叉搜索树,就是二叉树上了一个排列规则:

  • 每个节点都有一个值
  • 每一个节点,左子树中所有节点.的值都小于这个节点的值,其右子树中所有节点的值都大于这个节点的值.

画个图来理解一下

image-20240716225621020

可以看到,确实左右子树都符合上面两条规则,这样子的好处是查找的效率很高,比如要找10,先判断根节点是否大于.大于找右,小于找左,,重复这个步骤.在理想情况下（树是平衡的），查找操作的时间复杂度是 O(log⁡n)。但是在最坏情况下（树退化成一个链表），时间复杂度会变为 O(n)。

树退化成一个链表的情况

image-20240716230836009

这里乍一看就很长了(这里应该说树的高度比较高),假设没有右节点这种情况下，查找的效率变成了最差的 O(n)，和直接在一个链表中查找没有区别。

所以呢,为了保持最坏情况下,保证树的高度平衡,再给二叉搜索树添加规则.来保持平衡 近似平衡.首先给节点定义了红色和黑色,用作理解.

  1. 根节点 叶子节点（空节点）是黑色的

  2. 红色节点不能有红色的子节 (一条线上不能右两个连续的红色节点)

  3. 从任何节点到其每个叶子的所有路径上必须具有相同数量的黑色节点(不包括自己)

构建红黑树全流程解析

为什么会有叶子节点,也就是空结点,其实是用来滤清红黑树的路径.每个节点都会有两个节点,如果没有值默认就是叶子结点.

默认插入节点为红色

注这里不使用左旋与右旋的说法.

假设,有这么一个顺序[17,18,23,34, 27,15,9,6,8,5,25] ,来逐步演示该图

  1. 按照二叉树的方式插入17 ,18 ,23

    image-20240717144914031

  2. 可以发现这里违反了规则二.将23节点变为黑色.变为黑色后发现18节点违反了规则三(默认叶子节点不画省略,下图是为了方便理解规则三).

    image-20240717145158769

    所以需要满足规则三,把18号作为根节点,二17号作为18号的左子节点,17 18号父子关系进行一个互换,(左旋)然后根据规则三和规则二变更节点颜色

    image-20240717150047662

  3. 接着插入34,因为不满足规则二把34变为黑色.

    image-20240717150619460

    结果发现并不满足规则三,17到34 有两个黑色节点.那么,为了统一黑色节点.因为根节点默认为黑色(规则一),只需要把只需要把17和23节点变为黑色,即可满足规则三

    image-20240717151304524

  4. 继续插入27

    image-20240717153748300

    34于27进行一个交换组成一条纯右链的递增链条.(后续左链则相反,为递减.)(右旋右孩子,左旋爷爷,然后变色)

    image-20240717153740542

    可以发现这里违反了规则二.将34节点变为黑色.变为黑色后发现18节点违反了规则三(与先前的一次思路相同) 把27号作为23的父节点,23号作为27号的左子节点,23 27号父子关系进行一个互换,然后根据规则三和规则二变更节点颜色(右旋右孩子,左旋爷爷,然后变色)

    image-20240717154136670

  5. 继续插入15,并没有破坏红黑树的特性规则.继续插入6,可以发现这是根上方的 情况是一个对称的操作.直接对插入节点的父节点15,和爷爷节点17进行一个身份互换,再变色.随即,满足了规则三和二.

    image-20240717155506274

  6. 继续插入6,发现违反规则二,并发现这个值比父节点和叔叔(右节点)节点的值都要小,那么为了不违反规则就将父节点和叔叔节点变为黑色,爷爷节点变为红色就可以

    image-20240717160205352

  7. 插入7,又是一个似曾相识的画面,变成递减的左链.然后重复进行父爷互换的身份的操作.

    image-20240717160606167

  8. 接下来是5,同上步骤6

  9. image-20240717161614747

    ,解决了外层的规则二冲突后,发现7和15出现又出现了规则二的冲突.,乍一看确实好像挺麻烦了.实际上这个情况一样是出现过的.我们需要观察局部,发现这个情况正是步骤5的情况,

    image-20240717162059786

    做好处理,后把去掉的节点再添加回去,返现并没有破坏红黑树的规则与性质.

    image-20240717162307175

  10. 接下来插入25

    image-20240717162950402

    发现诶,这不是步骤8的对称操作么?那就进行一个变色.

    image-20240717163030507

    发现又是一个相同的变色情况.继续

    发现根节点应该为黑色,好继续变色

    image-20240717163150495

最终红黑树构建[17,18,23,34, 27,15,9,67,5,25]完成.

插入总结

  1. 插入新节点：

    • 将新节点插入到红黑树中，就像在普通的二叉搜索树中那样。新节点的颜色初始化为红色。

  2. 检查红黑树性质：

    1. 如果新插入的节点是根节点，仅将其颜色改为黑色即可满足所有性质。
    2. 如果新节点的父节点是黑色，不违反红黑树的性质，不需要做任何额外的操作。
    3. 如果新节点的父节点是红色，就需要进行一些调整来修复树的性质，因为这违反了性质: 红色节点的子节点必须是黑色。

  3. 调整红黑树： 如果新节点的父节点是红色的，有以下几种情况需要处理：

    1. 父节点是爷爷节点的左孩子
      1. 叔叔节点为红色
        1. 更改叔叔节点和父节点为黑色
        2. 将爷爷节点设为红色
        3. 以爷爷节点为目标继续判断是否需要调整
      2. 叔叔节点为黑色或者不存在
        1. 如果新节点是父节点的右孩子, 将操作的目标节点变为其父亲, 并左旋
        2. 将操作节点(可能因为上一步的左旋, 操作节点发生了变化)设为黑色, 爷爷节点设为红色
        3. 右旋爷爷节点
    2. 父节点是爷爷节点的右孩子
      1. 叔叔节点为红色
        1. 更改叔叔节点和父节点为黑色
        2. 将爷爷节点设为红色
        3. 以爷爷节点为目标继续判断是否需要调整
      2. 叔叔节点为黑色或者不存在
        1. 如果新节点是父节点的左孩子, 将操作的目标节点变为其父亲, 并右旋
        2. 将操作节点(可能因为上一步的右旋, 操作节点发生了变化)设为黑色, 爷爷节点设为红色
        3. 左旋爷爷节点

    能需要向上递归地进行调整，直到根节点，或者直到不再违反红黑树的性质为止。

旋转操作解释：

  • 左旋：节点x的右孩子y变成x的父节点，x变成了y的左孩子。如果y有一个左孩子，它会变成x的右孩子。
  • 右旋：与左旋相反，节点x的左孩子y变成x的父节点，x变成了y的右孩子。如果y有一个右孩子，它会变成x的左孩子。

插入操作的关键在于重新着色和旋转操作，它们能够在不破坏二叉搜索树属性的同时，保持红黑树的近似平衡性质。这些操作虽然看似复杂，但是每次插入的时间复杂度仍然是O(log n)，因为红黑树的高度保持在log2(n)以内。

删除总结

TODO

代码实践

理解了红黑树的运作机理,.那么就可以可以动手实现一个简单的红黑树容器

构造一个节点结构体与树

enum class Color { RED, BLACK };
template <typename T>
struct Node {
    T data;
    Color color;
    std::shared_ptr<Node<T>> left, right, parent;

    Node(T data)
        : data(data), color(Color::RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

template <typename T>
class RedBlackTree {
public:
    void insert(const T& data);
    void inorder() const;
    int height() const;
`
private:

    std::shared_ptr<Node<T>> root = nullptr;
    void rotateLeft(std::shared_ptr<Node<T>>& node);
    void rotateRight(std::shared_ptr<Node<T>>& node);
    void fixInsertion(std::shared_ptr<Node<T>>& node);
    void inorderHelper(const std::shared_ptr<Node<T>>& node) const;
    std::string getColor(const std::shared_ptr<Node<T>>& node) const;
};

插入

template <typename T>
void RedBlackTree<T>::insert(const T &data) {
    auto newNode = std::make_shared<Node<T>>(data); // 创建新节点
    if (!root) { // 如果树为空
        newNode->color = Color::BLACK; // 新节点作为根节点，颜色为黑色
        root = newNode;
        ++size;
    } else {
        auto temp = root;
        std::shared_ptr<Node<T>> parent = nullptr;

        // 找到插入位置
        while (temp) {
            parent = temp;
            if (data < temp->data) {
                temp = temp->left;
            } else if (data > temp->data) {
                temp = temp->right;
            } else { // 如果键相等，则说明树中已有相同键的节点，删除新节点并返回
                return;
            }
        }
        ++size;
        newNode->parent = parent; // 设置新节点的父节点
        if (data < parent->data) {
            parent->left = newNode;
        } else {
            parent->right = newNode;
        }

        fixInsertion(newNode); // 修复插入后的红黑树性质
    }
}

template <typename T>
int RedBlackTree<T>::height() const {
    return heightHelper(root); // 从根节点开始计算高度
}

template <typename T>
int RedBlackTree<T>::heightHelper(const std::shared_ptr<Node<T>>& node) const {
    if (!node) {
        return 0; // 空节点高度为0
    }
    int leftHeight = heightHelper(node->left); // 递归计算左子树高度
    int rightHeight = heightHelper(node->right); // 递归计算右子树高度
    return std::max(leftHeight, rightHeight) + 1; // 当前节点高度为左右子树最大高度加1
}
template <typename T>
void RedBlackTree<T>::fixInsertion(std::shared_ptr<Node<T>> &node) {
    // 当新节点的父节点为红色时，需要进行调整
    while (node != root && node->parent->color == Color::RED) {
        auto grandparent = node->parent->parent; // 获取祖父节点
        if (node->parent == grandparent->left) { // 父节点是祖父节点的左孩子
            auto uncle = grandparent->right; // 获取叔叔节点
            if (uncle && uncle->color == Color::RED) { // 叔叔节点是红色
                node->parent->color = Color::BLACK;
                uncle->color = Color::BLACK;
                grandparent->color = Color::RED;
                node = grandparent;
            } else {
                if (node == node->parent->right) { // 新节点是右孩子
                    node = node->parent;
                    rotateLeft(node); // 左旋
                }
                node->parent->color = Color::BLACK;
                grandparent->color = Color::RED;
                rotateRight(grandparent); // 右旋
            }
        } else { // 父节点是祖父节点的右孩子
            auto uncle = grandparent->left; // 获取叔叔节点
            if (uncle && uncle->color == Color::RED) { // 叔叔节点是红色
                node->parent->color = Color::BLACK;
                uncle->color = Color::BLACK;
                grandparent->color = Color::RED;
                node = grandparent;
            } else {
                if (node == node->parent->left) { // 新节点是左孩子
                    node = node->parent;
                    rotateRight(node); // 右旋
                }
                node->parent->color = Color::BLACK;
                grandparent->color = Color::RED;
                rotateLeft(grandparent); // 左旋
            }
        }
    }
    root->color = Color::BLACK; // 根节点总是黑色
}

template <typename T>
void RedBlackTree<T>::rotateLeft(std::shared_ptr<Node<T>> &node) {
    auto rightChild = node->right; // 获取右孩子
    node->right = rightChild->left; // 将右孩子的左子树移到当前节点的右子树
    if (rightChild->left) {
        rightChild->left->parent = node; // 更新父节点指针
    }
    rightChild->parent = node->parent; // 更新右孩子的父节点指针
    if (!node->parent) {
        root = rightChild; // 如果当前节点是根节点，更新根节点
    } else if (node == node->parent->left) {
        node->parent->left = rightChild; // 更新父节点的左孩子指针
    } else {
        node->parent->right = rightChild; // 更新父节点的右孩子指针
    }
    rightChild->left = node; // 旋转
    node->parent = rightChild; // 更新父节点指针
}

template <typename T>
void RedBlackTree<T>::rotateRight(std::shared_ptr<Node<T>> &node) {
    auto leftChild = node->left; // 获取左孩子
    node->left = leftChild->right; // 将左孩子的右子树移到当前节点的左子树
    if (leftChild->right) {
        leftChild->right->parent = node; // 更新父节点指针
    }
    leftChild->parent = node->parent; // 更新左孩子的父节点指针
    if (!node->parent) {
        root = leftChild; // 如果当前节点是根节点，更新根节点
    } else if (node == node->parent->right) {
        node->parent->right = leftChild; // 更新父节点的右孩子指针
    } else {
        node->parent->left = leftChild; // 更新父节点的左孩子指针
    }
    leftChild->right = node; // 旋转
    node->parent = leftChild; // 更新父节点指针
}
template <typename T>
void RedBlackTree<T>::inorder() const {
    inorderHelper(root); // 调用中序遍历辅助函数
}

template <typename T>
void RedBlackTree<T>::inorderHelper(const std::shared_ptr<Node<T>> &node) const {
    if (!node)
        return; // 如果节点为空，直接返回
    inorderHelper(node->left); // 递归遍历左子树
    std::cout << node->data << " "; // 打印当前节点的数据
    inorderHelper(node->right); // 递归遍历右子树
}

删除

TODO(后续更新...)

Q&A

  1. 红黑树的特性是什么？

    A：红黑树具有以下五个重要的特性:

    • 每个节点要么是红色，要么是黑色。
    • 根节点是黑色的。
    • 每个叶子节点（NIL节点，空节点）是黑色的。
    • 如果一个节点是红色的，则它的两个子节点都是黑色的（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
    • 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

  2. 为什么红黑树的操作是对数时间复杂度的？

    A：红黑树是近似平衡的二叉搜索树，它能够保证在最坏的情况下基本操作（如插入、查找和删除）的时间复杂度为O(log n)，其中n是树中元素的数量。这是因为树的高度始终保持在对数级别，所有的操作都要在从根到叶子的路径上进行。

  3. 如何验证一个二叉树是不是红黑树？

A：为了验证一个二叉树是否是红黑树，我们需要检查上述提到的红黑树的五个性质是否都得到满足。这通常需要遍历树的各个节点来检查节点颜色以及路径上的黑色节点数目是否一致。

  1. 为什么红黑树不是完全平衡的二叉树？

A：完全平衡的二叉树（如 AVL 树）要求二叉树的每个节点的左右子树高度差最多为一。这种高度平衡保证了树操作的最优效率，但是维护这种严格平衡的成本较高，因为每次插入或删除操作都可能需要多次旋转来保证树的平衡。相比之下，红黑树允许更大的不平衡度，它只是一个近似平衡的二叉树，这降低了维护平衡的成本，使得插入和删除操作可以在更少的旋转次数下完成。这种权衡在实际应用中常常是有利的，因为它提供了一个很好的在性能和实现复杂度之间的平衡。