devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【C++】【二叉树】【红黑树】构建RB tree、红黑树 类_c++二叉树和红黑树

作者：笔触狂放9 | 2024-03-16 02:05:21

赞

踩

c++二叉树和红黑树

文章目录

前言

1、红黑树定义

○ 每个节点或是红色，或是黑色。
○ 根节点是黑色。
○ 每个叶子节点（最后的空节点，和以前的叶子节点概念不一样）是黑色的。
○ 红色节点的孩子是黑色的。 任意节点到叶子节点，经过的黑色节点数是一样的。

2、红黑树性能

完全随机的数据，二分搜索树就很好用了。极端情况会退化成链表。

红黑树：添加删除查询都是2logn。翻转更少，相对来说添加比AVL要快。

红黑树：树高2logn，牺牲了一定的平衡性；但是统计性能更优（增删改查所有操作），即平均性能。

只查询的话，AVL更好；红黑树更均衡。

3、红黑树特点

红黑树的各种东西太琐碎了，都是总结起来，梳理成的逻辑。看红黑树之前最好看一下2-3树。

红黑树的删除节点比添加节点还要复杂，更深入了解，再来填坑。

这里讨论的都是左倾红黑树。

一、重点解析

1、插入规则

1、1、插入节点旁没有红色节点：

  1. 插入的元素在黑节点的左侧，直接添加即可；

  2. 插入的元素在黑节点的右侧，将其左旋转，新根节点颜色继承，新孩子节点颜色变红色。

1、2、插入节点周围有红色节点：

  1. 插入的元素的父节点是黑色，父节点另一个孩子是红色。直接颜色翻转即可（对应于2-3树中，3-节点插入作为临时4-节点，再分裂成为三个2-节点。然后根节点变红，继续往上融合）

  2. 插入的节点是黑节点的红节点的孩子位置，需要右旋转后反转颜色。

  3. 插入的节点是红色节点的右边。只需要先左旋转，就变成了上面的情况。

以下就是三种复杂的插入时候的情况。

即每次插入完总是下面三种情况，只需要判断是否需要左旋转、再判断是否需要右旋转、再判断是否需要颜色反转即可。

对于1.1中，插入红节点为左倾，直接不用管；插入红节点要右倾，就左旋转。即可塞入下图第二个节点的模样中。

在这里插入图片描述

所有的案例的逻辑为：

右孩子是红，左孩子不是红            ->左旋转
左孩子是红，左孩子的左孩子是红       ->左旋转
右孩子是红，左孩子是红              ->颜色翻转

  • 1
  • 2
  • 3

2、左旋转、右旋转

在这里插入图片描述

//   node                     x
//  /   \     左旋转         /  \
// T1   x   --------->   node   T3
//     / \              /   \
//    T2 T3            T1   T2

  • 1
  • 2
  • 3
  • 4
  • 5

在这里插入图片描述

//     node                   x
//    /   \     右旋转       /  \
//   x    T2   ------->   y   node
//  / \                       /  \
// y  T1                     T1  T2

  • 1
  • 2
  • 3
  • 4
  • 5

3、颜色翻转

在这里插入图片描述

4、插入节点

相对于BST，插入节点加入了：

  1. 对当前节点的高度计算；
  2. 对平衡因子的计算（左右子树的高度计算）；
  3. 根据平衡性，分四种情况进行左旋右旋->以恢复平衡。
// 向以node为根的二叉搜索树中,插入节点(key, value)
// 返回插入新节点后的二叉搜索树的根
Node *add(Node *node, Key key, Value value) {
    if (node == nullptr) {
        size++;
        return new Node(key, value);
    }
    if (key == node->key) {
        node->value = value;
    } else if (key < node->key) {
        node->left = add(node->left, key, value);
    } else {
        node->right = add(node->right, key, value);
    }
    node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
    int balanceFactor = getBalanceFactor(node);

    if (balanceFactor > 1 && getBalanceFactor(node->left) >= 0) {
        return rightRotate(node);
    }

    if (balanceFactor < -1 && getBalanceFactor(node->right) <= 0) {
        return leftRotate(node);
    }

    if (balanceFactor > 1 && getBalanceFactor(node->left) < 0) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if (balanceFactor < -1 && getBalanceFactor(node->right) > 0) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

5、析构函数

析构函数，需要用到后序遍历的思想。

即，删除当前节点，得先将其左右子树都删除掉，否则无法删除整个树。

下面代码，其实就是后序遍历的递归形式的析构函数。

    // 析构函数, 释放二分搜索树的所有空间
    ~BST(){
        destroy( root );
    }

    // 释放以node为根的二分搜索树的所有节点
    // 采用后续遍历的递归算法
    void destroy(Node* node){

        if( node != NULL ){
            destroy( node->left );
            destroy( node->right );

            delete node;
            count --;
        }
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

二、完整红黑树类

完整代码取自bobo老师及相关同学的github，文末有路径。


template<typename Key, typename Value>
class RBTree {
private:
    static const bool RED = true;
    static const bool BLACK = false;

    struct Node {
        Key key;
        Value value;
        Node *left;
        Node *right;
        bool color;

        Node(Key key, Value value) {
            this->key = key;
            this->value = value;
            this->left = this->right = nullptr;
            color = RED;
        }

        Node(Node *node) {
            this->key = node->key;
            this->value = node->value;
            this->left = node->left;
            this->right = node->right;
            this->color = node->color;
        }
    };

    Node *root;
    int size;

public:

    RBTree() {
        root = nullptr;
        size = 0;
    }

    ~RBTree() {
        destroy(root);
    }

    int getSize() {
        return size;
    }

    int isEmpty() {
        return size == 0;
    }

    bool isRed(Node *node) {
        if (node == nullptr) {
            return BLACK;
        }
        return node->color;
    }

    void add(Key key, Value value) {
        root = add(root, key, value);
        root->color = BLACK;
    }

    bool contains(Key key) {
        return getNode(root, key) != nullptr;
    }

    Value *get(Key key) {
        Node *node = getNode(root, key);
        return node == nullptr ? nullptr : &(node->value);
    }

    void set(Key key, Value newValue) {
        Node *node = getNode(root, key);
        if (node != nullptr) {
            node->value = newValue;
        }
    }

private:

    // 向以node为根的二叉搜索树中,插入节点(key, value)
    // 返回插入新节点后的二叉搜索树的根
    Node *add(Node *node, Key key, Value value) {
        if (node == nullptr) {
            size++;
            return new Node(key, value);
        }
        if (key == node->key) {
            node->value = value;
        } else if (key < node->key) {
            node->left = add(node->left, key, value);
        } else {
            node->right = add(node->right, key, value);
        }

        if (isRed(node->right) && !isRed(node->left)) {
            node = leftRotate(node);
        }

        if (isRed(node->left) && isRed(node->left->left)) {
            node = rightRotate(node);
        }

        if (isRed(node->left) && isRed(node->right)) {
            flipColors(node);
        }
        return node;
    }

    // 在以node为根的二叉搜索树中查找key所对应的Node
    Node *getNode(Node *node, Key key) {
        if (node == nullptr) {
            return nullptr;
        }
        if (key == node->key) {
            return node;
        } else if (key < node->key) {
            return getNode(node->left, key);
        } else {
            return getNode(node->right, key);
        }
    }

    void destroy(Node *node) {
        if (node != nullptr) {
            destroy(node->left);
            destroy(node->right);
            delete node;
            size--;
        }
    }

    Node *leftRotate(Node *node) {
        Node *x = node->right;
        node->right = x->left;
        x->left = node;

        x->color = node->color;
        node->color = RED;

        return x;
    }

    Node *rightRotate(Node *node) {
        Node *x = node->left;
        node->left = x->right;
        x->right = node;

        x->color = node->color;
        node->color = RED;

        return x;
    }

    void flipColors(Node *node) {
        node->color = RED;
        node->left->color = BLACK;
        node->right->color = BLACK;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162

参考

模板类、模板函数设计

二叉搜索树 实现

AVL树 实现

bobo老师github

houpengfei的github

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/246251
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号