C++红黑树的底层原理及其实现

C++红黑树的底层原理及其实现

引用

CSDN

1.

https://blog.csdn.net/2302_80214413/article/details/141818478

红黑树是一种自平衡二叉查找树，在C++标准库的set和map容器中被广泛应用。本文将详细介绍红黑树的底层原理、实现原理以及具体的代码实现，帮助读者深入理解这一重要的数据结构。

一、红黑树的底层原理

红黑树是一种自平衡二叉查找树，它通过在每个节点上增加一个存储位来表示节点的颜色，从而在插入和删除操作时保持树的平衡。红黑树需要满足以下五个性质：

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

二、红黑树的实现原理

红黑树的实现过程与搜索二叉树类似，主要区别在于插入过程中的调整。每次插入一个红色节点，但要保证根节点是黑色的。如果插入过程中遇到连续的红色节点，需要进行调整，以保持红黑树的特性。

三、红黑树的实现

1. 基础结构

在红黑树的实现过程中，相对于搜索二叉树，我们加入了节点的颜色和父节点的指针。以下是红黑树节点的结构定义：

enum Color {
    RED,
    BLACK
};

template<class T1, class T2>
struct RBTreeNode {
    pair<T1, T2> _data;
    struct RBTreeNode<T1, T2>* _left;
    struct RBTreeNode<T1, T2>* _right;
    struct RBTreeNode<T1, T2>* _parent;
    int col;

    RBTreeNode(const pair<T1, T2>& data)
        : _data(data)
        , _left(nullptr)
        , _right(nullptr)
        , col(RED)
        , _parent(nullptr)
    {}
};

2. 插入过程

插入过程是红黑树实现中最重要的一部分。在插入新节点后，需要检查并调整树的结构，以保持红黑树的特性。以下是插入操作的代码实现：

bool Insert(const pair<T1, T2>& x) {
    if (_root == nullptr) {
        _root = new Node(x);
        _root->col = BLACK;
        return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur) {
        if (cur->_data.first < x.first) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_data.first > x.first) {
            parent = cur;
            cur = cur->_left;
        } else {
            return false;
        }
    }
    if (parent->_left == cur && parent->_data.first > x.first) {
        parent->_left = new Node(x);
        parent->_left->_parent = parent;
        cur = parent->_left;
    } else {
        parent->_right = new Node(x);
        parent->_right->_parent = parent;
        cur = parent->_right;
    }
    while (parent && parent->col == RED) {
        Node* grandfather = parent->_parent;
        Node* uncle = nullptr;
        if (grandfather->_left == parent)
            uncle = grandfather->_right;
        else
            uncle = grandfather->_left;
        if (uncle && uncle->col == RED) {
            parent->col = uncle->col = BLACK;
            grandfather->col = RED;
            cur = grandfather;
            parent = cur->_parent;
        } else if ((uncle && uncle->col == BLACK) || uncle == nullptr) {
            if (grandfather->_left == parent && parent->_left == cur) {
                RotateR(grandfather);
                parent->col = BLACK;
                grandfather->col = RED;
                break;
            } else if (grandfather->_right == parent && parent->_right == cur) {
                RotateL(grandfather);
                parent->col = BLACK;
                grandfather->col = RED;
                break;
            } else if (grandfather->_left == parent && parent->_right == cur) {
                RotateL(parent);
                parent = grandfather->_left;
                cur = parent->_left;
            } else if (grandfather->_right == parent && parent->_left == cur) {
                RotateR(parent);
                parent = grandfather->_right;
                cur = parent->_right;
            } else
                assert(false);
        } else
            assert(false);
        _root->col = BLACK;
    }
    return true;
}

3. 销毁和遍历

红黑树的销毁和遍历与搜索二叉树类似，以下是相关代码实现：

void InOrder() {
    Node* cur = _root;
    _InOrder(cur);
    cout << endl;
}

void _InOrder(Node* root) {
    if (root == nullptr)
        return;
    _InOrder(root->_left);
    cout << root->_data.first << ":" << root->_data.second << endl;
    _InOrder(root->_right);
}

~RBTree() {
    _RBTreeDestory(_root);
    _root = nullptr;
}

void _RBTreeDestory(Node* root) {
    if (root == nullptr)
        return;
    _RBTreeDestory(root->_left);
    _RBTreeDestory(root->_right);
    delete root;
}

4. 验证红黑树的特性

为了验证红黑树是否满足其特性，可以使用以下代码进行检查：

bool IsRBTree() {
    Node* root = _root;
    if (_root->col == RED)
        return false;
    int BKNum = 0;
    while (root) {
        if (root->col == BLACK)
            BKNum++;
        root = root->_left;
    }
    return __IsRBTree(_root, BKNum);
}

bool __IsRBTree(Node* root, int k) {
    if (root == nullptr)
        return k == 0;
    if (root->col == BLACK)
        k--;
    if (root->col == RED) {
        if (root->_parent->col == RED)
            return false;
    }
    __IsRBTree(root->_left, k);
    __IsRBTree(root->_right, k);
}

通过以上步骤，我们可以实现一个完整的红黑树数据结构。希望本文能帮助读者深入理解红黑树的原理和实现细节。