(精华)2020年8月27日 数据结构与算法解析(红黑树)
【摘要】
红黑树定义：它或者是一颗空树，或者是具有一下性质的二叉查找树
1）：每个节点或是红的，或是黑的。
2）：根节点是黑的。
3）：每个叶节点（NIL）是黑的。（所有NULL结点称为叶子节点，且认为颜色为...
红黑树定义：它或者是一颗空树，或者是具有一下性质的二叉查找树
1）：每个节点或是红的，或是黑的。
2）：根节点是黑的。
3）：每个叶节点（NIL）是黑的。（所有NULL结点称为叶子节点，且认为颜色为黑）
4）：如果一个节点是红的，则他的两个子节点是黑的。
5）：对每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点。
红黑树用在关联数组、字典的实现上。需du要的空间zhi比散列表小。 任何键值对应,需要dao随机存储和键有序的情况都可以用。
class TreeNode<T>
{
public T Data { get; set; }
public TreeNode<T> LeftChild { get; set; }
public TreeNode<T> RightChild { get; set; }
public TreeNode<T> Parent { get; set; }
public int Color { get; set; }
public TreeNode(T data)
{
Data = data;
Parent = null;
LeftChild = null;
RightChild = null;
}
public TreeNode(T newData, TreeNode<T> parent)
{
Data = newData;
Parent = parent;
LeftChild = null;
RightChild = null;
}
}
internal class RedBlackTree<T> where T : IComparable<T>, IEquatable<T>, new()
{
public TreeNode<T> Root { get; private set; }
public int Size { get; private set; }
public RedBlackTree()
{
Root = null;
Size = 0;
}
private static TreeNode<T> Add(TreeNode<T> to, TreeNode<T> newNode)
{
if (newNode.Data.CompareTo(to.Data) < 0)
{
if (to.LeftChild != null) return Add(to.LeftChild, newNode);
newNode.LeftChild = null;
newNode.RightChild = null;
to.LeftChild = newNode;
newNode.Color = 1;
newNode.Parent = to;
return newNode;
}
if (to.RightChild != null) return Add(to.RightChild, newNode);
newNode.LeftChild = null;
newNode.RightChild = null;
to.RightChild = newNode;
newNode.Color = 1;
newNode.Parent = to;
return newNode;
}
private void LeftTurn(TreeNode<T> node)
{
if (node.RightChild == null) return;
var child = node.RightChild;
node.RightChild = child.LeftChild;
if (child.LeftChild != null) child.LeftChild.Parent = node;
child.Parent = node.Parent;
if (node.Parent == null) Root = child;
else
{
if (node == node.Parent.LeftChild)
node.Parent.LeftChild = child;
else
node.Parent.RightChild = child;
}
child.LeftChild = node;
node.Parent = child;
}
private void RightTurn(TreeNode<T> node)
{
if (node.LeftChild == null) return;
var child = node.LeftChild;
node.LeftChild = child.RightChild;
if (child.RightChild != null) child.RightChild.Parent = node;
child.Parent = node.Parent;
if (node.Parent == null) Root = child;
else
{
if (node == node.Parent.RightChild) node.Parent.RightChild = child;
else node.Parent.LeftChild = child;
}
child.RightChild = node;
node.Parent = child;
}
public void Insert(TreeNode<T> node)
{
if (Root == null)
{
Root = node;
Root.Color = 0;
Root.LeftChild = null;
Root.RightChild = null;
Root.Parent = null;
}
else
{
var addedNode = Add(Root, node);
while (addedNode != Root && addedNode.Parent.Color == 1)
{
if (addedNode.Parent == addedNode.Parent.Parent.LeftChild)
{
var y = addedNode.Parent.Parent.RightChild;
if (y != null && y.Color == 1)
{
addedNode.Parent.Color = 0;
y.Color = 0;
addedNode.Parent.Parent.Color = 1;
addedNode = addedNode.Parent.Parent;
}
else
{
if (addedNode == addedNode.Parent.RightChild)
{
addedNode = addedNode.Parent;
LeftTurn(addedNode);
}
addedNode.Parent.Color = 0;
addedNode.Parent.Parent.Color = 1;
RightTurn(addedNode.Parent.Parent);
}
}
else
{
var y = addedNode.Parent.Parent.LeftChild;
if (y != null && y.Color == 1)
{
addedNode.Parent.Color = 0;
y.Color = 0;
addedNode.Parent.Parent.Color = 1;
addedNode = addedNode.Parent.Parent;
}
else
{
if (addedNode == addedNode.Parent.Parent.LeftChild)
{
addedNode = addedNode.Parent;
RightTurn(addedNode);
}
addedNode.Parent.Color = 0;
addedNode.Parent.Parent.Color = 1;
LeftTurn(addedNode.Parent.Parent);
}
}
}
}
Root.Color = 0;
}
private static TreeNode<T> Min(TreeNode<T> node)
{
while (node.LeftChild != null) node = node.LeftChild;
return node;
}
private static TreeNode<T> Next(TreeNode<T> node)
{
if (node.RightChild != null) return Min(node.RightChild);
var y = node.Parent;
while (y != null && node == y.RightChild)
{
node = y;
y = y.Parent;
}
return y;
}
private void FixUp(TreeNode<T> node)
{
while (node != Root && node.Color == 0)
{
if (node == node.Parent.LeftChild)
{
var w = node.Parent.RightChild;
if (w.Color == 1)
{
w.Color = 0;
node.Parent.Color = 1;
LeftTurn(node.Parent);
w = node.Parent.RightChild;
}
if (w.LeftChild.Color == 0 && w.RightChild.Color == 0)
{
w.Color = 1;
node = node.Parent;
}
else
{
if (w.RightChild.Color == 0)
{
w.LeftChild.Color = 0;
w.Color = 1;
RightTurn(w);
w = node.Parent.RightChild;
}
w.Color = node.Parent.Color;
node.Parent.Color = 0;
w.RightChild.Color = 0;
LeftTurn(node.Parent);
node = Root;
}
}
else
{
var w = node.Parent.LeftChild;
if (w.Color == 1)
{
w.Color = 0;
node.Parent.Color = 1;
RightTurn(node.Parent);
w = node.Parent.LeftChild;
}
if (w.RightChild.Color == 0 && w.LeftChild.Color == 0)
{
w.Color = 1;
node = node.Parent;
}
else
{
if (w.LeftChild.Color == 0)
{
w.RightChild.Color = 0;
w.Color = 1;
LeftTurn(w);
w = node.Parent.LeftChild;
}
w.Color = node.Parent.Color;
node.Parent.Color = 0;
w.LeftChild.Color = 0;
RightTurn(node.Parent);
node = Root;
}
}
}
node.Color = 0;
}
public void Delete(TreeNode<T> node)
{
TreeNode<T> y;
if (node.LeftChild == null || node.RightChild == null)
y = node;
else
y = Next(node);
var x = y.LeftChild ?? y.RightChild;
if (x == null)
{
node.Data = y.Data;
if (y.Parent == null) return;
if (y.Parent.LeftChild == y) y.Parent.LeftChild = null;
else y.Parent.RightChild = null;
return;
}
x.Parent = y.Parent;
if (y.Parent == null) Root = x;
else
{
if (y == y.Parent.LeftChild) y.Parent.LeftChild = x;
else y.Parent.RightChild = x;
}
if (y != node)
{
node.Data = y.Data;
}
if (y.Color == 0) FixUp(x);
}
private static TreeNode<T> SearchInSubTree(TreeNode<T> topNode, T data)
{
if (data.Equals(topNode.Data))
return topNode;
if (data.CompareTo(topNode.Data) < 0 && topNode.LeftChild != null)
return SearchInSubTree(topNode.LeftChild, data);
if (data.CompareTo(topNode.Data) > 0 && topNode.RightChild != null)
return SearchInSubTree(topNode.RightChild, data);
return null;
}
public bool Search(T data)
{
return SearchInSubTree(Root, data) != null;
}
public TreeNode<T> SearchNode(T data)
{
return SearchInSubTree(Root, data);
}
public IEnumerator<T> GetEnumerator()
{
if (Root == null)
yield break;
var current = Min(Root);
yield return current.Data;
while (Next(current) != null)
{
current = Next(current);
yield return current.Data;
}
}
public IEnumerator<TreeNode<T>> DfsEnum()
{
var verts = new Stack<TreeNode<T>>();
if (Root == null)
yield break;
verts.Push(Root);
var previous = 0;
while (verts.Count != 0)
{
var current = verts.Peek();
if (current.LeftChild == null && current.RightChild == null)
{
verts.Pop();
yield return current;
if (current.Parent != null)
previous = current == current.Parent.LeftChild ? 1 : 2;
else
yield break;
continue;
}
switch (previous)
{
case 0:
if (current.LeftChild == null)
{
previous = 1;
continue;
}
verts.Push(current.LeftChild);
previous = 0;
break;
case 1:
if (current.RightChild == null)
{
verts.Pop();
yield return current;
if (current.Parent != null)
{
previous = current == current.Parent.LeftChild ? 1 : 2;
continue;
}
yield break;
}
verts.Push(current.RightChild);
previous = 0;
break;
case 2:
verts.Pop();
yield return current;
if (current.Parent != null)
previous = current == current.Parent.LeftChild ? 1 : 2;
else
yield break;
break;
}
}
}
public IEnumerator<TreeNode<T>> BfsEnum()
{
var verts = new Queue<TreeNode<T>>();
verts.Enqueue(Root);
while (verts.Count != 0)
{
var current = verts.Dequeue();
yield return current;
if (current.LeftChild != null)
verts.Enqueue(current.LeftChild);
if (current.RightChild != null)
verts.Enqueue(current.RightChild);
}
}
}
- 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
文章来源: codeboy.blog.csdn.net，作者：愚公搬代码，版权归原作者所有，如需转载，请联系作者。
原文链接：codeboy.blog.csdn.net/article/details/108192264
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）