Cpp五条

这个屌丝很懒，什么也没留下！

热门标签

红黑树（RED-BLACK TREE）_红黑树csdn

作者：Cpp五条 | 2024-06-16 11:52:40

踩

红黑树csdn

文章目录

红黑树（RED-BLACK TREE）

红黑树（RED-BLACK TREE）

1、红黑树概念

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，通常用于实现动态集合（如集合、映射等）的数据结构。它在插入、删除等操作后可以通过一系列的旋转和颜色变换来保持其平衡性，从而保证了在最坏情况下的时间复杂度为O(log n)，其中n是树中元素的个数。

红黑树具有以下特性：

每个节点要么是红色，要么是黑色。
根节点是黑色的。
每个叶子节点（NIL节点，即空节点）是黑色的。
如果一个节点是红色的，则它的两个子节点都是黑色的，并且它的双亲结点也是黑的，即不存在两个连续的红色结点。
对于任意节点，从该节点到其子孙节点的所有路径上包含相同数目的黑色节点（即，黑色节点的高度相同）。

总结一下就是（咸鱼老师的结论）：左根右，根叶黑，不红红，黑路同。

这些特性保证了红黑树的关键性质：任意一条从根到叶子的路径的长度不会超过其他路径的两倍长，从而保证了树的平衡性。

红黑树通常用于实现诸如集合、映射等数据结构，例如在C++的STL中的std::map和std::set就是基于红黑树实现的。

2、红黑树的实现

前面一篇博客有写平衡二叉树（AVL树）的实现，这里红黑树的实现和平衡二叉树（AVL树）类似。

2.1、红黑树的结点定义

这里我们将红黑树的结点的值定义为键值对（Key，Value），当然也可以只定义为单值Key。相对于平衡二叉树少了平衡因子，多了颜色。
enum Colour {
    RED,
    BLACK
};

template<class K, class V>
struct RBTreeNode {
    typedef RBTreeNode<K, V> Node;
    Node *_left;
    Node *_right;
    Node *_parent;
    Colour _col;

    pair<K, V> _kv;

    RBTreeNode(const pair<K, V> &kv) : _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _kv(kv) {}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
这里我们默认给新插入的结点的颜色设置为红色。原因是新增的结点如果颜色是黑色，那么一定会导致parent左右子树的黑结点总数不一样，就必须得调整；新增的结点如果颜色是红色，那么parent左右子树的黑结点总数还是一样的吗，如果parent的颜色的黑色，就不用调整！

2.2、红黑树的插入

红黑树的插入可以分为两步：

按二叉搜索树进行插入

之前的二叉搜索树代码：这里将K模型变为了KV模型。

bool Insert(const pair<K, V> &kv) {
        if (_root == nullptr) {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }

        Node *parent = nullptr;
        Node *cur = _root;
        while (cur) {
            if (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false;
            }
        }

        cur = new Node(kv);
        if (parent->_kv.first > cur->_kv.first)
            parent->_left = cur;
        else
            parent->_right = cur;
				return true;
}
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

简单修改一下，确定初步思路：

bool Insert(const pair<K, V> &kv) {
    Node *cur = _root;
    Node *parent = nullptr;
    if (cur == nullptr) {
        Node *newNode = new Node(key);
        _root = newNode;
        return true;
    }
    while (cur) {
        if (cur->_kv.first < kv.first) {
          parent = cur;
          cur = cur->_right;
        } else if (cur->_kv.first > kv.first) {
          parent = cur;
          cur = cur->_left;
        } else {
          return false;
        }
    }

    // cur == nullptr
    cur = new Node(kv);
    if (parent->_kv.first < kv.first)
      parent->_right = cur;
    else if (parent->_kv.first > kv.first)
      parent->_left = cur;

    cur->_parent = parent;// 这里是新增的代码，用来记录当前结点的双亲，以便后续进行向上迭代

  	// 判断当前插入新结点后会不会导致红黑树树变得不平衡
  	// 此处是代码
    return true;
}
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

检查插入新结点后会不会导致红黑树的性质得到破坏：

因为新结点是红色，如果其双亲是黑色结点，那么则不破坏红黑树的性质，不需要调整；如果其双亲是红色结点，那么则破坏了不红红的性质，需要做出调整，主要分为两种情况：

情况一：u存在且颜色为红。

u是uncle，g是grandfather，p是parent，cur就是当前结点。

那么当前u、g、p、cur的颜色是确定的（根据红黑树性质：左根右，根叶黑，不红红，黑路同）。即cur红，p红，g黑，u红。注意，这个cur可能是新增结点，也肯是由下往上调整时由黑变过来的。但是并不影响调整规则。

调整方案：p和u变黑，g变红，然后继续向上检查（因为当前子树的根结点还是红（g），还可能导致连续的两个红结点）。

那么代码变为如下：while结束条件为parent为空或者parent的颜色为黑。并且我们得记录u是g的左结点还是右结点，以便于后续的旋转调整（确定是L、R、LR、RL旋转的一个）。

这里提示一点：只要我们知道L、LR的调整方案，那么R、RL得到调整方案也很容易知道，因为这两个调整方案的对称的。

bool Insert(const pair<K, V> &kv) {
        if (_root == nullptr) {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }

        Node *parent = nullptr;
        Node *cur = _root;
        while (cur) {
            if (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false;
            }
        }

        cur = new Node(kv);
        if (parent->_kv.first > cur->_kv.first)
            parent->_left = cur;
        else
            parent->_right = cur;

        cur->_parent = parent;

        while (parent && parent->_col == RED) {

            // 记录祖父结点
            Node *grandfather = parent->_parent;

            // 记录祖父结点
            if (parent == grandfather->_left) {
                Node *uncle = grandfather->_right;

                // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
                // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上检查
                    cur = grandfather;
                    parent = cur->_parent;// 注意别写反了
                } else {
                    // 情况二：叔叔不存在或者叔叔存在且为黑
                    
                  	// 以下是代码

            } else {
                Node *uncle = grandfather->_left;
                // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
                // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上检查
                    cur = grandfather;
                    parent = cur->_parent;// 注意别写反了
                } else {
                    // 情况二：叔叔不存在或者叔叔存在且为黑
              
                  	// 以下是代码
                  
                }
            }
        }
        _root->_col = BLACK; // 根结点始终为黑
        return true;
}
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

情况二：u不存在或者存在且颜色为黑。

这个情况有点复杂，我们放到下面的红黑树的旋转中讲解。

2.3、红黑树的旋转

上面讲到情况二：u不存在或者存在且颜色为黑。这个时候存在四种形态：但是每个形态的调整规则都是一样的，不区分u不存在或者存在且颜色为黑。

形态一：p为g的左结点，cur为p的左结点，这个时候需要右单旋。

形态二：p为g的右结点，cur为p的右结点，这个时候需要左单旋。

形态三：p为g的左结点，cur为p的右结点，这个时候需要先左单旋再右单旋。

形态四：p为g的右结点，cur为p的左结点，这个时候需要先右单旋再左单旋。

看完这四种形态，是不是觉得和AVL树很像！并且下面代码用到的左单旋和右单旋的代码都是用的AVL树的，只不过不再需要平衡因子了！

这里声明一个点：下面的所有抽象图，在插入新结点之前，每条路径的最低一层的黑色结点都是代表一棵具有n（可以是0,12,3…）个黑色结点的树，多少个黑色结点不影响调整规则。

2.3.1、右单旋（R旋转）

形态一：p为g的左结点，cur为p的左结点，这个时候需要右单旋。

u是uncle，g是grandfather，p是parent，cur就是当前结点。

调整方案：以g结点进行右单旋，然后p变黑，g变红，然后调整结束，不必再向上检查（因为当前子树的根结点是黑（p），不再可能导致连续的两个红结点）。

代码变为如下：

bool Insert(const pair<K, V> &kv) {
        if (_root == nullptr) {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }

        Node *parent = nullptr;
        Node *cur = _root;
        while (cur) {
            if (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false;
            }
        }

        cur = new Node(kv);
        if (parent->_kv.first > cur->_kv.first)
            parent->_left = cur;
        else
            parent->_right = cur;

        cur->_parent = parent;

        while (parent && parent->_col == RED) {

            // 记录祖父结点
            Node *grandfather = parent->_parent;

            // 记录祖父结点
            if (parent == grandfather->_left) {
                Node *uncle = grandfather->_right;

                // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
                // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上检查
                    cur = grandfather;
                    parent = cur->_parent;// 注意别写反了
                } else {
                    // 情况二：叔叔不存在或者叔叔存在且为黑
                    
                  	//  形状一
                    //               g
                    //        p               u
                    //  cur
                    if (cur == parent->_left) {
                        // 这时候只需要右旋
                        RotateR(grandfather);
                        //只要父亲和祖父变色
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        //形状三
                      
                    }
							break; // 旋转完加变色，不需要再调整
            } else {
                Node *uncle = grandfather->_left;
                // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
                // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上检查
                    cur = grandfather;
                    parent = cur->_parent;// 注意别写反了
                } else {
                    // 情况二：叔叔不存在或者叔叔存在且为黑
              
                  	// 以下是代码
                  
                }
            }
        }
        _root->_col = BLACK; // 根结点始终为黑
        return true;
}
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

2.3.2、左单旋（L旋转）

形态二：p为g的右结点，cur为p的右结点，这个时候需要左单旋。

u是uncle，g是grandfather，p是parent，cur就是当前结点。

调整方案：以g结点进行左单旋，然后p变黑，g变红，然后调整结束，不必再向上检查（因为当前子树的根结点是黑（p），不再可能导致连续的两个红结点）。

这里不再花抽象图，自行根据上述右单旋画。这里仅贴代码：其实根据对称，代码也很好写。

代码变为如下：

bool Insert(const pair<K, V> &kv) {
       if (_root == nullptr) {
           _root = new Node(kv);
           _root->_col = BLACK;
           return true;
       }

       Node *parent = nullptr;
       Node *cur = _root;
       while (cur) {
           if (cur->_kv.first < kv.first) {
               parent = cur;
               cur = cur->_right;
           } else if (cur->_kv.first > kv.first) {
               parent = cur;
               cur = cur->_left;
           } else {
               return false;
           }
       }

       cur = new Node(kv);
       if (parent->_kv.first > cur->_kv.first)
           parent->_left = cur;
       else
           parent->_right = cur;

       cur->_parent = parent;

       while (parent && parent->_col == RED) {

           // 记录祖父结点
           Node *grandfather = parent->_parent;

           // 记录祖父结点
           if (parent == grandfather->_left) {
               Node *uncle = grandfather->_right;

               // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
               // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
               if (uncle && uncle->_col == RED) {
                   parent->_col = uncle->_col = BLACK;
                   grandfather->_col = RED;

                   //继续往上检查
                   cur = grandfather;
                   parent = cur->_parent;// 注意别写反了
               } else {
                   // 情况二：叔叔不存在或者叔叔存在且为黑
                   
                 	//  形状一
                   //               g
                   //        p               u
                   //  cur
                   if (cur == parent->_left) {
                       // 这时候只需要右旋
                       RotateR(grandfather);
                       //只要父亲和祖父变色
                       parent->_col = BLACK;
                       grandfather->_col = RED;
                   } else {
                       //形状三
                     
                   }
							break; // 旋转完加变色，不需要再调整
           } else {
               Node *uncle = grandfather->_left;
               // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
               // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
               if (uncle && uncle->_col == RED) {
                   parent->_col = uncle->_col = BLACK;
                   grandfather->_col = RED;

                   //继续往上检查
                   cur = grandfather;
                   parent = cur->_parent;// 注意别写反了
               } else {
                   // 情况二：叔叔不存在或者叔叔存在且为黑
             
                 	//  形状二
                   //               g
                   //        u               p
                   //                              cur
                   if (cur == parent->_right) {
                       // 这时候只需要左旋
                       RotateL(grandfather);
                       //只要父亲和祖父变色
                       parent->_col = BLACK;
                       grandfather->_col = RED;
                   } else {
                       //形状四
                   }
                 break; // 旋转完加变色，不需要再调整
               }
           }
       }
       _root->_col = BLACK; // 根结点始终为黑
       return true;
}
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

2.3.3、先左单旋再右单旋（LR旋转）

形态三：p为g的左结点，cur为p的右结点，这个时候需要先左单旋再右单旋。

u是uncle，g是grandfather，p是parent，cur就是当前结点。

调整方案：先以p结点进行左单旋，然后以g结点进行右单旋，最后cur变黑，g变红，然后调整结束，不必再向上检查（因为当前子树的根结点是黑（cur），不再可能导致连续的两个红结点）。

代码变为如下：

bool Insert(const pair<K, V> &kv) {
        if (_root == nullptr) {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }

        Node *parent = nullptr;
        Node *cur = _root;
        while (cur) {
            if (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false;
            }
        }

        cur = new Node(kv);
        if (parent->_kv.first > cur->_kv.first)
            parent->_left = cur;
        else
            parent->_right = cur;

        cur->_parent = parent;

        while (parent && parent->_col == RED) {

            // 记录祖父结点
            Node *grandfather = parent->_parent;

            // 记录祖父结点
            if (parent == grandfather->_left) {
                Node *uncle = grandfather->_right;

                // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
                // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上检查
                    cur = grandfather;
                    parent = cur->_parent;// 注意别写反了
                } else {
                    // 情况二：叔叔不存在或者叔叔存在且为黑
                    
                  	//  形状一
                    //               g
                    //        p               u
                    //  cur
                    if (cur == parent->_left) {
                        // 这时候只需要右旋
                        RotateR(grandfather);
                        //只要父亲和祖父变色
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        //形状三
                        //               g
                        //        p               u
                        //            cur

                        // 这时候需要先左旋再右旋
                        // p位置左旋
                        // 再g位置右旋
                        RotateL(parent);
                        RotateR(grandfather);

                        //p和g位置变色
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
							break; // 旋转完加变色，不需要再调整
            } else {
                Node *uncle = grandfather->_left;
                // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
                // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上检查
                    cur = grandfather;
                    parent = cur->_parent;// 注意别写反了
                } else {
                    // 情况二：叔叔不存在或者叔叔存在且为黑
              
                  	//  形状二
                    //               g
                    //        u               p
                    //                              cur
                    if (cur == parent->_right) {
                        // 这时候只需要左旋
                        RotateL(grandfather);
                        //只要父亲和祖父变色
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        //形状四
                    }
                  break; // 旋转完加变色，不需要再调整
                }
            }
        }
        _root->_col = BLACK; // 根结点始终为黑
        return true;
}
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

2.3.4、先右单旋再左单旋（RL旋转）

形态四：p为g的右结点，cur为p的左结点，这个时候需要先右单旋再左单旋。

u是uncle，g是grandfather，p是parent，cur就是当前结点。

调整方案：先以p结点进行右单旋，然后以g结点进行左单旋，最后cur变黑，g变红，然后调整结束，不必再向上检查（因为当前子树的根结点是黑（cur），不再可能导致连续的两个红结点）。

这里不再花抽象图，自行根据上述右单旋画。这里仅贴代码：其实根据对称，代码也很好写。

代码变为如下：

    bool Insert(const pair<K, V> &kv) {
        if (_root == nullptr) {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }

        Node *parent = nullptr;
        Node *cur = _root;
        while (cur) {
            if (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false;
            }
        }

        cur = new Node(kv);
        if (parent->_kv.first > cur->_kv.first)
            parent->_left = cur;
        else
            parent->_right = cur;

        cur->_parent = parent;

        while (parent && parent->_col == RED) {

            // 记录祖父结点
            Node *grandfather = parent->_parent;

            // 记录祖父结点
            if (parent == grandfather->_left) {
                Node *uncle = grandfather->_right;

                // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
                // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上检查
                    cur = grandfather;
                    parent = cur->_parent;// 注意别写反了
                } else {
                    // 情况二：叔叔不存在或者叔叔存在且为黑

                    //  形状一
                    //               g
                    //        p               u
                    //  cur
                    if (cur == parent->_left) {
                        // 这时候只需要右旋
                        RotateR(grandfather);
                        //只要父亲和祖父变色
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        //形状三
                        //               g
                        //        p               u
                        //            cur

                        // 这时候需要先左旋再右旋
                        // p位置左旋
                        // 再g位置右旋
                        RotateL(parent);
                        RotateR(grandfather);

                        //p和g位置变色
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break; // 旋转完加变色，不需要再调整
                }

            } else {
                Node *uncle = grandfather->_left;
                // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
                // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上检查
                    cur = grandfather;
                    parent = cur->_parent;// 注意别写反了
                } else {
                    // 情况二：叔叔不存在或者叔叔存在且为黑

                    //  形状二
                    //               g
                    //        u               p
                    //                              cur
                    if (cur == parent->_right) {
                        // 这时候只需要左旋
                        RotateL(grandfather);
                        //只要父亲和祖父变色
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        //形状四
                        //               g
                        //        u               p
                        //                   cur

                        // 这时候需要先右旋再左旋
                        // p位置右旋
                        // 再g位置左旋
                        RotateR(parent);
                        RotateL(grandfather);

                        //p和g位置变色
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break; // 旋转完加变色，不需要再调整
                }
            }
        }
        _root->_col = BLACK; // 根结点始终为黑
        return true;
    }
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

2.4、红黑树的插入完整代码

需要注意的是：再进行了旋转加变色后，当前子树的根结点都变为了黑色，不再存在连续的红色结点，因此可以直接退出调整，即跳出while循环。

    bool Insert(const pair<K, V> &kv) {
        if (_root == nullptr) {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }

        Node *parent = nullptr;
        Node *cur = _root;
        while (cur) {
            if (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false;
            }
        }

        cur = new Node(kv);
        if (parent->_kv.first > cur->_kv.first)
            parent->_left = cur;
        else
            parent->_right = cur;

        cur->_parent = parent;

        while (parent && parent->_col == RED) {

            // 记录祖父结点
            Node *grandfather = parent->_parent;

            // 记录祖父结点
            if (parent == grandfather->_left) {
                Node *uncle = grandfather->_right;

                // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
                // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上检查
                    cur = grandfather;
                    parent = cur->_parent;// 注意别写反了
                } else {
                    // 情况二：叔叔不存在或者叔叔存在且为黑

                    //  形状一
                    //               g
                    //        p               u
                    //  cur
                    if (cur == parent->_left) {
                        // 这时候只需要右旋
                        RotateR(grandfather);
                        //只要父亲和祖父变色
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        //形状三
                        //               g
                        //        p               u
                        //            cur

                        // 这时候需要先左旋再右旋
                        // p位置左旋
                        // 再g位置右旋
                        RotateL(parent);
                        RotateR(grandfather);

                        //p和g位置变色
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break; // 旋转完加变色，不需要再调整
                }

            } else {
                Node *uncle = grandfather->_left;
                // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
                // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上检查
                    cur = grandfather;
                    parent = cur->_parent;// 注意别写反了
                } else {
                    // 情况二：叔叔不存在或者叔叔存在且为黑

                    //  形状二
                    //               g
                    //        u               p
                    //                              cur
                    if (cur == parent->_right) {
                        // 这时候只需要左旋
                        RotateL(grandfather);
                        //只要父亲和祖父变色
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        //形状四
                        //               g
                        //        u               p
                        //                   cur

                        // 这时候需要先右旋再左旋
                        // p位置右旋
                        // 再g位置左旋
                        RotateR(parent);
                        RotateL(grandfather);

                        //p和g位置变色
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break; // 旋转完加变色，不需要再调整
                }
            }
        }
        _root->_col = BLACK; // 根结点始终为黑
        return true;
    }

void RotateL(Node *parent) {
        Node *subR = parent->_right;
        Node *subRL = subR->_left;

        parent->_right = subRL;
        subR->_left = parent;
        Node *ppnode = parent->_parent;

        if (subRL)
            subRL->_parent = parent;
        parent->_parent = subR;



        // 如果当前parent本身就是跟结点的话，我们得把根结点更新
        if (parent == _root) {
            _root = subR;
            subR->_parent = nullptr;
        } else {
            if (parent == ppnode->_left) {
                // subR链接上之前的爷爷结点
                ppnode->_left = subR;
            } else {
                // subR链接上之前的爷爷结点
                ppnode->_right = subR;
            }
            subR->_parent = ppnode;
        }
    }

    void RotateR(Node *parent) {
        Node *subL = parent->_left;
        Node *subLR = subL->_right;

        parent->_left = subLR;
        subL->_right = parent;
        Node *ppnode = parent->_parent;

        if (subLR)
            subLR->_parent = parent;
        parent->_parent = subL;



        // 如果当前parent本身就是跟结点的话，我们得把根结点更新
        if (parent == _root) {
            _root = subL;
            subL->_parent = nullptr;
        } else {
            if (parent == ppnode->_left) {
                // subR链接上之前的爷爷结点
                ppnode->_left = subL;
            } else {
                // subR链接上之前的爷爷结点
                ppnode->_right = subL;
            }
            subL->_parent = ppnode;
        }
    }
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

3、红黑树的验证

验证其为搜索二叉树
- 中序遍历该红黑树，如果是有序说明是搜索二叉树。
验证其是否满足红黑树的性质
- 左根右，根叶黑，不红红，黑路同。

bool _Check(Node *cur, int blackNum, int refBlackNum) {
        if (cur == nullptr) {
            if (blackNum != refBlackNum) {
                cout << "黑结点数量不一样" << endl;
                return false;// 到空结点开始比较黑结点是不是一样
            }

            cout << blackNum << endl;
            return true;
}

bool IsBalance() {
        if (_root && _root->_col == RED)
            return false;
        int refBlackNum = 0; // 每条路径黑色结点的个数，这里以最右边的路径黑色结点的个数为基准
        Node *cur = _root;
        while (cur) {
            if (cur->_col == BLACK)
                ++refBlackNum;
            cur = cur->_right;
        }
        return _Check(_root, 0, refBlackNum);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

4、红黑树的删除（了解）

红黑树的删除比较难，这里仅贴代码。

    bool Remove(const K &key) {
        Node *target = Find(key);
        if (!target) // 如果没找到目标结点，则返回false
            return false;

        // 执行删除操作
        Node *to_fix = nullptr; // 用于记录需要修正的结点
        Node *parent = target->_parent;
        Colour target_original_colour = target->_col;
        Node *child;
        if (!target->_left) {
            child = target->_right;
            Transplant(target, target->_right);
        } else if (!target->_right) {
            child = target->_left;
            Transplant(target, target->_left);
        } else {
            Node *successor = Minimum(target->_right); // 找到右子树中的最小结点作为后继结点
            target_original_colour = successor->_col;
            child = successor->_right;
            if (successor->_parent == target)
                child->_parent = successor;
            else {
                Transplant(successor, successor->_right);
                successor->_right = target->_right;
                successor->_right->_parent = successor;
            }
            Transplant(target, successor);
            successor->_left = target->_left;
            successor->_left->_parent = successor;
            successor->_col = target->_col;
        }
        delete target;

        // 修正红黑树性质
        if (target_original_colour == BLACK)
            FixAfterDelete(parent, child);
        return true;
    }


    void FixAfterDelete(Node *parent, Node *node) {
        while (node != _root && (!node || node->_col == BLACK)) {
            if (node == parent->_left) {
                Node *sibling = parent->_right;
                if (sibling->_col == RED) {
                    sibling->_col = BLACK;
                    parent->_col = RED;
                    RotateL(parent);
                    sibling = parent->_right;
                }
                if ((!sibling->_left || sibling->_left->_col == BLACK) &&
                    (!sibling->_right || sibling->_right->_col == BLACK)) {
                    sibling->_col = RED;
                    node = parent;
                    parent = parent->_parent;
                } else {
                    if (!sibling->_right || sibling->_right->_col == BLACK) {
                        sibling->_left->_col = BLACK;
                        sibling->_col = RED;
                        RotateR(sibling);
                        sibling = parent->_right;
                    }
                    sibling->_col = parent->_col;
                    parent->_col = BLACK;
                    sibling->_right->_col = BLACK;
                    RotateL(parent);
                    node = _root;
                }
            } else {
                Node *sibling = parent->_left;
                if (sibling->_col == RED) {
                    sibling->_col = BLACK;
                    parent->_col = RED;
                    RotateR(parent);
                    sibling = parent->_left;
                }
                if ((!sibling->_right || sibling->_right->_col == BLACK) &&
                    (!sibling->_left || sibling->_left->_col == BLACK)) {
                    sibling->_col = RED;
                    node = parent;
                    parent = parent->_parent;
                } else {
                    if (!sibling->_left || sibling->_left->_col == BLACK) {
                        sibling->_right->_col = BLACK;
                        sibling->_col = RED;
                        RotateL(sibling);
                        sibling = parent->_left;
                    }
                    sibling->_col = parent->_col;
                    parent->_col = BLACK;
                    sibling->_left->_col = BLACK;
                    RotateR(parent);
                    node = _root;
                }
            }
        }
        if (node)
            node->_col = BLACK;
    }


    Node *Minimum(Node *node) const {
        while (node->_left)
            node = node->_left;
        return node;
    }


    void Transplant(Node *u, Node *v) {
        if (!u->_parent)
            _root = v;
        else if (u == u->_parent->_left)
            u->_parent->_left = v;
        else
            u->_parent->_right = v;
        if (v)
            v->_parent = u->_parent;
    }
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

5、红黑树的性能

红黑树在各种操作的性能表现上都比较稳定，其时间复杂度如下：

查找：红黑树的查找操作与二叉搜索树类似，时间复杂度为 O(log n)，其中 n 为红黑树中元素的数量。

插入：插入操作可能会引起红黑树的结构变化，但是由于红黑树的平衡性质，插入操作的最坏情况时间复杂度也是 O(log n)。

删除：与插入操作类似，删除操作可能会引起红黑树的结构变化，但由于红黑树的平衡性质，删除操作的最坏情况时间复杂度也是 O(log n)。

相比于普通的二叉搜索树，红黑树在插入和删除操作上引入了一些额外的平衡维护操作，但这些操作的时间复杂度都是常数级别的，对整体性能的影响较小。因此，红黑树在实践中通常表现良好，并且被广泛应用在需要高效插入、删除和查找操作的场景中，比如 C++ STL 中的 std::map 和 std::set，后面我们模拟实现map和set可以看到。

6、红黑树的整体代码

RBTree.h文件

enum Colour {
   RED,
   BLACK
};

template<class K, class V>
struct RBTreeNode {
   typedef RBTreeNode<K, V> Node;
   Node *_left;
   Node *_right;
   Node *_parent;
   Colour _col;

   pair<K, V> _kv;

   RBTreeNode(const pair<K, V> &kv) : _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _kv(kv) {}
};


template<class K, class V>
class RBTree {
   typedef RBTreeNode<K, V> Node;
public:

   // 红黑树的查找
   Node *Find(const K &key) const {
       Node *cur = _root;
       while (cur) {
           if (cur->_kv.first < key)
               cur = cur->_right;
           else if (cur->_kv.first > key)
               cur = cur->_left;
           else
               return cur; // 找到了目标结点
       }
       return nullptr; // 没找到目标结点
   }


   // 红黑树的删除

   bool Remove(const K &key) {
       Node *target = Find(key);
       if (!target) // 如果没找到目标结点，则返回false
           return false;

       // 执行删除操作
       Node *to_fix = nullptr; // 用于记录需要修正的结点
       Node *parent = target->_parent;
       Colour target_original_colour = target->_col;
       Node *child;
       if (!target->_left) {
           child = target->_right;
           Transplant(target, target->_right);
       } else if (!target->_right) {
           child = target->_left;
           Transplant(target, target->_left);
       } else {
           Node *successor = Minimum(target->_right); // 找到右子树中的最小结点作为后继结点
           target_original_colour = successor->_col;
           child = successor->_right;
           if (successor->_parent == target)
               child->_parent = successor;
           else {
               Transplant(successor, successor->_right);
               successor->_right = target->_right;
               successor->_right->_parent = successor;
           }
           Transplant(target, successor);
           successor->_left = target->_left;
           successor->_left->_parent = successor;
           successor->_col = target->_col;
       }
       delete target;

       // 修正红黑树性质
       if (target_original_colour == BLACK)
           FixAfterDelete(parent, child);
       return true;
   }


   void FixAfterDelete(Node *parent, Node *node) {
       while (node != _root && (!node || node->_col == BLACK)) {
           if (node == parent->_left) {
               Node *sibling = parent->_right;
               if (sibling->_col == RED) {
                   sibling->_col = BLACK;
                   parent->_col = RED;
                   RotateL(parent);
                   sibling = parent->_right;
               }
               if ((!sibling->_left || sibling->_left->_col == BLACK) &&
                   (!sibling->_right || sibling->_right->_col == BLACK)) {
                   sibling->_col = RED;
                   node = parent;
                   parent = parent->_parent;
               } else {
                   if (!sibling->_right || sibling->_right->_col == BLACK) {
                       sibling->_left->_col = BLACK;
                       sibling->_col = RED;
                       RotateR(sibling);
                       sibling = parent->_right;
                   }
                   sibling->_col = parent->_col;
                   parent->_col = BLACK;
                   sibling->_right->_col = BLACK;
                   RotateL(parent);
                   node = _root;
               }
           } else {
               Node *sibling = parent->_left;
               if (sibling->_col == RED) {
                   sibling->_col = BLACK;
                   parent->_col = RED;
                   RotateR(parent);
                   sibling = parent->_left;
               }
               if ((!sibling->_right || sibling->_right->_col == BLACK) &&
                   (!sibling->_left || sibling->_left->_col == BLACK)) {
                   sibling->_col = RED;
                   node = parent;
                   parent = parent->_parent;
               } else {
                   if (!sibling->_left || sibling->_left->_col == BLACK) {
                       sibling->_right->_col = BLACK;
                       sibling->_col = RED;
                       RotateL(sibling);
                       sibling = parent->_left;
                   }
                   sibling->_col = parent->_col;
                   parent->_col = BLACK;
                   sibling->_left->_col = BLACK;
                   RotateR(parent);
                   node = _root;
               }
           }
       }
       if (node)
           node->_col = BLACK;
   }


   Node *Minimum(Node *node) const {
       while (node->_left)
           node = node->_left;
       return node;
   }


   void Transplant(Node *u, Node *v) {
       if (!u->_parent)
           _root = v;
       else if (u == u->_parent->_left)
           u->_parent->_left = v;
       else
           u->_parent->_right = v;
       if (v)
           v->_parent = u->_parent;
   }


   // 红黑树的插入
   bool Insert(const pair<K, V> &kv) {
       if (_root == nullptr) {
           _root = new Node(kv);
           _root->_col = BLACK;
           return true;
       }

       Node *parent = nullptr;
       Node *cur = _root;
       while (cur) {
           if (cur->_kv.first < kv.first) {
               parent = cur;
               cur = cur->_right;
           } else if (cur->_kv.first > kv.first) {
               parent = cur;
               cur = cur->_left;
           } else {
               return false;
           }
       }

       cur = new Node(kv);
       if (parent->_kv.first > cur->_kv.first)
           parent->_left = cur;
       else
           parent->_right = cur;

       cur->_parent = parent;

       while (parent && parent->_col == RED) {

           // 记录祖父结点
           Node *grandfather = parent->_parent;

           // 记录祖父结点
           if (parent == grandfather->_left) {
               Node *uncle = grandfather->_right;

               // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
               // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
               if (uncle && uncle->_col == RED) {
                   parent->_col = uncle->_col = BLACK;
                   grandfather->_col = RED;

                   //继续往上检查
                   cur = grandfather;
                   parent = cur->_parent;// 注意别写反了
               } else {
                   // 情况二：叔叔不存在或者叔叔存在且为黑

                   //  形状一
                   //               g
                   //        p               u
                   //  cur
                   if (cur == parent->_left) {
                       // 这时候只需要右旋
                       RotateR(grandfather);
                       //只要父亲和祖父变色
                       parent->_col = BLACK;
                       grandfather->_col = RED;
                   } else {
                       //形状三
                       //               g
                       //        p               u
                       //            cur

                       // 这时候需要先左旋再右旋
                       // p位置左旋
                       // 再g位置右旋
                       RotateL(parent);
                       RotateR(grandfather);

                       //p和g位置变色
                       cur->_col = BLACK;
                       grandfather->_col = RED;
                   }
                   break; // 旋转完加变色，不需要再调整
               }

           } else {
               Node *uncle = grandfather->_left;
               // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
               // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
               if (uncle && uncle->_col == RED) {
                   parent->_col = uncle->_col = BLACK;
                   grandfather->_col = RED;

                   //继续往上检查
                   cur = grandfather;
                   parent = cur->_parent;// 注意别写反了
               } else {
                   // 情况二：叔叔不存在或者叔叔存在且为黑

                   //  形状二
                   //               g
                   //        u               p
                   //                              cur
                   if (cur == parent->_right) {
                       // 这时候只需要左旋
                       RotateL(grandfather);
                       //只要父亲和祖父变色
                       parent->_col = BLACK;
                       grandfather->_col = RED;
                   } else {
                       //形状四
                       //               g
                       //        u               p
                       //                   cur

                       // 这时候需要先右旋再左旋
                       // p位置右旋
                       // 再g位置左旋
                       RotateR(parent);
                       RotateL(grandfather);

                       //p和g位置变色
                       cur->_col = BLACK;
                       grandfather->_col = RED;
                   }
                   break; // 旋转完加变色，不需要再调整
               }
           }
       }
       _root->_col = BLACK; // 根结点始终为黑
       return true;
   }

   void InOrder() {
       return _InOrder(_root);
   }

   bool IsBalance() {
       if (_root && _root->_col == RED)
           return false;
       int refBlackNum = 0; // 每条路径黑色结点的个数，这里以最右边的路径黑色结点的个数为基准
       Node *cur = _root;
       while (cur) {
           if (cur->_col == BLACK)
               ++refBlackNum;
           cur = cur->_right;
       }
       return _Check(_root, 0, refBlackNum);
   }

private:
   Node *_root = nullptr;

   bool _Check(Node *cur, int blackNum, int refBlackNum) {
       if (cur == nullptr) {
           if (blackNum != refBlackNum) {
               cout << "黑结点数量不一样" << endl;
               return false;// 到空结点开始比较黑结点是不是一样
           }

           cout << blackNum << endl;
           return true;
       }

       if (cur->_col == RED && cur->_parent->_col == RED) {
           cout << "存在连续红结点：" << cur->_kv.first << endl;
           return false;
       }

       if (cur->_col == BLACK)
           ++blackNum; // 统计该条路径的黑结点个数


       return _Check(cur->_left, blackNum, refBlackNum) && _Check(cur->_right, blackNum, refBlackNum);
   }

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

   void RotateL(Node *parent) {
       Node *subR = parent->_right;
       Node *subRL = subR->_left;

       parent->_right = subRL;
       subR->_left = parent;
       Node *ppnode = parent->_parent;

       if (subRL)
           subRL->_parent = parent;
       parent->_parent = subR;

       // 如果当前parent本身就是跟结点的话，我们得把根结点更新
       if (parent == _root) {
           _root = subR;
           subR->_parent = nullptr;
       } else {
           if (parent == ppnode->_left) {
               // subR链接上之前的爷爷结点
               ppnode->_left = subR;
           } else {
               // subR链接上之前的爷爷结点
               ppnode->_right = subR;
           }
           subR->_parent = ppnode;
       }
   }

   void RotateR(Node *parent) {
       Node *subL = parent->_left;
       Node *subLR = subL->_right;

       parent->_left = subLR;
       subL->_right = parent;
       Node *ppnode = parent->_parent;

       if (subLR)
           subLR->_parent = parent;
       parent->_parent = subL;

       // 如果当前parent本身就是跟结点的话，我们得把根结点更新
       if (parent == _root) {
           _root = subL;
           subL->_parent = nullptr;
       } else {
           if (parent == ppnode->_left) {
               // subR链接上之前的爷爷结点
               ppnode->_left = subL;
           } else {
               // subR链接上之前的爷爷结点
               ppnode->_right = subL;
           }
           subL->_parent = ppnode;
       }
   }
};
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
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397

7、二叉搜索树、AVL树和红黑树的性能对比（插入、查找、旋转（AVL和红黑树））

RBTree.h文件

//
// Created by 徐鹏 on 2024/3/31.
//

#ifndef DEMO_05_RBTREE_H
#define DEMO_05_RBTREE_H

#endif //DEMO_05_RBTREE_H

#include <iostream>

using namespace std;

enum Colour {
    RED,
    BLACK
};

template<class K, class V>
struct RBTreeNode {
    typedef RBTreeNode<K, V> Node;
    Node *_left;
    Node *_right;
    Node *_parent;
    Colour _col;

    pair<K, V> _kv;

    RBTreeNode(const pair<K, V> &kv) : _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED), _kv(kv) {}
};


template<class K, class V>
class RBTree {
    typedef RBTreeNode<K, V> Node;
public:

    // 红黑树的查找
    Node *Find(const K &key) const {
        Node *cur = _root;
        while (cur) {
            if (cur->_kv.first < key)
                cur = cur->_right;
            else if (cur->_kv.first > key)
                cur = cur->_left;
            else
                return cur; // 找到了目标结点
        }
        return nullptr; // 没找到目标结点
    }


    // 红黑树的删除

    bool Remove(const K &key) {
        Node *target = Find(key);
        if (!target) // 如果没找到目标结点，则返回false
            return false;

        // 执行删除操作
        Node *to_fix = nullptr; // 用于记录需要修正的结点
        Node *parent = target->_parent;
        Colour target_original_colour = target->_col;
        Node *child;
        if (!target->_left) {
            child = target->_right;
            Transplant(target, target->_right);
        } else if (!target->_right) {
            child = target->_left;
            Transplant(target, target->_left);
        } else {
            Node *successor = Minimum(target->_right); // 找到右子树中的最小结点作为后继结点
            target_original_colour = successor->_col;
            child = successor->_right;
            if (successor->_parent == target)
                child->_parent = successor;
            else {
                Transplant(successor, successor->_right);
                successor->_right = target->_right;
                successor->_right->_parent = successor;
            }
            Transplant(target, successor);
            successor->_left = target->_left;
            successor->_left->_parent = successor;
            successor->_col = target->_col;
        }
        delete target;

        // 修正红黑树性质
        if (target_original_colour == BLACK)
            FixAfterDelete(parent, child);
        return true;
    }


    void FixAfterDelete(Node *parent, Node *node) {
        while (node != _root && (!node || node->_col == BLACK)) {
            if (node == parent->_left) {
                Node *sibling = parent->_right;
                if (sibling->_col == RED) {
                    sibling->_col = BLACK;
                    parent->_col = RED;
                    RotateL(parent);
                    sibling = parent->_right;
                }
                if ((!sibling->_left || sibling->_left->_col == BLACK) &&
                    (!sibling->_right || sibling->_right->_col == BLACK)) {
                    sibling->_col = RED;
                    node = parent;
                    parent = parent->_parent;
                } else {
                    if (!sibling->_right || sibling->_right->_col == BLACK) {
                        sibling->_left->_col = BLACK;
                        sibling->_col = RED;
                        RotateR(sibling);
                        sibling = parent->_right;
                    }
                    sibling->_col = parent->_col;
                    parent->_col = BLACK;
                    sibling->_right->_col = BLACK;
                    RotateL(parent);
                    node = _root;
                }
            } else {
                Node *sibling = parent->_left;
                if (sibling->_col == RED) {
                    sibling->_col = BLACK;
                    parent->_col = RED;
                    RotateR(parent);
                    sibling = parent->_left;
                }
                if ((!sibling->_right || sibling->_right->_col == BLACK) &&
                    (!sibling->_left || sibling->_left->_col == BLACK)) {
                    sibling->_col = RED;
                    node = parent;
                    parent = parent->_parent;
                } else {
                    if (!sibling->_left || sibling->_left->_col == BLACK) {
                        sibling->_right->_col = BLACK;
                        sibling->_col = RED;
                        RotateL(sibling);
                        sibling = parent->_left;
                    }
                    sibling->_col = parent->_col;
                    parent->_col = BLACK;
                    sibling->_left->_col = BLACK;
                    RotateR(parent);
                    node = _root;
                }
            }
        }
        if (node)
            node->_col = BLACK;
    }


    Node *Minimum(Node *node) const {
        while (node->_left)
            node = node->_left;
        return node;
    }


    void Transplant(Node *u, Node *v) {
        if (!u->_parent)
            _root = v;
        else if (u == u->_parent->_left)
            u->_parent->_left = v;
        else
            u->_parent->_right = v;
        if (v)
            v->_parent = u->_parent;
    }


    // 红黑树的插入
    bool Insert(const pair<K, V> &kv) {
        if (_root == nullptr) {
            _root = new Node(kv);
            _root->_col = BLACK;
            return true;
        }

        Node *parent = nullptr;
        Node *cur = _root;
        while (cur) {
            if (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false;
            }
        }

        cur = new Node(kv);
        if (parent->_kv.first > cur->_kv.first)
            parent->_left = cur;
        else
            parent->_right = cur;

        cur->_parent = parent;

        while (parent && parent->_col == RED) {

            // 记录祖父结点
            Node *grandfather = parent->_parent;

            // 记录祖父结点
            if (parent == grandfather->_left) {
                Node *uncle = grandfather->_right;

                // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
                // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上检查
                    cur = grandfather;
                    parent = cur->_parent;// 注意别写反了
                } else {
                    // 情况二：叔叔不存在或者叔叔存在且为黑

                    //  形状一
                    //               g
                    //        p               u
                    //  cur
                    if (cur == parent->_left) {
                        // 这时候只需要右旋
                        RotateR(grandfather);
                        //只要父亲和祖父变色
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        //形状三
                        //               g
                        //        p               u
                        //            cur

                        // 这时候需要先左旋再右旋
                        // p位置左旋
                        // 再g位置右旋
                        RotateL(parent);
                        RotateR(grandfather);

                        //p和g位置变色
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break; // 旋转完加变色，不需要再调整
                }

            } else {
                Node *uncle = grandfather->_left;
                // 情况一：叔叔存在且为红 --- 当前不用旋转调整，只需要改变g、u、p的颜色
                // 因为如果叔叔为红，那么祖父和父亲的颜色是确定的！
                if (uncle && uncle->_col == RED) {
                    parent->_col = uncle->_col = BLACK;
                    grandfather->_col = RED;

                    //继续往上检查
                    cur = grandfather;
                    parent = cur->_parent;// 注意别写反了
                } else {
                    // 情况二：叔叔不存在或者叔叔存在且为黑

                    //  形状二
                    //               g
                    //        u               p
                    //                              cur
                    if (cur == parent->_right) {
                        // 这时候只需要左旋
                        RotateL(grandfather);
                        //只要父亲和祖父变色
                        parent->_col = BLACK;
                        grandfather->_col = RED;
                    } else {
                        //形状四
                        //               g
                        //        u               p
                        //                   cur

                        // 这时候需要先右旋再左旋
                        // p位置右旋
                        // 再g位置左旋
                        RotateR(parent);
                        RotateL(grandfather);

                        //p和g位置变色
                        cur->_col = BLACK;
                        grandfather->_col = RED;
                    }
                    break; // 旋转完加变色，不需要再调整
                }
            }
        }
        _root->_col = BLACK; // 根结点始终为黑
        return true;
    }

    void InOrder() {
        return _InOrder(_root);
    }

    bool IsBalance() {
        if (_root && _root->_col == RED)
            return false;
        int refBlackNum = 0; // 每条路径黑色结点的个数，这里以最右边的路径黑色结点的个数为基准
        Node *cur = _root;
        while (cur) {
            if (cur->_col == BLACK)
                ++refBlackNum;
            cur = cur->_right;
        }
        return _Check(_root, 0, refBlackNum);
    }

    int Height() {
        return _Height(_root);
    }

    int _Height(Node *root) {
        if (root == nullptr)
            return 0;
        int lheight = _Height(root->_left);
        int rheight = _Height(root->_right);
        return lheight > rheight ? lheight + 1 : rheight + 1;
    }

    int Size() {
        if (!_root)
            return 0;

        int size = 0;
        std::stack<Node*> stack;
        Node *current = _root;

        while (current || !stack.empty()) {
            while (current) {
                stack.push(current);
                current = current->_left;
            }

            current = stack.top();
            stack.pop();
            size++;
            current = current->_right;
        }

        return size;
    }



    int GetRotateSize() {
        return rotateSize;
    }

private:
    Node *_root = nullptr;
    int rotateSize = 0;

    bool _Check(Node *cur, int blackNum, int refBlackNum) {
        if (cur == nullptr) {
            if (blackNum != refBlackNum) {
                cout << "黑结点数量不一样" << endl;
                return false;// 到空结点开始比较黑结点是不是一样
            }

            return true;
        }

        if (cur->_col == RED && cur->_parent->_col == RED) {
            cout << "存在连续红结点：" << cur->_kv.first << endl;
            return false;
        }

        if (cur->_col == BLACK)
            ++blackNum; // 统计该条路径的黑结点个数


        return _Check(cur->_left, blackNum, refBlackNum) && _Check(cur->_right, blackNum, refBlackNum);
    }

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

    void RotateL(Node *parent) {
        ++rotateSize;

        Node *subR = parent->_right;
        Node *subRL = subR->_left;

        parent->_right = subRL;
        subR->_left = parent;
        Node *ppnode = parent->_parent;

        if (subRL)
            subRL->_parent = parent;
        parent->_parent = subR;

        // 如果当前parent本身就是跟结点的话，我们得把根结点更新
        if (parent == _root) {
            _root = subR;
            subR->_parent = nullptr;
        } else {
            if (parent == ppnode->_left) {
                // subR链接上之前的爷爷结点
                ppnode->_left = subR;
            } else {
                // subR链接上之前的爷爷结点
                ppnode->_right = subR;
            }
            subR->_parent = ppnode;
        }
    }

    void RotateR(Node *parent) {
        ++rotateSize;

        Node *subL = parent->_left;
        Node *subLR = subL->_right;

        parent->_left = subLR;
        subL->_right = parent;
        Node *ppnode = parent->_parent;

        if (subLR)
            subLR->_parent = parent;
        parent->_parent = subL;

        // 如果当前parent本身就是跟结点的话，我们得把根结点更新
        if (parent == _root) {
            _root = subL;
            subL->_parent = nullptr;
        } else {
            if (parent == ppnode->_left) {
                // subR链接上之前的爷爷结点
                ppnode->_left = subL;
            } else {
                // subR链接上之前的爷爷结点
                ppnode->_right = subL;
            }
            subL->_parent = ppnode;
        }
    }
};
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
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455

AVLTree.h文件

//
// Created by 徐鹏 on 2024/3/31.
//

#ifndef DEMO_05_AVLTREE_H
#define DEMO_05_AVLTREE_H

#endif //DEMO_05_AVLTREE_H

#include<iostream>

using namespace std;

template<class K, class V>
struct AVLTreeNode {
    typedef AVLTreeNode<K, V> Node;

    Node *_left;
    Node *_right;
    Node *_parent;

    pair<K, V> _kv;
    int _bf; // 平衡因子

    AVLTreeNode(const pair<K, V> &kv) : _left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0) {}
};


template<class K, class V>
class AVLTree {
public:
    typedef AVLTreeNode<K, V> Node;

    // AVL的查找
    Node *Find(const K &key) const {
        Node *cur = _root;

        // 从根节点开始搜索
        while (cur) {
            if (cur->_kv.first < key) {
                cur = cur->_right; // 如果当前节点的键值小于目标键值，则向右子树搜索
            } else if (cur->_kv.first > key) {
                cur = cur->_left; // 如果当前节点的键值大于目标键值，则向左子树搜索
            } else {
                return cur; // 找到目标键值，返回当前节点
            }
        }

        return nullptr; // 没有找到目标键值，返回空指针
    }


    // AVL的删除
    bool Remove(const K &key) {
        return Remove(_root, key);
    }

    bool Remove(Node *&root, const K &key) {
        if (!root)
            return false;

        if (key < root->_kv.first) {
            bool res = Remove(root->_left, key);
            // 重新计算平衡因子并进行平衡调整
            if (res)
                updateBalanceFactor(root);
            return res;
        } else if (key > root->_kv.first) {
            bool res = Remove(root->_right, key);
            // 重新计算平衡因子并进行平衡调整
            if (res)
                updateBalanceFactor(root);
            return res;
        } else {
            if (!root->_left || !root->_right) {
                Node *temp = root;
                root = (root->_left) ? root->_left : root->_right;
                if (root)
                    root->_parent = temp->_parent;
                delete temp;
            } else {
                Node *successor = GetSuccessor(root->_right);
                root->_kv = successor->_kv;
                Remove(root->_right, successor->_kv.first);
                // 重新计算平衡因子并进行平衡调整
                updateBalanceFactor(root);
            }
            return true;
        }
    }

    Node *GetSuccessor(Node *node) {
        while (node->_left)
            node = node->_left;
        return node;
    }

    void updateBalanceFactor(Node *node) {
        int leftHeight = (node->_left) ? _Height(node->_left) : -1;
        int rightHeight = (node->_right) ? _Height(node->_right) : -1;
        node->_bf = rightHeight - leftHeight;
    }


    // AVL的插入
    bool Insert(const pair<K, V> &kv) {

        if (_root == nullptr) {
            _root = new Node(kv);
            return true;
        }

        Node *cur = _root;
        Node *parent = nullptr;

        while (cur) {
            if (cur->_kv.first < kv.first) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_kv.first > kv.first) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false;
            }
        }

        // cur == nullptr
        cur = new Node(kv);
        if (parent->_kv.first < kv.first)
            parent->_right = cur;
        else if (parent->_kv.first > kv.first)
            parent->_left = cur;

        cur->_parent = parent;

        // 看当前插入的结点会不会导致树不平衡
        // parent == nullptr说明已经调整到根了
        // 平衡因子使用的是右减左的方案
        while (parent) {
            if (cur == parent->_left)
                parent->_bf--;
            else
                parent->_bf++;

            // 说明插入之前parent的平衡因子是1或者-1，现在变得非常健康，不要调整
            if (parent->_bf == 0) {
                break;
            } else if (parent->_bf == 1 || parent->_bf == -1) {
                // 说明插入之前parent的平衡因子是0,现在变得亚健康，需要往上看爷爷结点是不是平衡因子出现问题了
                cur = cur->_parent;
                parent = parent->_parent;
            } else if (parent->_bf == 2 || parent->_bf == -2) {
                // 旋转调整

                // 说明插入之前parent的平衡因子是1或者-1，现在变得不健康了，需要调整
                if (parent->_bf == 2 && parent->_right->_bf == 1) { // parent->_bf == 2 && cur->_bf == 1
                    // 此时需要左单旋
                    RotateL(parent);
                } else if (parent->_bf == -2 && parent->_left->_bf == -1) {
                    // 此时需要右单旋
                    RotateR(parent);
                } else if (parent->_bf == 2 && parent->_right->_bf == -1) {
                    // 此时需要右旋再左旋
                    RotateRL(parent);
                } else {
                    // 此时需要左旋再右旋
                    RotateLR(parent);
                }
                break;// 调整结束，不用再往上调整
            }
        }
        return true;
    }

    void RotateL(Node *parent) {
        ++rotateSize;

        Node *subR = parent->_right;
        Node *subRL = subR->_left;

        parent->_right = subRL;
        subR->_left = parent;
        Node *ppnode = parent->_parent;

        if (subRL)
            subRL->_parent = parent;
        parent->_parent = subR;



        // 如果当前parent本身就是跟结点的话，我们得把根结点更新
        if (parent == _root) {
            _root = subR;
            subR->_parent = nullptr;
        } else {
            if (parent == ppnode->_left) {
                // subR链接上之前的爷爷结点
                ppnode->_left = subR;
            } else {
                // subR链接上之前的爷爷结点
                ppnode->_right = subR;
            }
            subR->_parent = ppnode;
        }
        parent->_bf = 0;
        subR->_bf = 0;
    }

    void RotateR(Node *parent) {
        ++rotateSize;

        Node *subL = parent->_left;
        Node *subLR = subL->_right;

        parent->_left = subLR;
        subL->_right = parent;
        Node *ppnode = parent->_parent;

        if (subLR)
            subLR->_parent = parent;
        parent->_parent = subL;



        // 如果当前parent本身就是跟结点的话，我们得把根结点更新
        if (parent == _root) {
            _root = subL;
            subL->_parent = nullptr;
        } else {
            if (parent == ppnode->_left) {
                // subR链接上之前的爷爷结点
                ppnode->_left = subL;
            } else {
                // subR链接上之前的爷爷结点
                ppnode->_right = subL;
            }
            subL->_parent = ppnode;
        }
        parent->_bf = 0;
        subL->_bf = 0;
    }

    void RotateRL(Node *parent) {
        // 因为左单旋转和右单旋后bf都设置为0了，因此我们需要手动再设置改变的结点的平衡因子

        // 会改变平衡因子的结点
        Node *subR = parent->_right;
        Node *subRL = subR->_left;

        //  用来记录没旋转前subRL的结点的bf
        int rlbf = subRL->_bf;

        RotateR(parent->_right);
        RotateL(parent);

        // 讨论旋转后的bf（平衡因子改变的结点）
        if (rlbf == -1) {
            subRL->_bf = 0;
            subR->_bf = 1;
            parent->_bf = 0;
        } else if (rlbf == 1) {
            subRL->_bf = 0;
            subR->_bf = 0;
            parent->_bf = -1;
        } else if (rlbf == 0) { // rlbf == 0
            subRL->_bf = 0;
            subR->_bf = 0;
            parent->_bf = 0;
        } else {
            assert(false);
        }
    }

    void RotateLR(Node *parent) {
        // 因为左单旋转和右单旋后bf都设置为0了，因此我们需要手动再设置改变的结点的平衡因子

        // 会改变平衡因子的结点
        Node *subL = parent->_left;
        Node *subLR = subL->_right;

        //  用来记录没旋转前subLR的结点的bf
        int lrbf = subLR->_bf;

        RotateL(parent->_left);
        RotateR(parent);

        // 讨论旋转后的bf（平衡因子改变的结点）
        if (lrbf == -1) {
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 1;
        } else if (lrbf == 1) {
            subLR->_bf = 0;
            subL->_bf = -1;
            parent->_bf = 0;
        } else if (lrbf == 0) { // lrbf == 0
            subLR->_bf = 0;
            subL->_bf = 0;
            parent->_bf = 0;
        } else {
            assert(false);
        }

    }


    void InOrder() {
        _InOrder(_root);
    }

    int Height() {
        return _Height(_root);
    }

    bool IsBalance() {
        return _IsBalance(_root);
    }

    int Size() {
        if (!_root)
            return 0;

        int size = 0;
        std::stack<Node*> stack;
        Node *current = _root;

        while (current || !stack.empty()) {
            while (current) {
                stack.push(current);
                current = current->_left;
            }

            current = stack.top();
            stack.pop();
            size++;
            current = current->_right;
        }

        return size;
    }


    int GetRotateSize() {
        return rotateSize;
    }


private:

    bool _IsBalance(Node *root) {
        if (root == nullptr)
            return true;
        int lheight = _Height(root->_left);
        int rheight = _Height(root->_right);
        if (root->_bf != (rheight - lheight) || root->_bf > 1 || root->_bf < -1)
            return false;
        return _IsBalance(root->_left) && _IsBalance(root->_right);
    }

    int _Height(Node *root) {
        if (root == nullptr)
            return 0;
        int lheight = _Height(root->_left);
        int rheight = _Height(root->_right);
        return lheight > rheight ? lheight + 1 : rheight + 1;
    }

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

    }


    Node *_root = nullptr;
    int rotateSize = 0;
};
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
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381

BinarySeachTree.h文件

//
// Created by 徐鹏 on 2024/3/31.
//

#ifndef DEMO_05_BINARYSEACHTREE_H
#define DEMO_05_BINARYSEACHTREE_H

#endif //DEMO_05_BINARYSEACHTREE_H

#include <iostream>

using namespace std;

template<class K>
struct BSTreeNode {
    //typedef BSTreeNode<K> Node;

    BSTreeNode<K> *_left;
    BSTreeNode<K> *_right;
    K _key;

    BSTreeNode(const K &key) : _left(nullptr), _right(nullptr), _key(key) {}

};


template<class K>
class BinarySearchTree {
public:
    typedef BSTreeNode<K> Node;

    BinarySearchTree() = default;

    BinarySearchTree(const BinarySearchTree<K> &b) {
        _root = Copy(b._root);
    }

    Node *Copy(Node *root) {
        if (root == nullptr)
            return nullptr;
        Node *newNode = new Node(root->_key);
        newNode->_left = Copy(root->_left);
        newNode->_right = Copy(root->_right);

        return newNode;

    }

    BinarySearchTree<K> &operator=(BinarySearchTree<K> b) {
        swap(b._root, _root);
        return *this;
    }

    ~BinarySearchTree() {
        Destroy(_root);
    }

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


    bool Erase(const K &key) {
        Node *cur = _root;
        Node *parent = nullptr;

        if (cur == nullptr)
            return false;


        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            } else {
                //找到要删的结点

                // 当前要删的结点有一个孩子或者没有孩子
                if (cur->_left == nullptr) {
                    // 判断跟结点是否只有一颗子树
                    if (cur == _root) {
                        _root = _root->_right;
                    } else {
                        if (parent->_left == cur)
                            parent->_left = cur->_right;
                        else
                            parent->_right = cur->_right;
                    }

                    delete cur;
                    return true;

                } else if (cur->_right == nullptr) {

                    // 判断跟结点是否只有一颗子树
                    if (cur == _root) {
                        _root = _root->_left;
                    } else {
                        if (parent->_left == cur)
                            parent->_left = cur->_left;
                        else
                            parent->_right = cur->_left;
                    }


                    delete cur;
                    return true;

                } else {
                    // 当前要删的结点有两个孩子

                    // 找个替代的值去删  -- 找左子树的最右结点,即左子树最大的结点

                    Node *LeftMax = cur->_left;
                    Node *LeftMaxParent = cur;
                    while (LeftMax->_right) {
                        LeftMaxParent = LeftMax;
                        LeftMax = LeftMax->_right;
                    }

                    cur->_key = LeftMax->_key;
                    if (LeftMaxParent->_left == LeftMax)
                        LeftMaxParent->_left = LeftMax->_left;
                    else
                        LeftMaxParent->_right = LeftMax->_left;
                    delete LeftMax;
                    return true;
                }
            }
        }
        return false;
    }

    bool Insert(const K &key) {
        Node *cur = _root;
        Node *parent = nullptr;
        if (cur == nullptr) {
            Node *newNode = new Node(key);
            _root = newNode;
            return true;
        }
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false;
            }
        }

        // cur == nullptr
//        Node *newNode = new Node(key);
//        if (parent->_key < key)
//            parent->_right = newNode;
//        else if (parent->_key > key)
//            parent->_left = newNode;

        cur = new Node(key);
        if (parent->_key < key)
            parent->_right = cur;
        else if (parent->_key > key)
            parent->_left = cur;
        return true;
    }

    bool Find(const K &key) {
        Node *cur = _root;
        if (cur == nullptr)
            return false;

        while (cur) {
            if (cur->_key < key) {
                cur = cur->_right;
            } else if (cur->_key > key) {
                cur = cur->_left;
            } else {
                return true;
            }
        }

        return false;
    }

    int Height() {
        return _Height(_root);
    }

    int _Height(Node *root) {
        if (root == nullptr)
            return 0;
        int lheight = _Height(root->_left);
        int rheight = _Height(root->_right);
        return lheight > rheight ? lheight + 1 : rheight + 1;
    }

    int Size() {
        if (!_root)
            return 0;

        int size = 0;
        std::stack<Node *> stack;
        Node *current = _root;

        while (current || !stack.empty()) {
            while (current) {
                stack.push(current);
                current = current->_left;
            }

            current = stack.top();
            stack.pop();
            size++;
            current = current->_right;
        }

        return size;
    }

    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }


    bool FindR(const K &key) {
        return _FindR(_root, key);
    }

    bool InsertR(const K &key) {
        return _InsertR(_root, key);
    }

    bool EraseR(const K &key) {
        return _EraseR(_root, key);
    }


private:

    bool _EraseR(Node *root, const K &key) {
        if (root == nullptr)
            return false;

        if (root->_key < key) {
            return _EraseR(root->_right, key);
        } else if (root->_key > key) {
            return _EraseR(root->_left, key);
        } else {

            Node *del = root;
            if (root->_right == nullptr)
                root = root->_left;
            else if (root->_left == nullptr)
                root = root->_right;
            else {
                // 将当前要删的结点的值和当前结点的左子树最大值的结点交换
                Node *LeftMax = root->_left;
                while (LeftMax->_right) {
                    LeftMax = LeftMax->_right;
                }

                swap(LeftMax->_key, root->_key);

                return _EraseR(root, key);
            }
            delete del;
            return true;
        }
    }

    bool _InsertR(Node *&root, const K &key) {
        if (root == nullptr) {
            root = new Node(key);
            return true;
        }

        if (root->_key < key) {
            return _InsertR(root->_right, key);
        } else if (root->_key > key) {
            return _InsertR(root->_left, key);
        } else {
            return false;
        }
    }

    bool _FindR(Node *root, const K &key) {
        if (root == nullptr)
            return false;

        if (root->_key < key) {
            return _FindR(root->_right, key);
        } else if (root->_key > key) {
            return _FindR(root->_left, key);
        } else {
            return true;
        }
    }


    void _InOrder(Node *root) {
        if (root == nullptr)
            return;
        if (root->_left)
            _InOrder(root->_left);
        cout << root->_key << " ";
        if (root->_right)
            _InOrder(root->_right);
    }

    Node *_root = nullptr;
};


namespace kv {
    template<class K, class V>
    struct BSTreeNode {
        //typedef BSTreeNode<K> Node;

        BSTreeNode<K, V> *_left;
        BSTreeNode<K, V> *_right;
        K _key;
        V _val;

        BSTreeNode(const K &key, const K &val) : _left(nullptr), _right(nullptr), _key(key), _val(val) {}

    };


    template<class K, class V>
    class BinarySearchTree {
    public:
        typedef BSTreeNode<K, V> Node;

        BinarySearchTree() = default;

        BinarySearchTree(const BinarySearchTree<K, V> &b) {
            _root = Copy(b._root);
        }

        Node *Copy(Node *root) {
            if (root == nullptr)
                return nullptr;
            Node *newNode = new Node(root->_key);
            newNode->_left = Copy(root->_left);
            newNode->_right = Copy(root->_right);

            return newNode;

        }

        BinarySearchTree<K, V> &operator=(BinarySearchTree<K, V> b) {
            swap(b._root, _root);
            return *this;
        }

        ~BinarySearchTree() {
            Destroy(_root);
        }

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


        bool Erase(const K &key) {
            Node *cur = _root;
            Node *parent = nullptr;

            if (cur == nullptr)
                return false;


            while (cur) {
                if (cur->_key < key) {
                    parent = cur;
                    cur = cur->_right;
                } else if (cur->_key > key) {
                    parent = cur;
                    cur = cur->_left;
                } else {
                    //找到要删的结点

                    // 当前要删的结点有一个孩子或者没有孩子
                    if (cur->_left == nullptr) {
                        // 判断跟结点是否只有一颗子树
                        if (cur == _root) {
                            _root = _root->_right;
                        } else {
                            if (parent->_left == cur)
                                parent->_left = cur->_right;
                            else
                                parent->_right = cur->_right;
                        }

                        delete cur;
                        return true;

                    } else if (cur->_right == nullptr) {

                        // 判断跟结点是否只有一颗子树
                        if (cur == _root) {
                            _root = _root->_left;
                        } else {
                            if (parent->_left == cur)
                                parent->_left = cur->_left;
                            else
                                parent->_right = cur->_left;
                        }


                        delete cur;
                        return true;

                    } else {
                        // 当前要删的结点有两个孩子

                        // 找个替代的值去删  -- 找左子树的最右结点,即左子树最大的结点

                        Node *LeftMax = cur->_left;
                        Node *LeftMaxParent = cur;
                        while (LeftMax->_right) {
                            LeftMaxParent = LeftMax;
                            LeftMax = LeftMax->_right;
                        }

                        cur->_key = LeftMax->_key;
                        if (LeftMaxParent->_left == LeftMax)
                            LeftMaxParent->_left = LeftMax->_left;
                        else
                            LeftMaxParent->_right = LeftMax->_left;
                        delete LeftMax;
                        return true;
                    }
                }
            }
            return false;
        }

        bool Insert(const K &key, const K &val) {
            Node *cur = _root;
            Node *parent = nullptr;
            if (cur == nullptr) {
                Node *newNode = new Node(key, val);
                _root = newNode;
                return true;
            }
            while (cur) {
                if (cur->_key < key) {
                    parent = cur;
                    cur = cur->_right;
                } else if (cur->_key > key) {
                    parent = cur;
                    cur = cur->_left;
                } else {
                    return false;
                }
            }

            // cur == nullptr
            Node *newNode = new Node(key, val);
            if (parent->_key < key)
                parent->_right = newNode;
            else if (parent->_key > key)
                parent->_left = newNode;
            return true;
        }

        Node *Find(const K &key) {
            Node *cur = _root;
            if (cur == nullptr)
                return nullptr;

            while (cur) {
                if (cur->_key < key) {
                    cur = cur->_right;
                } else if (cur->_key > key) {
                    cur = cur->_left;
                } else {
                    return cur;
                }
            }

            return nullptr;
        }

        void InOrder() {
            _InOrder(_root);
            cout << endl;
        }


    private:

        void _InOrder(Node *root) {
            if (root == nullptr)
                return;
            if (root->_left)
                _InOrder(root->_left);
            cout << root->_key << " ";
            if (root->_right)
                _InOrder(root->_right);
        }

        Node *_root = nullptr;
    };

}
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
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521

main.cpp文件

#include<stack>
#include"AVLTree.h"
#include"RBTree.h"
#include"BinarySeachTree.h"
#include<vector>

// 插入结点的个数 ， 可自行修改查看
#define N 2000 

void test_ARB1() {
    vector<int> v;
    v.reserve(N);
    srand(time(0));

    for (size_t i = 0; i < N; i++) {
        v.push_back(rand() + i); // 让几棵树插入随机值
        //v.push_back( i );// 让几棵树插入有序值 -- 这个会导致二叉搜索树和结点个数一样高
    }

    RBTree<int, int> rbt;
    AVLTree<int, int> avl;
    BinarySearchTree<int> bst;

    int begin1 = clock();
    for (auto &e: v) {
        rbt.Insert(make_pair(e, e));
    }
    int end1 = clock();

    int begin2 = clock();
    for (auto &e: v) {
        avl.Insert(make_pair(e, e));
    }
    int end2 = clock();

    int begin3 = clock();
    for (auto &e: v) {
        bst.Insert(e);
    }
    int end3 = clock();

    cout << "RBTree RotateSize:" << rbt.GetRotateSize() << endl;
    cout << "AVLTree RotateSize:" << avl.GetRotateSize() << endl;
    cout << "============================" << endl;


    cout << "RBTree Insert:" << end1 - begin1 << endl;
    cout << "AVLTree Insert:" << end2 - begin2 << endl;
    cout << "BinarySearchTree Insert:" << end3 - begin3 << endl;
    cout << "============================" << endl;


    cout << "RBTree IsBalance:" << rbt.IsBalance() << endl;
    cout << "AVLTree IsBalance:" << avl.IsBalance() << endl;
    cout << "============================" << endl;


    cout << "RBTree Height:" << rbt.Height() << endl;
    cout << "RBTree Size:" << rbt.Size() << endl;
    cout << "============================" << endl;


    cout << "AVLTree Height:" << avl.Height() << endl;
    cout << "AVLTree Size:" << avl.Size() << endl;
    cout << "============================" << endl;


    cout << "BinarySearchTree Height:" << bst.Height() << endl;
    cout << "BinarySearchTree Size:" << bst.Size() << endl;
    cout << "============================" << endl;


    int begin4 = clock();
    for (auto &e: v) {
        rbt.Find(e);
    }

//    // 随机值
//    for (size_t i = 0; i < N; i++) {
//        rbt.Find((rand() + i));
//    }

    int end4 = clock();

    int begin5 = clock();
    for (auto &e: v) {
        avl.Find(e);
    }

//    // 随机值
//    for (size_t i = 0; i < N; i++) {
//        avl.Find((rand() + i));
//    }
    int end5 = clock();


    int begin6 = clock();
    for (auto &e: v) {
        bst.Find(e);
    }

//    // 随机值
//    for (size_t i = 0; i < N; i++) {
//        avl.Find((rand() + i));
//    }
    int end6 = clock();
    cout << "RBTree Find:" << end4 - begin4 << endl;
    cout << "AVLTree Find:" << end5 - begin5 << endl;
    cout << "BinarySearchTree Find:" << end6 - begin6 << endl;

}

int main() {
    test_ARB1();
    return 0;
}
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

当插入的是有序值时，输出为以下（此时N为2000）

RBTree RotateSize:1981
AVLTree RotateSize:1989
============================
RBTree Insert:148
AVLTree Insert:132
BinarySearchTree Insert:2548
============================
RBTree IsBalance:1
AVLTree IsBalance:1
============================
RBTree Height:19
RBTree Size:2000
============================
AVLTree Height:11
AVLTree Size:2000
============================
BinarySearchTree Height:2000
BinarySearchTree Size:2000
============================
RBTree Find:76
AVLTree Find:79
BinarySearchTree Find:2525
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

可以看到二叉搜索树的高度非常高，而红黑树和AVL树高度不高。也能看到旋转次数红黑树比AVL树少。

我们再来看插入的是随机值，输出为以下（此时N为2000）：

RBTree RotateSize:1191
AVLTree RotateSize:1454
============================
RBTree Insert:220
AVLTree Insert:347
BinarySearchTree Insert:165
============================
RBTree IsBalance:1
AVLTree IsBalance:1
============================
RBTree Height:14
RBTree Size:2000
============================
AVLTree Height:13
AVLTree Size:2000
============================
BinarySearchTree Height:29
BinarySearchTree Size:2000
============================
RBTree Find:128
AVLTree Find:129
BinarySearchTree Find:127
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

可以看到二叉搜索树的高度依然最高，红黑树其次，AVL树最低。也能看到旋转次数红黑树依然比AVL树少。

当N非常大的时候，二叉搜索树与红黑树、AVL树不是一个量级的，不用比较。

我们可以单独比较红黑树、AVL树。

main.cpp文件

#include<stack>
#include"AVLTree.h"
#include"RBTree.h"
#include"BinarySeachTree.h"
#include<vector>

#define N 3000000

void test_ARB2() {
    vector<int> v;
    v.reserve(N);
    srand(time(0));

    for (size_t i = 0; i < N; i++) {
        v.push_back(rand() + i); // 让几棵树插入随机值
//        v.push_back( i );// 让几棵树插入有序值 -- 这个会导致二叉搜索树和结点个数一样高
    }

    RBTree<int, int> rbt;
    AVLTree<int, int> avl;

    int begin1 = clock();
    for (auto &e: v) {
        rbt.Insert(make_pair(e, e));
    }
    int end1 = clock();

    int begin2 = clock();
    for (auto &e: v) {
        avl.Insert(make_pair(e, e));
    }
    int end2 = clock();


    cout << "RBTree RotateSize:" << rbt.GetRotateSize() << endl;
    cout << "AVLTree RotateSize:" << avl.GetRotateSize() << endl;
    cout << "============================" << endl;


    cout << "RBTree Insert:" << end1 - begin1 << endl;
    cout << "AVLTree Insert:" << end2 - begin2 << endl;
    cout << "============================" << endl;


    cout << "RBTree IsBalance:" << rbt.IsBalance() << endl;
    cout << "AVLTree IsBalance:" << avl.IsBalance() << endl;
    cout << "============================" << endl;


    cout << "RBTree Height:" << rbt.Height() << endl;
    cout << "RBTree Size:" << rbt.Size() << endl;
    cout << "============================" << endl;


    cout << "AVLTree Height:" << avl.Height() << endl;
    cout << "AVLTree Size:" << avl.Size() << endl;
    cout << "============================" << endl;



    int begin4 = clock();
    for (auto &e: v) {
        rbt.Find(e);
    }

//    // 随机值
//    for (size_t i = 0; i < N; i++) {
//        rbt.Find((rand() + i));
//    }

    int end4 = clock();

    int begin5 = clock();
    for (auto &e: v) {
        avl.Find(e);
    }

//    // 随机值
//    for (size_t i = 0; i < N; i++) {
//        avl.Find((rand() + i));
//    }
    int end5 = clock();


    cout << "RBTree Find:" << end4 - begin4 << endl;
    cout << "AVLTree Find:" << end5 - begin5 << endl;

}
int main() {
//    test_ARB1();
    test_ARB2();
    return 0;
}
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

当插入的是随机值，输出为以下（此时N为3000000）：

RBTree RotateSize:1745356
AVLTree RotateSize:2092687
============================
RBTree Insert:2483973
AVLTree Insert:2235168
============================
RBTree IsBalance:1
AVLTree IsBalance:1
============================
RBTree Height:27
RBTree Size:2997882
============================
AVLTree Height:25
AVLTree Size:2997882
============================
RBTree Find:1548347
AVLTree Find:1466679
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

可以看到红黑树比AVL树要高，红黑树的旋转次数比AVL树要少35万次左右，查找的时间差不多。

现实中，其实红黑树和AVL树的性能是差不多的，但是大家一般用的都是红黑树，比如set和map的底层就是由红黑树实现的。

OKOK，红黑树就到这里。如果你对Linux和C++也感兴趣的话，可以看看我的主页哦。下面是我的github主页，里面记录了我的学习代码和leetcode的一些题的题解，有兴趣的可以看看。

Xpccccc的github主页

本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】