268-C++ 红黑树RBTree_c++ rbtree

最下面的黑色节点是哨兵节点
通常面试的时候都不给出头节点，有头节点会使红黑树变的更加容易


红黑树能不能给出三种颜色？就相当于是AVL树，AVL树是三种状态

RB树只要求是大致平衡的，不想AVL树是完全平衡的

下面两个图是等价的，所有路径都包含相同数目的黑色节点

每次新建节点的默认颜色都是红色

typedef enum {RED = 0,BLACK = 1}ColorType;
typedef int KeyType;
typedef struct rb_node
{
    rb_node* leftchild;
    rb_node* parent;
    rb_node* rightchild;
    ColorType color;
    KeyType key;
}rb_node,*RBTree;
rb_node* BuyNode();
static rb_node* Nil = BuyNode();//哨兵节点
rb_node* BuyNode()
{
    rb_node* s = (rb_node*)malloc(sizeof(rb_node));
    if (nullptr == s) exit(1);
    memset(s, 0, sizeof(rb_node));
    s->leftchild = Nil;//指向哨兵节点
    s->rightchild = Nil;//指向哨兵节点
    s->color = RED;
    return s;
}
rb_node* MakeRoot(KeyType kx)
{
    rb_node* root = BuyNode();
    root->color = BLACK;
    root->key = kx;
    return root;
}
//左单旋
void RotateLeft(rb_node*& tree, rb_node* ptr)
{
    rb_node* newroot = ptr->rightchild;
    newroot->parent = ptr->parent;
    ptr->rightchild = newroot->leftchild;//1
    if (newroot->leftchild != nullptr)
    {
        newroot->leftchild->parent = ptr;//2
    }
    newroot->leftchild = ptr;
    if (ptr == tree)
    {
        tree = newroot;
    }
    else
    {
        if (ptr->parent->leftchild == ptr)
        {
            ptr->parent->leftchild = newroot;
        }
        else
        {
            ptr->parent->rightchild = newroot;
        }
    }
    ptr->parent = newroot;//3
}
//右单旋
void RotateRight(rb_node*& tree, rb_node* ptr)
{
    rb_node* newroot = ptr->leftchild;//1
    newroot->parent = ptr->parent;//newroot的双亲更新a
    ptr->leftchild = newroot->rightchild;//2 ptr左孩子更新
    if (newroot->rightchild != nullptr)
    {
        newroot->rightchild->parent = ptr;//newroot右孩子的双亲更新b
    }
    newroot->rightchild = ptr;//newroot右孩子更新3
    if (ptr == tree)//如果我本身是根
    {
        tree = newroot;//更新根
    }
    else
    {
        if (ptr->parent->leftchild == ptr)
        {
            ptr->parent->leftchild = newroot;
        }
        else
        {
            ptr->parent->rightchild = newroot;
        }
    }
    ptr->parent = newroot;//ptr双亲更新c
}
void PassRBTree(rb_node*& tree, rb_node* p)
{
    rb_node* _X = nullptr;
    for (; p != tree && p->parent->color == RED;)//p!=tree说明有双亲
    {
        if (p->parent->parent->rightchild == p->parent)//p在p爷爷的右边
        {
            _X = p->parent->parent->leftchild;
            if (_X->color == RED)//p爷爷的左孩子是红色，按照两个图等价交换颜色即可
            {
                _X->color = BLACK;
                p->parent->color = BLACK;
                p->parent->parent->color = RED;
                p = p->parent->parent;
            }
            else//p爷爷的左孩子是黑色，只能旋转了
            {//if条件满足，先右旋再左旋，不满足，就左旋
                if (p->parent->leftchild == p)//p在p爷爷的右边，但是p在p双亲的左边，是一个折线
                {
                    p = p->parent;
                    RotateRight(tree, p);
                }
                p->parent->color = BLACK;//p双亲的颜色变成黑
                p->parent->parent->color = RED;//p爷爷的颜色变成红，
                //就形成了红黑红的形式，然后以黑作为根，将第一个红左单旋转下来
                RotateLeft(tree, p->parent->parent);//左单旋
            }
        } 
        else//pa在p双亲的双亲的左边
        {
            _X = p->parent->parent->rightchild;
            if (_X->color == RED)//p爷爷的右孩子是红色，按照两个图等价交换颜色即可
            {
                _X->color = BLACK;
                p->parent->color = BLACK;
                p->parent->parent->color = RED;
                p = p->parent->parent;
            }
            else//p爷爷的左孩子是黑色，只能旋转了
            {//if条件满足，先左旋再右旋，不满足，就右旋
                if (p->parent->rightchild == p)//p在p爷爷的左边，但是p在p双亲的右边，是一个折线
                {
                    p = p->parent;
                    RotateRight(tree, p);
                }
                p->parent->color = BLACK;//p双亲的颜色变成黑
                p->parent->parent->color = RED;//p爷爷的颜色变成红，
                //就形成了红黑红的形式，然后以黑作为根，将第一个红左单旋转下来
                RotateRight(tree, p->parent->parent);//右单旋
            }
        }
    }
    tree->color = BLACK;//退出以后保证根是黑色
}
bool Insert(rb_node*& tree, KeyType kx)
{
    if (tree == nullptr)
    {
        tree = MakeRoot(kx);
        return true;
    }
    rb_node* pa = nullptr;
    rb_node* p = tree;
    while (p != nullptr && p->key != kx)
    {
        pa = p;
        p = kx < p->key ? p->leftchild : p->rightchild;
    }
    if (p != nullptr && p->key == kx)return false;//如果数据重复的话，返回false
    p = BuyNode();
    p->key = kx;
    p->parent = pa;
    if (kx < pa->key)
    {
        pa->leftchild = p;
    }
    else
    {
        pa->rightchild = p;
    }
    PassRBTree(tree, p);
    return true;
}
int main()
{
    int ar[] = { 16,3,7,11,9,26,18,14,15 };
    AVLTree root = nullptr;
    for (auto& x : ar)
    {
        cout << Insert(root, x) << endl;
    }
    InOrder(root);
    cout << endl;
    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
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