1. Python技术站首页
  2. 数据结构

C++数据结构之红黑树的实现

• 数据结构

《C++数据结构之红黑树的实现》是一篇介绍红黑树实现的文章，通过本文，你可以了解到什么是红黑树以及如何实现红黑树。

什么是红黑树

红黑树是一种自平衡的二叉查找树，它具有良好的平衡性和查找性能。红黑树可以在O(log n)的时间内完成查找、插入和删除操作。

红黑树的一个重要性质是它的任何一个节点都有一个颜色（红色或黑色）属性。在插入、删除操作中，需要通过一定的规则来对节点的颜色、位置进行调整来维持红黑树的平衡性。

红黑树的实现

红黑树的实现需要涉及到节点的定义、插入、删除、查找等操作。下面分别进行介绍。

节点的定义

红黑树节点需要保存节点的数据、颜色、指向父节点、左子树、右子树的指针。定义如下：

template<typename T>
struct RBNode {
    T data;
    bool color;
    RBNode<T>* parent, * left, * right;

    RBNode(T data, bool color = false, RBNode<T>* parent = nullptr,
        RBNode<T>* left = nullptr, RBNode<T>* right = nullptr) : data(data), color(color), parent(parent), left(left), right(right) {}
};

插入操作

插入节点时，需要通过旋转和变色来保证红黑树的平衡性。

插入时，首先按照二叉查找树的规则找到插入位置，并插入一个红色节点。如果父节点是黑色，插入结束，红黑树仍然保持平衡；如果父节点是红色，则需要进行平衡操作。

平衡操作有以下几种：

  1. 如果插入节点的父节点是爷爷节点的左孩子，则叔叔节点是右孩子：

a. 如果叔叔节点是红色的，则重新给父节点和叔叔节点涂黑色，爷爷节点涂红色，并将爷爷节点作为当前节点进行后续平衡操作。

b. 如果叔叔节点是黑色的，并且当前节点是父节点的右孩子，则左旋转父节点，并把父节点作为当前节点进行后续平衡操作。

c. 如果叔叔节点是黑色的，并且当前节点是父节点的左孩子，则将父节点涂黑色，爷爷节点涂红色，然后以爷爷节点为支点进行右旋转。

  1. 如果插入节点的父节点是爷爷节点的右孩子：

a. 如果叔叔节点是红色的，则重新给父节点和叔叔节点涂黑色，爷爷节点涂红色，并将爷爷节点作为当前节点进行后续平衡操作。

b. 如果叔叔节点是黑色的，并且当前节点是父节点的左孩子，则右旋转父节点，并把父节点作为当前节点进行后续平衡操作。

c. 如果叔叔节点是黑色的，并且当前节点是父节点的右孩子，则将父节点涂黑色，爷爷节点涂红色，然后以爷爷节点为支点进行左旋转。

插入操作的代码实现如下：

template<typename T>
void RBTree<T>::insertFixup(RBNode<T>* node) {
    while (node->parent && node->parent->color == red) {
        RBNode<T>* p = node->parent;
        RBNode<T>* g = node->parent->parent;
        if (p == g->left) {
            RBNode<T>* u = g->right;
            if (u && u->color == red) {
                p->color = black;
                u->color = black;
                g->color = red;
                node = g;
            }
            else {
                if (node == p->right) {
                    node = p;
                    leftRotate(node);
                    p = node->parent;
                }
                p->color = black;
                g->color = red;
                rightRotate(g);
            }
        }
        else {
            RBNode<T>* u = g->left;
            if (u && u->color == red) {
                p->color = black;
                u->color = black;
                g->color = red;
                node = g;
            }
            else {
                if (node == p->left) {
                    node = p;
                    rightRotate(node);
                    p = node->parent;
                }
                p->color = black;
                g->color = red;
                leftRotate(g);
            }
        }
    }
    root->color = black;
}

template<typename T>
void RBTree<T>::insert(T data) {
    // 创建插入节点
    RBNode<T>* node = new RBNode<T>(data, red);

    // 查找插入位置
    RBNode<T>* p = nullptr;
    RBNode<T>* cur = root;
    while (cur) {
        p = cur;
        if (data < cur->data) {
            cur = cur->left;
        }
        else {
            cur = cur->right;
        }
    }

    // 连接父节点和插入节点
    node->parent = p;
    if (!p) {
        root = node;
    }
    else if (data < p->data) {
        p->left = node;
    }
    else {
        p->right = node;
    }

    // 修复红黑树
    insertFixup(node);
}

删除操作

删除节点时，是突出之处。当要删除的节点有两个非空子节点时，无法直接删除该节点。如果直接删除该节点，会破坏红黑树的平衡性，因此，在删除前需要找到要删除节点的前驱或后继节点来替换要删除的节点。同时，需要进行旋转和变色来保持红黑树平衡。

① 如果要删除的节点没有孩子或只有一个孩子，直接删除。

② 如果要删除的节点有两个孩子，则找到它的后继节点（该节点的左子树中最小的节点），并将后继节点的数据替换到要删除的节点中，然后删除后继节点。

删除操作的代码实现如下：

template<typename T>
void RBTree<T>::removeFixup(RBNode<T>* node, RBNode<T>* p) {
    while (node != root && (!node || node->color == black)) {
        if (node == p->left) {
            RBNode<T>* s = p->right;
            if (s->color == red) {
                s->color = black;
                p->color = red;
                leftRotate(p);
                s = p->right;
            }
            if ((!s->left || s->left->color == black) && (!s->right || s->right->color == black)) {
                s->color = red;
                node = p;
                p = p->parent;
            }
            else {
                if (!s->right || s->right->color == black) {
                    s->left->color = black;
                    s->color = red;
                    rightRotate(s);
                    s = p->right;
                }
                s->color = p->color;
                p->color = black;
                s->right->color = black;
                leftRotate(p);
                node = root;
            }
        }
        else {
            RBNode<T>* s = p->left;
            if (s->color == red) {
                s->color = black;
                p->color = red;
                rightRotate(p);
                s = p->left;
            }
            if ((!s->right || s->right->color == black) && (!s->left || s->left->color == black)) {
                s->color = red;
                node = p;
                p = p->parent;
            }
            else {
                if (!s->left || s->left->color == black) {
                    s->right->color = black;
                    s->color = red;
                    leftRotate(s);
                    s = p->left;
                }
                s->color = p->color;
                p->color = black;
                s->left->color = black;
                rightRotate(p);
                node = root;
            }
        }
    }
    if (node) {
        node->color = black;
    }
}

template<typename T>
void RBTree<T>::remove(const T& data) {
    RBNode<T>* node = searchNode(data);
    if (!node) {
        return;
    }

    // 记录删除节点的颜色和父节点
    bool color = node->color;
    RBNode<T>* p = node->parent;

    // 如果有两个孩子，则找到后继节点，用后继节点替代
    if (node->left && node->right) {
        RBNode<T>* s = node->right;
        while (s->left) {
            s = s->left;
        }
        node->data = s->data;
        node = s;
        p = s->parent;
        color = s->color;
    }

    // 替换节点为其左右孩子节点
    RBNode<T>* child = node->left ? node->left : node->right;
    if (child) {
        child->parent = p;
    }

    if (!p) {
        root = child;
    }
    else if (node == p->left) {
        p->left = child;
    }
    else {
        p->right = child;
    }

    // 修复红黑树
    if (color == black) {
        removeFixup(child, p);
    }

    delete node;
}

查找操作

查找操作与普通二叉查找树中的查找操作相同，效率为O(log n)。具体实现如下：

template<typename T>
RBNode<T>* RBTree<T>::searchNode(const T& data) const {
    RBNode<T>* cur = root;
    while (cur) {
        if (cur->data == data) {
            return cur;
        }
        else if (data < cur->data) {
            cur = cur->left;
        }
        else {
            cur = cur->right;
        }
    }
    return nullptr;
}

示例说明

下面给出两个关于红黑树的示例：

示例一

给定一个字符串数组，如何用红黑树实现字符串去重？

思路：遍历字符串数组，将其插入红黑树中，如果遇到重复的字符串，则不插入，最终得到的树中的所有节点即为去重后的字符串。插入时，需要重载比较运算符。

代码实现：

#include "RBTree.h"
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {
    vector<string> strs = { "hello", "world", "hello", "cpp", "world" };
    RBTree<string> tree;
    for (auto& str : strs) {
        tree.insert(str);
    }
    // 输出去重后的字符串
    tree.inOrder([](const string& str) {
        cout << str << " ";
    });
    // 输出结果：cpp hello world 
    return 0;
}

示例二

如何用红黑树实现一个有序集合？

思路：通过红黑树来实现一个有序集合，可以保证该集合中的元素按照从小到大的顺序排列。在插入节点和删除节点时，保持红黑树的平衡性，通过遍历树，可以输出有序集合中的元素。

代码实现：

#include "RBTree.h"
#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> nums = { 3, 1, 4, 5, 2 };
    RBTree<int> tree;
    for (auto& num : nums) {
        tree.insert(num);
    }

    // 遍历树，输出集合元素
    tree.inOrder([](int num) {
        cout << num << " ";
    });
    // 输出结果：1 2 3 4 5

    return 0;
}

以上就是关于C++数据结构之红黑树的实现的完整攻略，希望能对你有所帮助。

本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C++数据结构之红黑树的实现 - Python技术站

赞 (0)
0 0 打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023年5月17日
下一篇 2023年5月17日

相关文章

  • 如何配置git环境

    首先我们新建一个文件夹；    然后我们右键git Bash Here一下;在里面输入： cd ssh-keygen cd.ssh ls (注意，我们要是之前就生成过密钥，直接输入ls就好了) 输入ls之后，会显示出来我们的公钥，我们输入： cat id_rsa.pub 然后密钥就出来了，密钥出来之后，我们把密钥复制一下，打开github 选择设置； 中会有…

    算法与数据结构 2023年4月18日
    00

  • C++高级数据结构之线段树

    C++高级数据结构之线段树攻略 什么是线段树 线段树是一种数据结构，它可以支持区间查询和单点修改，是处理静态区间问题的常用手段。它利用了 二分思想，将区间离散化成一些个体，然后考虑对个体进行处理，再结合区间合并的特性，更新区间信息。线段树主要由四个操作构成：建树、单点修改、区间查询和区间修改。 线段树的数据表示 在实现线段树时，我们需要考虑数据结构的几个要素…

    数据结构 2023年5月17日
    00

  • PHP 数据结构队列(SplQueue)和优先队列(SplPriorityQueue)简单使用实例

    下面我来为大家详细讲解一下“PHP 数据结构队列(SplQueue)和优先队列(SplPriorityQueue)简单使用实例”的攻略。 一、SplQueue 首先，我们先来介绍一下SplQueue。SplQueue是一个双向队列，它基于一个双向链表实现，可以在队列的两端插入和删除元素，既可以按照先进先出的顺序来操作队列，也可以反过来按照先进后出的顺序来操作…

    数据结构 2023年5月17日
    00

  • Java 数据结构算法Collection接口迭代器示例详解

    Java 数据结构算法 Collection 接口迭代器示例详解 如果你正在学习 Java 编程，那么数据结构和算法一定是一个不可避免的话题。在 Java 中，Collection 框架提供了许多有用的接口和类来管理和操作集合。其中，迭代器 Iterator 是 Collection 中最重要的接口之一，它提供了对集合元素进行迭代的方法。本文将对 Java …

    数据结构 2023年5月17日
    00

  • 自制PHP框架之模型与数据库

    很好，下面我将为您详细讲解如何自制PHP框架中的模型与数据库部分。 什么是模型和数据库？ 在讲解自制PHP框架的模型和数据库前，我们需要先了解什么是模型和数据库。在PHP框架架构中，模型是用来操作数据库的一种机制，用来处理对数据表的增删改查等操作，并且与数据库的连接是一定的。而数据库是一种数据存储工具，用于存储数据并提供数据操作的方法，例如数据的增删改查等。…

    数据结构 2023年5月17日
    00

  • 手撕HashMap（二）

    这里再补充几个手撕HashMap的方法 1、remove() remove 方法参数值应该是键值对的键的值，当传入键值对的键的时候，remove 方法会删除对应的键值对 需要利用我们自己先前创建的 hashcodeList 来实现，hashcodeList 存入了所有被使用的 hashcode 值，方便后续的操作 在 put() 中，当添加新的键值对时，就会…

    算法与数据结构 2023年4月18日
    00

  • 深入理解Objective-C中类的数据结构

    深入理解Objective-C中类的数据结构 在Objective-C中，类作为面向对象编程的基础，是必不可少的概念。理解Objective-C中类的数据结构，对于开发者理解iOS应用程序的底层原理，以及编写高质量代码具有重要的意义。 类的数据结构 一个Objective-C类由以下几部分组成： isa指针：指向该类对象的元类，元类是描述一个类的对象。isa…

    数据结构 2023年5月17日
    00

  • 栈(Stack)

    概述 栈就是一种 只允许在表尾进行插入和删除操作 的 线性表 栈的特点 先进后出 ，在表尾进行插入和删除操作 数组实现栈 crown crown：使用bottom来确定栈顶所在数组的下标，默认为 -1 空栈 当空栈时 ，crown = -1 栈是否为空 当 crown = -1 时 ，栈为空 ，不能 遍历 ，出栈 ， 获取栈顶元素 栈是否已满 当 crown…

    算法与数据结构 2023年4月19日
    00
合作推广
合作推广
分享本页
返回顶部