首页 > 其他分享 >数据结构之 红黑树入门教程、红黑树代码示例

数据结构之 红黑树入门教程、红黑树代码示例

时间：2024-08-20 12:24:19浏览次数：15  
标签：Node right pt parent 示例 color 入门教程 红黑树 left

红黑树（Red-Black Tree）是一种自平衡的二叉查找树（BST），它在插入、删除和查找操作后通过一些特定的规则来维护树的平衡，从而确保这些操作的时间复杂度始终为O(log n)。红黑树主要应用在需要高效动态集合操作的场景中，如操作系统中的进程调度器、数据库中的索引等。

红黑树的基本性质

红黑树的每个节点都有一个颜色属性，可以是红色或黑色。红黑树通过以下性质来维持平衡：

  1. 节点颜色：每个节点都是红色或黑色。
  2. 根节点：根节点必须是黑色的。
  3. 叶节点：每个叶节点（通常是空节点，表示nullptr）是黑色的。
  4. 红色节点的限制：红色节点不能有红色的子节点，即红色节点的子节点必须是黑色的。这确保了不会出现连续的红色节点。
  5. 黑色节点的平衡：从任意节点到其每个叶节点的所有路径上必须包含相同数量的黑色节点。

这些性质确保了树的高度近似平衡，从而保证了在最坏情况下，树的高度为O(log n)。

操作介绍

  • 插入：在红黑树中插入节点与在普通二叉查找树中插入类似，但插入后需要通过重新着色和旋转来恢复红黑树的平衡性。插入操作保证了红黑树的高度不会变得过高。

  • 删除：删除节点后的树可能会违反红黑树的性质，因此删除操作通常需要进行多次旋转和重新着色，以恢复树的平衡性。

  • 查找：红黑树的查找操作与普通二叉查找树相同，通过比较键值，沿树路径查找目标节点。

优势与应用

  1. 时间复杂度稳定：由于红黑树的自平衡特性，插入、删除和查找的时间复杂度始终为O(log n)，这使得红黑树在许多需要频繁动态操作的应用中非常有效。

  2. 动态调整：红黑树能够动态调整其结构，使其适用于一系列需要频繁插入和删除操作的场景，例如实时系统中的任务调度、编译器中的符号表管理等。

  3. 平衡性：红黑树保持了树的高度平衡，使得在大量数据的处理和访问过程中，操作时间不会因树的高度而显著增加。

红黑树的应用

  • C++ STL 的 map 和 set：C++的标准模板库中的map和set容器通常使用红黑树作为底层数据结构来实现。
  • 操作系统中的调度器：许多操作系统的任务调度器使用红黑树来管理任务队列，以保证任务的高效查找和插入。
  • 数据库索引：红黑树经常用于数据库中的索引结构，以便在大量数据中快速查找和维护索引。

红黑树代码实现

#include <iostream>
#include <queue>
using namespace std;

enum Color { RED, BLACK };

struct Node {
    int data;
    Color color;
    Node *left, *right, *parent;

    Node(int data) : data(data) {
        parent = left = right = nullptr;
        color = RED; // 新插入的节点是红色
    }
};

class RedBlackTree {
private:
    Node *root;

    void rotateLeft(Node *&);
    void rotateRight(Node *&);
    void fixInsert(Node *&);
    void fixDelete(Node *&);
    void inorderHelper(Node *node) const;
    void levelOrderHelper(Node *node) const;
    Node* minValueNode(Node* node);
    void deleteNodeHelper(Node* node, int key);

public:
    RedBlackTree() { root = nullptr; }
    void insert(int data);
    void deleteNode(int data);
    Node* search(int data);
    int extractMin();
    void inorder() const;
    void levelOrder() const;
};

void RedBlackTree::rotateLeft(Node *&pt) {
    Node *pt_right = pt->right;

    pt->right = pt_right->left;
    if (pt->right != nullptr)
        pt->right->parent = pt;

    pt_right->parent = pt->parent;

    if (pt->parent == nullptr)
        root = pt_right;

    else if (pt == pt->parent->left)
        pt->parent->left = pt_right;

    else
        pt->parent->right = pt_right;

    pt_right->left = pt;
    pt->parent = pt_right;
}

void RedBlackTree::rotateRight(Node *&pt) {
    Node *pt_left = pt->left;

    pt->left = pt_left->right;
    if (pt->left != nullptr)
        pt->left->parent = pt;

    pt_left->parent = pt->parent;

    if (pt->parent == nullptr)
        root = pt_left;

    else if (pt == pt->parent->left)
        pt->parent->left = pt_left;

    else
        pt->parent->right = pt_left;

    pt_left->right = pt;
    pt->parent = pt_left;
}

void RedBlackTree::fixInsert(Node *&pt) {
    Node *parent_pt = nullptr;
    Node *grand_parent_pt = nullptr;

    while ((pt != root) && (pt->color != BLACK) && (pt->parent->color == RED)) {
        parent_pt = pt->parent;
        grand_parent_pt = pt->parent->parent;

        if (parent_pt == grand_parent_pt->left) {
            Node *uncle_pt = grand_parent_pt->right;

            if (uncle_pt != nullptr && uncle_pt->color == RED) {
                grand_parent_pt->color = RED;
                parent_pt->color = BLACK;
                uncle_pt->color = BLACK;
                pt = grand_parent_pt;
            } else {
                if (pt == parent_pt->right) {
                    rotateLeft(parent_pt);
                    pt = parent_pt;
                    parent_pt = pt->parent;
                }

                rotateRight(grand_parent_pt);
                swap(parent_pt->color, grand_parent_pt->color);
                pt = parent_pt;
            }
        } else {
            Node *uncle_pt = grand_parent_pt->left;

            if (uncle_pt != nullptr && uncle_pt->color == RED) {
                grand_parent_pt->color = RED;
                parent_pt->color = BLACK;
                uncle_pt->color = BLACK;
                pt = grand_parent_pt;
            } else {
                if (pt == parent_pt->left) {
                    rotateRight(parent_pt);
                    pt = parent_pt;
                    parent_pt = pt->parent;
                }

                rotateLeft(grand_parent_pt);
                swap(parent_pt->color, grand_parent_pt->color);
                pt = parent_pt;
            }
        }
    }

    root->color = BLACK;
}

void RedBlackTree::insert(int data) {
    Node *pt = new Node(data);

    if (root == nullptr) {
        pt->color = BLACK;
        root = pt;
    } else {
        Node *current = root;
        Node *parent = nullptr;

        while (current != nullptr) {
            parent = current;
            if (pt->data < current->data)
                current = current->left;
            else
                current = current->right;
        }

        pt->parent = parent;

        if (pt->data < parent->data)
            parent->left = pt;
        else
            parent->right = pt;

        fixInsert(pt);
    }
}

void RedBlackTree::fixDelete(Node *&x) {
    while (x != root && x->color == BLACK) {
        if (x == x->parent->left) {
            Node *w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateLeft(x->parent);
                w = x->parent->right;
            }

            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rotateRight(w);
                    w = x->parent->right;
                }

                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                rotateLeft(x->parent);
                x = root;
            }
        } else {
            Node *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateRight(x->parent);
                w = x->parent->left;
            }

            if (w->right->color == BLACK && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    rotateLeft(w);
                    w = x->parent->left;
                }

                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rotateRight(x->parent);
                x = root;
            }
        }
    }
    x->color = BLACK;
}

Node* RedBlackTree::minValueNode(Node* node) {
    Node* current = node;
    while (current->left != nullptr)
        current = current->left;

    return current;
}

void RedBlackTree::deleteNodeHelper(Node* root, int data) {
    Node *z = nullptr;
    Node *x, *y;
    while (root != nullptr) {
        if (root->data == data)
            z = root;

        if (root->data <= data)
            root = root->right;
        else
            root = root->left;
    }

    if (z == nullptr)
        return;

    y = z;
    Color y_original_color = y->color;
    if (z->left == nullptr) {
        x = z->right;
        if (x != nullptr)
            x->parent = z->parent;

        if (z->parent == nullptr)
            root = x;
        else if (z == z->parent->left)
            z->parent->left = x;
        else
            z->parent->right = x;
        delete z;
    } else if (z->right == nullptr) {
        x = z->left;
        if (x != nullptr)
            x->parent = z->parent;

        if (z->parent == nullptr)
            root = x;
        else if (z == z->parent->left)
            z->parent->left = x;
        else
            z->parent->right = x;
        delete z;
    } else {
        y = minValueNode(z->right);
        y_original_color = y->color;
        x = y->right;

        if (y->parent == z) {
            if (x != nullptr)
                x->parent = y;
        } else {
            if (x != nullptr)
                x->parent = y->parent;
            y->parent->left = x;
            y->right = z->right;
            if (y->right != nullptr)
                y->right->parent = y;
        }

        if (z->parent == nullptr)
            root = y;
        else if (z == z->parent->left)
            z->parent->left = y;
        else
            z->parent->right = y;

        y->parent = z->parent;
        y->color = z->color;
        y->left = z->left;
        if (y->left != nullptr)
            y->left->parent = y;

        delete z;
    }

    if (y_original_color == BLACK)
        fixDelete(x);
}

void RedBlackTree::deleteNode(int data) {
    deleteNodeHelper(root, data);
}

Node* RedBlackTree::search(int data) {
    Node* current = root;
    while (current != nullptr

) {
        if (current->data == data)
            return current;
        else if (data < current->data)
            current = current->left;
        else
            current = current->right;
    }
    return nullptr;
}

int RedBlackTree::extractMin() {
    if (root == nullptr)
        return -1;

    Node* minNode = minValueNode(root);
    int minValue = minNode->data;
    deleteNode(minValue);
    return minValue;
}

void RedBlackTree::inorderHelper(Node *node) const {
    if (node == nullptr)
        return;

    inorderHelper(node->left);
    cout << node->data << " ";
    inorderHelper(node->right);
}

void RedBlackTree::inorder() const {
    inorderHelper(root);
}

void RedBlackTree::levelOrderHelper(Node *node) const {
    if (node == nullptr)
        return;

    queue<Node *> q;
    q.push(node);

    while (!q.empty()) {
        Node *temp = q.front();
        cout << temp->data << " ";
        q.pop();

        if (temp->left != nullptr)
            q.push(temp->left);

        if (temp->right != nullptr)
            q.push(temp->right);
    }
}

void RedBlackTree::levelOrder() const {
    levelOrderHelper(root);
}

int main() {
    RedBlackTree tree;

    tree.insert(7);
    tree.insert(3);
    tree.insert(18);
    tree.insert(10);
    tree.insert(22);
    tree.insert(8);
    tree.insert(11);
    tree.insert(26);

    cout << "Inorder traversal of the tree:\n";
    tree.inorder();
    cout << "\nLevel order traversal of the tree:\n";
    tree.levelOrder();

    cout << "\n\nAfter deleting 18, 11, and 3:\n";
    tree.deleteNode(18);
    tree.deleteNode(11);
    tree.deleteNode(3);

    cout << "Inorder traversal of the modified tree:\n";
    tree.inorder();
    cout << "\nLevel order traversal of the modified tree:\n";
    tree.levelOrder();

    cout << "\n\nSearch for 10: ";
    Node* searchResult = tree.search(10);
    if (searchResult != nullptr)
        cout << "Found\n";
    else
        cout << "Not Found\n";

    cout << "\nExtracting minimum: " << tree.extractMin() << endl;

    cout << "Inorder traversal after extracting min:\n";
    tree.inorder();
    cout << endl;

    return 0;
}

使用示例及实例测试步骤

  • 插入元素：向树中插入多个整数，如7, 3, 18, 10, 22, 8, 11, 26。
  • 删除元素：删除某些特定的元素，如18, 11, 3。
  • 查找元素：查找特定的元素，如10。
  • 取出最小值：提取树中的最小值，并在提取后查看树的结构。
  • 遍历：通过中序遍历（Inorder）和层序遍历（Level Order）来查看树的结构。

实例测试结果

Inorder traversal of the tree:
3 7 8 10 11 18 22 26 
Level order traversal of the tree:
7 3 18 8 22 10 26 11 

After deleting 18, 11, and 3:
Inorder traversal of the modified tree:
7 8 10 22 26 
Level order traversal of the modified tree:
7 8 22 10 26 

Search for 10: Found

Extracting minimum: 7
Inorder traversal after extracting min:
8 10 22 26

代码解析

  1. 节点结构：Node结构体包含数据、颜色以及指向左右子节点和父节点的指针。节点颜色用于维持红黑树的平衡。

  2. 插入操作：insert方法在插入节点后，通过fixInsert方法进行必要的旋转和重新着色，确保红黑树的性质不被破坏。

  3. 删除操作：deleteNode方法删除节点后，通过fixDelete方法进行旋转和重新着色，以恢复红黑树的平衡。

  4. 查找操作：search方法遍历树以查找特定的值。

  5. 取出最小值：extractMin方法找到最小的节点并将其删除。

  6. 遍历：中序遍历用于输出树中的元素，层序遍历用于展示树的层次结构。

红黑树与其他数据结构的优势

  • 与普通二叉查找树（BST）相比：红黑树通过自平衡机制，确保了最坏情况下的时间复杂度为O(log n)，而普通的二叉查找树在最坏情况下的时间复杂度可能退化为O(n)。

  • 与AVL树相比：红黑树在插入和删除时的旋转次数比AVL树更少，因此在插入和删除操作较频繁的情况下，红黑树的性能往往优于AVL树。

  • 与哈希表相比：虽然哈希表的查找、插入和删除操作的平均时间复杂度为O(1)，但红黑树维护了元素的有序性，适合需要有序遍历元素的场景。

标签：Node,right,pt,parent,示例,color,入门教程,红黑树,left
From： https://blog.csdn.net/weixin_44251074/article/details/141353991

相关文章

  • Docker 入门教程
    本文是官方GettingStarts教程的阅读笔记，包含对步骤、命令的记录和解释。教程分一系列课程，包括有：安装Docker运行容器和创建自定义容器创建高效可复用的镜像，并推送到DockerHub上GetDockerDesktopDockerDesktop是简单易用的Docker工具软件，使用DockerDesktop可......
  • TopoJSON格式详解，写入读取TopoJSON示例
    还是大剑师兰特：曾是美国某知名大学计算机专业研究生，现为航空航海领域高级前端工程师；CSDN知名博主，GIS领域优质创作者，深耕openlayers、leaflet、mapbox、cesium，canvas，webgl，echarts等技术开发，欢迎加底部微信（gis-dajianshi），一起交流。No.内容链接1Openlayers【入门教程】-......
  • 多重示例详细说明Eureka原理实践
    Eureka原理（EurekaPrinciple）是指在长时间的思考和积累之后，通过偶然的瞬间获得灵感或发现解决问题的方法的一种认知现象。这个过程通常包括三个主要阶段：准备阶段、潜伏期以及突然的灵感爆发。下面详细说明Eureka原理的实践步骤：1.准备阶段广泛阅读与研究：在这个阶段，研究者需......
  • AES常用的代码示例
    AESAES是对称加密。对称加密是指加密和解密使用相同的密钥的加密算法。非对称加密是指加密和解密使用不同的密钥的加密算法。AES加密解密加密模式，有ECB模式和CBC模式等等，ECB不需要iv偏移量，而CBC需要。密钥，可以自定义。填充方式，有PKCS5、PKCS7、NoPadding。......
  • RabbitMQ消息队列：概念、单节点和集群示例
    目录消息队列概念主流的消息队列消息队列名词（1）Broker（2）Topic（3）Producer（4）Consumer（5）Queue（6）Message消息队列中两种工作模式Point-to-Point（PTP、点到点）Pub/Sub消息队列的缺点系统可用性降低系统复杂性提高数据一致性无法保证RabbitMQ相关术语（1）生产者（2）消费者（3）队......
  • axios取消请求CancelToken的原理解析及用法示例
    文章目录一、axios的实例与请求流程二、CancelToken的作用三、CancelToken的实现原理四、取消请求的流程五、CancelToken用法六、利用拦截器取消请求1、axios请求拦截器2、axios响应拦截器3、利用路由导航守卫取消请求一、axios的实例与请求流程下图是axios实例......
  • python入门教程（非常详细！3w+ 文字）
    先序:学习编程语言要先学个轮廓，刚开始只用学核心的部分，一些细节、不常用的内容先放着，现用现查即可；把常用的东西弄熟练了在慢慢补充。1、安装Python解释器为什么需要安装PythonPython语言本身是由解释器执行的，因此你需要在你的计算机上安装Python解释器。这个解释器会将......
  • java 入门教程（非常详细！1.6w+ 文字）
    先序:学习编程语言要先学个轮廓，刚开始只用学核心的部分，一些细节、不常用的内容先放着，现用现查即可；把常用的东西弄熟练了在慢慢补充。1.Java概述Java是一种面向对象的编程语言，由SunMicrosystems（现在的Oracle）在1995年推出。Java程序可以在任何支持Java虚拟机(JVM)的......
  • python入门教程（非常详细！3w+ 文字）
    先序:学习编程语言要先学个轮廓，刚开始只用学核心的部分，一些细节、不常用的内容先放着，现用现查即可；把常用的东西弄熟练了在慢慢补充。1、安装Python解释器为什么需要安装PythonPython语言本身是由解释器执行的，因此你需要在你的计算机上安装Python解释器。这个解释......
  • 红黑树
    红黑树1=》2=》3不平衡二叉树-左旋1=》2=》3不平衡二叉树-右旋3=》2=》1平衡二叉树-变色10=》8=》20=》4=》9=》15=》28=》20......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99