行业资讯

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

发布时间：2022-08-08 14:13:13 作者：iii
来源：亿速云 阅读：126

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

目录

  1. 引言
  2. 红黑树的基本概念
  3. 红黑树的节点结构
  4. 红黑树的基本操作
  5. 红黑树的实现
  6. 红黑树的应用
  7. 总结

引言

红黑树是一种自平衡的二叉查找树，它在计算机科学中有着广泛的应用。红黑树通过引入颜色属性来维护树的平衡，从而保证了在最坏情况下基本操作的时间复杂度为O(log n)。本文将详细介绍红黑树的基本概念、性质、节点结构、基本操作及其在C++中的实现。

红黑树的基本概念

2.1 红黑树的定义

红黑树是一种二叉查找树，每个节点都带有一个额外的存储位表示节点的颜色，可以是红色或黑色。通过对任何一条从根到叶子的路径上各个节点着色方式的限制，红黑树确保没有一条路径会比其他路径长出两倍，因而是接近平衡的。

2.2 红黑树的性质

红黑树具有以下性质：

  1. 每个节点是红色或黑色。
  2. 根节点是黑色。
  3. 每个叶子节点（NIL节点，空节点）是黑色。
  4. 如果一个节点是红色的，则它的两个子节点都是黑色的（即没有两个连续的红色节点）。
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些性质确保了红黑树的平衡性，使得红黑树在最坏情况下也能保持O(log n)的时间复杂度。

红黑树的节点结构

红黑树的节点结构通常包含以下信息：

在C++中，红黑树的节点结构可以定义如下：

enum Color { RED, BLACK };

struct Node {
    int key;
    Color color;
    Node* left;
    Node* right;
    Node* parent;

    Node(int key, Color color = RED, Node* left = nullptr, Node* right = nullptr, Node* parent = nullptr)
        : key(key), color(color), left(left), right(right), parent(parent) {}
};

红黑树的基本操作

4.1 插入操作

4.1.1 插入节点的基本步骤

红黑树的插入操作与普通二叉查找树的插入操作类似，但在插入后需要进行平衡调整以保持红黑树的性质。插入操作的基本步骤如下：

  1. 按照二叉查找树的插入规则，将新节点插入到树中。
  2. 将新节点的颜色设置为红色。
  3. 如果新节点的父节点是黑色，则插入操作完成。
  4. 如果新节点的父节点是红色，则需要进行平衡调整。

4.1.2 插入后的平衡调整

插入后的平衡调整主要分为以下几种情况：

  1. 情况1：新节点的叔节点是红色

    • 将父节点和叔节点都设置为黑色。
    • 将祖父节点设置为红色。
    • 将祖父节点作为新的当前节点，继续进行调整。

  2. 情况2：新节点的叔节点是黑色，且新节点是父节点的右子节点

    • 以父节点为支点进行左旋。
    • 将父节点作为新的当前节点，继续进行调整。

  3. 情况3：新节点的叔节点是黑色，且新节点是父节点的左子节点

    • 将父节点设置为黑色。
    • 将祖父节点设置为红色。
    • 以祖父节点为支点进行右旋。

4.2 删除操作

4.2.1 删除节点的基本步骤

红黑树的删除操作与普通二叉查找树的删除操作类似，但在删除后需要进行平衡调整以保持红黑树的性质。删除操作的基本步骤如下：

  1. 按照二叉查找树的删除规则，找到要删除的节点。
  2. 如果要删除的节点有两个子节点，则找到其后继节点（即右子树中的最小节点），并将其值复制到要删除的节点中，然后删除后继节点。
  3. 如果要删除的节点只有一个子节点或没有子节点，则直接删除该节点，并将其子节点（如果有）连接到其父节点。
  4. 如果删除的节点是黑色，则需要进行平衡调整。

4.2.2 删除后的平衡调整

删除后的平衡调整主要分为以下几种情况：

  1. 情况1：删除的节点的兄弟节点是红色

    • 将兄弟节点设置为黑色。
    • 将父节点设置为红色。
    • 以父节点为支点进行左旋或右旋。
    • 继续进行调整。

  2. 情况2：删除的节点的兄弟节点是黑色，且兄弟节点的两个子节点都是黑色

    • 将兄弟节点设置为红色。
    • 将父节点作为新的当前节点，继续进行调整。

  3. 情况3：删除的节点的兄弟节点是黑色，且兄弟节点的左子节点是红色，右子节点是黑色

    • 将兄弟节点的左子节点设置为黑色。
    • 将兄弟节点设置为红色。
    • 以兄弟节点为支点进行右旋。
    • 继续进行调整。

  4. 情况4：删除的节点的兄弟节点是黑色，且兄弟节点的右子节点是红色

    • 将兄弟节点的颜色设置为父节点的颜色。
    • 将父节点设置为黑色。
    • 将兄弟节点的右子节点设置为黑色。
    • 以父节点为支点进行左旋。
    • 调整完成。

4.3 查找操作

红黑树的查找操作与普通二叉查找树的查找操作相同。从根节点开始，比较要查找的键值与当前节点的键值：

查找操作的时间复杂度为O(log n)。

红黑树的实现

5.1 节点类的实现

在C++中，红黑树的节点类可以定义如下：

enum Color { RED, BLACK };

struct Node {
    int key;
    Color color;
    Node* left;
    Node* right;
    Node* parent;

    Node(int key, Color color = RED, Node* left = nullptr, Node* right = nullptr, Node* parent = nullptr)
        : key(key), color(color), left(left), right(right), parent(parent) {}
};

5.2 红黑树类的实现

红黑树类的实现主要包括插入、删除和查找操作。以下是红黑树类的定义及其基本操作的实现。

5.2.1 插入操作的实现

class RedBlackTree {
private:
    Node* root;
    Node* nil;

    void leftRotate(Node* x) {
        Node* y = x->right;
        x->right = y->left;
        if (y->left != nil) {
            y->left->parent = x;
        }
        y->parent = x->parent;
        if (x->parent == nil) {
            root = y;
        } else if (x == x->parent->left) {
            x->parent->left = y;
        } else {
            x->parent->right = y;
        }
        y->left = x;
        x->parent = y;
    }

    void rightRotate(Node* y) {
        Node* x = y->left;
        y->left = x->right;
        if (x->right != nil) {
            x->right->parent = y;
        }
        x->parent = y->parent;
        if (y->parent == nil) {
            root = x;
        } else if (y == y->parent->right) {
            y->parent->right = x;
        } else {
            y->parent->left = x;
        }
        x->right = y;
        y->parent = x;
    }

    void insertFixup(Node* z) {
        while (z->parent->color == RED) {
            if (z->parent == z->parent->parent->left) {
                Node* y = z->parent->parent->right;
                if (y->color == RED) {
                    z->parent->color = BLACK;
                    y->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->right) {
                        z = z->parent;
                        leftRotate(z);
                    }
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    rightRotate(z->parent->parent);
                }
            } else {
                Node* y = z->parent->parent->left;
                if (y->color == RED) {
                    z->parent->color = BLACK;
                    y->color = BLACK;
                    z->parent->parent->color = RED;
                    z = z->parent->parent;
                } else {
                    if (z == z->parent->left) {
                        z = z->parent;
                        rightRotate(z);
                    }
                    z->parent->color = BLACK;
                    z->parent->parent->color = RED;
                    leftRotate(z->parent->parent);
                }
            }
        }
        root->color = BLACK;
    }

public:
    RedBlackTree() {
        nil = new Node(0, BLACK);
        root = nil;
    }

    void insert(int key) {
        Node* z = new Node(key);
        Node* y = nil;
        Node* x = root;

        while (x != nil) {
            y = x;
            if (z->key < x->key) {
                x = x->left;
            } else {
                x = x->right;
            }
        }

        z->parent = y;
        if (y == nil) {
            root = z;
        } else if (z->key < y->key) {
            y->left = z;
        } else {
            y->right = z;
        }

        z->left = nil;
        z->right = nil;
        z->color = RED;

        insertFixup(z);
    }
};

5.2.2 删除操作的实现

class RedBlackTree {
private:
    Node* root;
    Node* nil;

    void transplant(Node* u, Node* v) {
        if (u->parent == nil) {
            root = v;
        } else if (u == u->parent->left) {
            u->parent->left = v;
        } else {
            u->parent->right = v;
        }
        v->parent = u->parent;
    }

    void deleteFixup(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;
                    leftRotate(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;
                        rightRotate(w);
                        w = x->parent->right;
                    }
                    w->color = x->parent->color;
                    x->parent->color = BLACK;
                    w->right->color = BLACK;
                    leftRotate(x->parent);
                    x = root;
                }
            } else {
                Node* w = x->parent->left;
                if (w->color == RED) {
                    w->color = BLACK;
                    x->parent->color = RED;
                    rightRotate(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;
                        leftRotate(w);
                        w = x->parent->left;
                    }
                    w->color = x->parent->color;
                    x->parent->color = BLACK;
                    w->left->color = BLACK;
                    rightRotate(x->parent);
                    x = root;
                }
            }
        }
        x->color = BLACK;
    }

public:
    RedBlackTree() {
        nil = new Node(0, BLACK);
        root = nil;
    }

    void deleteNode(Node* z) {
        Node* y = z;
        Node* x;
        Color yOriginalColor = y->color;

        if (z->left == nil) {
            x = z->right;
            transplant(z, z->right);
        } else if (z->right == nil) {
            x = z->left;
            transplant(z, z->left);
        } else {
            y = minimum(z->right);
            yOriginalColor = y->color;
            x = y->right;
            if (y->parent == z) {
                x->parent = y;
            } else {
                transplant(y, y->right);
                y->right = z->right;
                y->right->parent = y;
            }
            transplant(z, y);
            y->left = z->left;
            y->left->parent = y;
            y->color = z->color;
        }

        if (yOriginalColor == BLACK) {
            deleteFixup(x);
        }

        delete z;
    }

    Node* minimum(Node* x) {
        while (x->left != nil) {
            x = x->left;
        }
        return x;
    }
};

5.2.3 查找操作的实现

class RedBlackTree {
private:
    Node* root;
    Node* nil;

public:
    RedBlackTree() {
        nil = new Node(0, BLACK);
        root = nil;
    }

    Node* search(int key) {
        Node* x = root;
        while (x != nil && key != x->key) {
            if (key < x->key) {
                x = x->left;
            } else {
                x = x->right;
            }
        }
        return x;
    }
};

红黑树的应用

红黑树在计算机科学中有着广泛的应用，主要包括以下几个方面：

  1. 关联容器：C++ STL中的std::map和std::set通常使用红黑树作为底层数据结构。
  2. 数据库索引：许多数据库系统使用红黑树来实现索引结构，以提高查询效率。
  3. 内存管理：操作系统中的内存管理模块使用红黑树来管理空闲内存块。
  4. 网络路由：路由器使用红黑树来存储路由表，以快速查找最佳路由路径。

总结

红黑树是一种高效的自平衡二叉查找树，通过引入颜色属性和一系列平衡调整操作，红黑树能够在最坏情况下保持O(log n)的时间复杂度。本文详细介绍了红黑树的基本概念、性质、节点结构、基本操作及其在C++中的实现。红黑树在计算机科学中有着广泛的应用，是数据结构与算法学习中的重要内容。

推荐阅读：
  1. 红黑树之插入
  2. map实现之红黑树

免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。

c++

上一篇：Linux Shell自动交互功能如何实现

下一篇：怎么使用await-to-js源码处理异步任务

相关阅读

您好，登录后才能下订单哦！

密码登录
登录注册
获取短信验证码
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》
产品服务
地区划分
帮助支持
关于我们
行业资讯-文章归档 问答-问答归档
广州亿速云计算有限公司

7*24小时在线电话：400-100-2938

7*24小时在线QQ：800811969

Copyright © Yisu Cloud Ltd. All Rights Reserved. 2018 版权所有
粤ICP备17096448号-1 粤公网安备 44010402001142号