2-3 树

基本性质

  1. 满足二分搜索树的基本性质；
  2. 节点可以存放一个元素或者两个元素；

在某种意义上，红黑树其实可以等价于 2-3 数，只不过红黑树的节点只放了一个元素，用红黑颜色表示了是否属于同一个节点

红黑树

基本性质

  1. 每个节点或者是红色，或者是黑色
  2. 根节点是黑色
  3. 每个叶子节点（最后的空节点）是黑色
  4. 如果一个节点是红色的，那么他的孩子节点都是黑色
  5. 从任意一个节点到叶子节点，经过的黑色节点是一样的

旋转解决平衡问题

红黑树添加或者删除节点都会经过以下几种结构类型，只需要判断当前结构满足类型，直接进行后续的步骤即可。

1
2
3
4
5
6
7
/*
 *       X(B)                   X(B)                   X(B)
 *      /                      /                      /                     Z(B)                     Z(R)
 *    Y(R)    == 添加元素 =>   Y(R)     == 左旋转 =>   Z(R)    == 右旋转 =>   /    \    == 颜色翻转 =>   /   \
 *                             \                   /                     Y(R)   X(R)              Y(B)   X(B) 
 *                              Z(R)             Y(R)
 */

颜色翻转解释

因为颜色翻转后，根节点需要跟父节点融合，所以需要将根节点变成红色，如果是 root 节点，会在操作结束之后更改为黑色。

代码

修改部分

  1. 基于之前的二分搜索树代码，删除父节点信息（因为后面检查代码的时候发现根本没用上）；
  2. 使用 C++ 特有的智能指针 share_ptr，没用上 weak_ptr 和 unique_ptr，这个智能指针用的我头皮发麻，第一次用踩了很多坑，会在下一篇笔记中进行记录；
  3. 使用了 C++ 的属性 [[nodiscard]]；
  4. 形参使用引用避免复制，使用 C++ 的 const 关键字对部分函数进行优化；
  5. 禁止使用复制构造函数和拷贝赋值；

红黑树类定义

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
//
// Created by Tianyi on 2021/12/20.
//

#ifndef BLACK_RED_TREE_TREE_DEFINE_H
#define BLACK_RED_TREE_TREE_DEFINE_H

#include <iostream>
#include <memory>

#endif //BLACK_RED_TREE_TREE_DEFINE_H

using namespace std;

/**
 * 红黑树节点类
 */
class RBTNode final {
public:
    static const bool RED = true;
    static const bool BLACK = false;

    using this_type = RBTNode;
    using node_type = std::shared_ptr<this_type>;

private:
    bool color;
    int value;

    node_type left_node;
    node_type right_node;

public:
    // 禁止空值构造
    RBTNode() = delete;

    // 禁止复制构造
    RBTNode(const node_type&) = delete;

    // 禁止拷贝赋值
    RBTNode operator=(const node_type&) = delete;

    // 使用默认析构函数
    ~RBTNode() = default;

    // 显示转换的单参构造函数
    explicit RBTNode(int);

    // value setter
    void setValue(int);

    // value getter
    [[nodiscard]] int getValue() const;

    // color setter
    void setColor(bool);

    // color getter
    [[nodiscard]] bool getColor() const;

    // 判断节点是否为红
    [[nodiscard]] bool isRed() const;

    // color changer
    void changeColor();

    // left_node setter
    void setLeft(const node_type&);

    // left_node getter
    [[nodiscard]] RBTNode::node_type getLeft() const;

    // right_node setter
    void setRight(const node_type&);

    // right_node getter
    [[nodiscard]] RBTNode::node_type getRight() const;
};


/**
 * 红黑树
 */
class RBT {
public:
    using node_type = RBTNode::node_type;
private:

    int count;
    node_type root;

    node_type add(node_type, const int &);

    // 查找数据节点
    [[nodiscard]] node_type getNode(const node_type &node, const int &value) const;

    // 删除最小数据节点
    node_type removeMinimum(node_type);

    node_type remove(node_type node, const int &value);

    // 最小数据节点
    node_type minimum(const node_type &);

    void preorderShow(const node_type &) const;

    void inorderShow(const node_type &) const;

    void postorderShow(const node_type &) const;

    // 节点左旋转
    static node_type leftRotate(node_type &);

    // 节点右旋转
    static node_type rightRotate(node_type &);

    // 颜色翻转
    static void flipColors(node_type &);

public:
    // 禁止拷贝构造
    RBT(const RBT &) = delete;

    // 禁止拷贝赋值
    RBT operator=(const RBT &) = delete;

    // 使用默认的析构函数
    ~RBT() = default;

    // 构造函数
    RBT();

    // 判空
    [[nodiscard]] bool isEmpty() const;

    // count getter
    [[nodiscard]] int getCount() const;

    // get root num
    [[nodiscard]] int getRoot() const;

    // 添加数据节点
    void add(const int &);

    // 检查节点是否存在
    bool contains(const int &);

    // 删除数据节点
    int remove(const int &);

    int minimum();

    // 前序遍历
    void preorderShow() const;

    // 中序遍历
    void inorderShow() const;

    // 后序遍历
    void postorderShow() const;
};

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//
// Created by Tianyi on 2021/12/21.
//
#include <utility>

#include "../header/tree_define.h"

RBTNode::RBTNode(const int v) {
    this->value = v;
    this->color = RBTNode::RED;
    this->left_node = nullptr;
    this->right_node = nullptr;
}

void RBTNode::setValue(const int v) {
    this->value = v;
}

int RBTNode::getValue() const {
    return this->value;
}

void RBTNode::setColor(const bool c) {
    this->color = c;
}

bool RBTNode::getColor() const {
    return this->color;
}

bool RBTNode::isRed() const {
    return this->color;
}

void RBTNode::changeColor() {
    this->color = !this->color;
}

void RBTNode::setLeft(const node_shared_type& node) {
    this->left_node = node;
}

RBTNode::node_shared_type RBTNode::getLeft() const {
    return this->left_node;
}

void RBTNode::setRight(const node_shared_type& node) {
    this->right_node = node;
}

RBTNode::node_shared_type RBTNode::getRight() const {
    return this->right_node;
}

tree 操作

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
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
//
// Created by Tianyi on 2021/12/21.
//
#include "../header/tree_define.h"

using node_type = RBTNode::node_type;

RBT::RBT() {
    this->count = 0;
}

bool RBT::isEmpty() const {
    return this->count > 0;
}

int RBT::getCount() const {
    return this->count;
}

int RBT::getRoot() const {
    return this->root->getValue();
}

/**
 * 节点左旋转
 * @param node
 * @return
 */
node_type RBT::leftRotate(node_type &node) {

    auto rightN = node->getRight();

    // 旋转节点
    node->setRight(rightN->getLeft());
    rightN->setLeft(node);

    // 改变节点颜色
    rightN->setColor(node->getColor());
    node->setColor(RBTNode::RED);

    return rightN;
}

/**
 * 右旋转
 * @param node
 * @return
 */
node_type RBT::rightRotate(node_type &node) {

    auto leftN = node->getLeft();

    // 旋转节点
    node->setLeft(leftN->getRight());
    leftN->setRight(node);

    // 改变节点颜色
    leftN->setColor(node->getColor());
    // 这里有点特殊
    // 因为右旋转后，node 和 leftN 可能会组成一个 4 孩子节点
    // 所以需要将 node 的颜色改成 RED
    node->setColor(RBTNode::RED);

    return leftN;
}

/**
 * 颜色翻转
 * @param node
 */
void RBT::flipColors(node_type &node) {
    node->setColor(RBTNode::RED);

    if (node->getLeft() != nullptr) {
        node->getLeft()->setColor(RBTNode::BLACK);
    }

    if (node->getRight() != nullptr) {
        node->getRight()->setColor(RBTNode::BLACK);
    }
}

/**
 * 向红黑树中添加新的元素
 * @param value
 */
void RBT::add(const int &value) {
    this->root = add(this->root, value);
    this->root->changeColor();
}

/**
 * 以 node 为根的红黑树插入元素
 * 返回插入新节点后红黑树的根
 * @param node
 * @param value
 * @return
 */
node_type RBT::add(node_type node, const int &value) {
    if (node == nullptr) {
        this->count++;
        return std::make_shared<RBTNode>(value);
    }

    if (value < node->getValue()) {
        node->setLeft(add(node->getLeft(), value));
    } else if (value > node->getValue()) {
        node->setRight(add(node->getRight(), value));
    } else {
        node->setValue(value);
    }

    if (node->getRight() != nullptr && node->getRight()->isRed()) {
        node = this->leftRotate(node);
    }

    if (node->getLeft() != nullptr && node->getLeft()->getLeft() != nullptr && node->getLeft()->getLeft()->isRed()) {
        node = this->rightRotate(node);
    }

    if (node->getLeft() != nullptr && node->getRight() != nullptr && node->getRight()->isRed() &&
        node->getLeft()->isRed()) {
        this->flipColors(node);
    }

    return node;
}

/**
 * 判断某节点是否存在
 * @param value
 * @return
 */
bool RBT::contains(const int &value) {
    auto retNode = getNode(this->root, value);

    return retNode != nullptr;
}

/**
 * 从二叉搜索树中删除某个节点
 * @param value
 */
int RBT::remove(const int &value) {
    if (this->contains(value)) {
        this->root = remove(this->root, value);
        this->root->setColor(RBTNode::BLACK);
        return value;
    }
    return INT_MIN;
}

/**
 * 递归查找删除节点并删除
 * @param node
 * @param value
 * @return
 */
node_type RBT::remove(node_type node, const int &value) {
    if (node == nullptr) {
        return nullptr;
    }

    auto retNode = node;

    if (value < node->getValue()) {
        node->setLeft(this->remove(node->getLeft(), value));
        return node;
    } else if (value > node->getValue()) {
        node->setRight(this->remove(node->getRight(), value));
        return node;
    } else {

        if (node->getLeft() == nullptr) {
            // 如果待删除节点左子树为空， 则嫁接右子树
            auto rightNode = node->getRight();
            // 删除 node 节点信息
            node->setRight(nullptr);
            node = nullptr;
            // 总数减一
            this->count--;
            retNode = rightNode;
        } else if (node->getRight() == nullptr) {
            // 如果待删除节点右子树为空，则嫁接左子树
            auto leftNode = node->getLeft();
            // 删除 node 节点信息
            node->setLeft(nullptr);
            node = nullptr;
            // 总数减一
            this->count--;
            retNode = leftNode;
        } else {
            // 左右子树都不为空的时候需要进行替换
            auto successor = this->minimum(node->getRight());
            auto successorRight = this->removeMinimum(node->getRight());
            successor->setRight(successorRight);
            successor->setLeft(node->getLeft());
            // 删除 node 节点信息
            node->setLeft(nullptr);
            node->setRight(nullptr);
            node = nullptr;
            // 总数减一
            this->count--;
            retNode = successor;
        }
    }

    if (retNode->getRight() != nullptr && retNode->getRight()->isRed()) {
        retNode = this->leftRotate(retNode);
    }

    if (retNode->getLeft() != nullptr && retNode->getLeft()->getLeft() != nullptr && retNode->getLeft()->getLeft()->isRed()) {
        retNode = this->rightRotate(retNode);
    }

    if (retNode->getLeft() != nullptr && retNode->getRight() != nullptr && retNode->getRight()->isRed() &&
        retNode->getLeft()->isRed()) {
        this->flipColors(retNode);
    }

    return retNode;
}

/**
 * 删除指定节点下的最小节点
 * @return
 */
node_type RBT::removeMinimum(node_type node) {
    if (node->getLeft() == nullptr) {
        auto rightNode = node->getRight();
        node->setRight(nullptr);
        node = nullptr;
        return rightNode;
    }

    node->setLeft(this->removeMinimum(node->getLeft()));
    return node;
}

/**
 * 获取整棵树最小值
 * @return
 */
int RBT::minimum() {
    return this->minimum(this->root)->getValue();
}

/**
 * 获取指定节点下的最小值节点
 * @param node
 * @return
 */
node_type RBT::minimum(const node_type &node) {
    assert(node != nullptr && "该结点为空");

    // 如果当前节点没有左子树，则当前节点就是最小值节点
    if (node->getLeft() == nullptr) {
        return node;
    }

    auto tempNode = node;
    while (tempNode->getLeft() != nullptr) {
        tempNode = tempNode->getLeft();
    }

    return tempNode;
}

/**
 * 根据值获取指定节点
 * @param node
 * @param value
 * @return
 */
node_type RBT::getNode(const node_type &node, const int &value) const {
    // 判断智能指针是否失效
    if (node == nullptr) {
        return node;
    }

    if (value == node->getValue()) {
        return node;
    } else if (value > node->getValue()) {
        return getNode(node->getRight(), value);
    } else {
        return getNode(node->getLeft(), value);
    }
}

/**
 * 前序遍历
 */
void RBT::preorderShow() const {
    preorderShow(this->root);
    cout << endl;
}

/**
 * 递归前序遍历
 * @param node
 */
void RBT::preorderShow(const node_type &node) const {
    // 该结点内存已经被系统回收，expired 函数判断该智能指针失效
    if (node == nullptr) {
        return;
    }

    std::cout << node->getValue() << " - ";
    preorderShow(node->getLeft());
    preorderShow(node->getRight());
}

/**
 * 中序遍历
 */
void RBT::inorderShow() const {
    inorderShow(this->root);
    cout << endl;
}

/**
 * 递归中序遍历
 * @param node
 */
void RBT::inorderShow(const node_type &node) const {
    if (node == nullptr) {
        return;
    }

    inorderShow(node->getLeft());
    std::cout << node->getValue() << " - ";
    inorderShow(node->getRight());
}

/**
 * 后序遍历
 */
void RBT::postorderShow() const {
    postorderShow(this->root);
    cout << endl;
}

/**
 * 递归后序遍历
 * @param node
 */
void RBT::postorderShow(const node_type &node) const {
    if (node == nullptr) {
        return;
    }

    postorderShow(node->getLeft());
    postorderShow(node->getRight());
    std::cout << node->getValue() << " - ";
}

测试代码

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
#include "./header/tree_define.h"

int main() {
    auto rbt = make_unique<RBT>();
    rbt->add(9);
    rbt->add(5);
    rbt->add(2);
    rbt->add(4);
    rbt->add(1);
    rbt->add(3);
    rbt->add(7);
    rbt->add(6);
    rbt->add(8);
    rbt->add(15);
    rbt->add(10);
    rbt->add(13);
    rbt->add(14);
    rbt->add(11);
    rbt->add(12);
    rbt->add(16);

    cout << "此时树的容量为 : " << rbt->getCount() << endl;
    rbt->inorderShow();

    cout << "节点是否存在 : " << rbt->contains(7) << endl;
    cout << "整棵树的最小值为 : " << rbt->minimum() << endl;
    cout << "删除节点 : " << rbt->remove(9) << endl;
    cout << "删除节点 : " << rbt->remove(4) << endl;
    cout << "删除节点 : " << rbt->remove(15) << endl;
    cout << "删除节点 : " << rbt->remove(10) << endl;
    cout << "此时的根为 : " << rbt->getRoot() << endl;
    cout << "此时树的容量为 : " << rbt->getCount() << endl;

    rbt->inorderShow();

    return 0;
}

最后哔哔一句

C++ 的智能指针确实好用，相当与一个对象直接操作，还不用自己手动回收，用出了一种 Java 对象的感觉，但是刚开始因为不了解智能指针的特性，踩了一个下午的坑，差点放弃掉，现在算是理解了，也准备搞一篇笔记记一下，这玩意还是挺好玩的，特别是 weak_ptr 和 share_ptr 这俩倒霉玩意儿，理解用法就挺难得了。