之前的一片博客中关于二叉查找树在最差的情况是O(n)，不能完全的达到O(lgN)，在一棵还有N个节点的树中，如果树的高度为lgN,那么我们可以在lgN次比较内结束查找，不过动态插入保证树的平衡性代码量和额外的空间都会是很大的代价。为了保证查找树的平衡性，我们可以允许树中的节点可以保存多个键，标准的二叉树的节点我们可以称之为2-节点（一个键和两条链接），3-节点（含有两个键和三条链接），这就是2-3树。一个2-结点左链接小于该结点，右链接大于该节点。3-节点左链接小于所有键，中链介于两个键之间，右链大于所有键。
2-3树能够在常数级别实现数亿数字的查找和插入，不过实现起来需要维护两种不同的数据节点，而且中间需要大量的代码控制变换，因为就有2-3树的改进版红黑树出现了，所有的节点都是统一的2-节点，3-节点拆分成了2-节点中间通过红线链接，正常的链接之间是黑色，红黑树因此得名。
实现树最基本的就是节点，节点定义代码:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
@interface
RedBlackNode:
NSObject
@property
(strong,
nonatomic
)
NSString
*key;
//键
@property
(strong,
nonatomic
)
NSString
*value;
//值
@property
(strong,
nonatomic
) RedBlackNode *left;
//左子树的节点
@property
(strong,
nonatomic
) RedBlackNode *right;
//右子树的节点
@property
(assign,
nonatomic
)
NSInteger
childCount;
//以该结点为根的自述中的结点总数
@property
(assign,
nonatomic
) RedBlackEnum color;
//链接颜色
-(
void
)initWithData:(
NSString
*)key value:(
NSString
*)value childCount:(
NSInteger
)childCount color:(RedBlackEnum)color;
@end
|
跟之前二叉查找树之间最大区别在于多了颜色的控制:
|
1
2
3
4
5
6
|
-(
void
)initWithData:(
NSString
*)key value:(
NSString
*)value childCount:(
NSInteger
)childCount color:(RedBlackEnum)color{
self
.key=key;
self
.value=value;
self
.childCount=childCount;
self
.color=color;
}
|
红黑树的查找和二叉查找树一样代码一样，不过最大的不同就是插入有所不同，插入比较复杂，需要的辅助方法比较多:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
@interface
RedBlackTree :
NSObject
@property
(strong,
nonatomic
) RedBlackNode *root;
//红黑树的根节点
-(
NSString
*)get:(
NSString
*)key;
//获取键对应的值
-(
void
)put:(
NSString
*)key value:(
NSString
*)value;
//插入键值对
//判断是否是红色链接
-(Boolean)isRed:(RedBlackNode *)node;
//左旋转
-(RedBlackNode *)rotateLeft:(RedBlackNode *)node;
//右旋转
-(RedBlackNode *)rotateRight:(RedBlackNode *)node;
//反转颜色
-(
void
)flipColors:(RedBlackNode *)node;
@end
|
红黑树主要实现代码:
|
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
|
@implementation
RedBlackTree
-(
NSString
*)get:(
NSString
*)key{
return
[
self
getByKey:
self
.root key:key];
}
-(
NSString
*)getByKey:(RedBlackNode *)node key:(
NSString
*)key{
//在node为根结点的子树种查找并返回key所对应的值
//如果找不到返回null
if
(node==
nil
) {
return
nil
;
}
//左右节点进行比较，每个结点的键值大于左子树的结点值小于右子树的结点值
NSInteger
compare=[key integerValue]-[node.key integerValue];
if
(compare>0) {
return
[
self
getByKey:node.right key:key];
}
else
if
(compare<0){
return
[
self
getByKey:node.left key:key];
}
else
{
return
node.value;
}
}
//http://www.cnblogs.com/xiaofeixiang
-(
void
)put:(
NSString
*)key value:(
NSString
*)value{
//查找键值，找到则更新它的值，否则为它创建一个新的结点
self
.root=[
self
putNode:
self
.root key:key value:value];
self
.root.color=Black;
}
-(RedBlackNode *)putNode:(RedBlackNode *)node key:(
NSString
*)key value:(
NSString
*)value{
if
(node==
nil
) {
RedBlackNode *newNode=[[RedBlackNode alloc]init];
[newNode initWithData:key value:value childCount:1 color:Red];
return
newNode;
}
NSInteger
compare=[key integerValue]-[node.key integerValue];
if
(compare>0) {
node.right=[
self
putNode:node.right key:key value:value];
}
else
if
(compare<0){
node.left=[
self
putNode:node.left key:key value:value];
}
else
{
node.value=value;
}
//将含有红色右链接的3-结点(4-结点)向左旋转
if
([
self
isRed:node.right]&&![
self
isRed:node.left]) {
node=[
self
rotateLeft:node];
}
//连续红色左链接向右旋转
if
([
self
isRed:node.left]&&[
self
isRed:node.left.left]) {
node=[
self
rotateRight:node];
}
//红色链接向上传递
if
([
self
isRed:node.left]&&[
self
isRed:node.right]) {
[
self
flipColors:node];
}
node.childCount=[
self
childSizeCount:node.left]+[
self
childSizeCount:node.right]+1;
return
node;
}
-(
NSInteger
)childSize{
return
[
self
childSizeCount:
self
.root];
}
-(
NSInteger
)childSizeCount:(RedBlackNode *)node{
if
(node==
nil
) {
return
0;
}
else
{
return
node.childCount;
}
}
-(Boolean)isRed:(RedBlackNode *)node{
if
(!node) {
return
false
;
}
return
node.color==Red;
}
//左旋转，将较大的值作为根节点
-(RedBlackNode *)rotateLeft:(RedBlackNode *)node{
RedBlackNode *rightNode=node.right;
node.right=rightNode.left;
rightNode.left=node;
rightNode.color=node.color;
node.color=Red;
rightNode.childCount=node.childCount;
node.childCount=[
self
childSizeCount:node.left]+[
self
childSizeCount:node.right]+1;
return
rightNode;
}
//右旋转，将较小的值作为根节点
-(RedBlackNode *)rotateRight:(RedBlackNode *)node{
RedBlackNode *leftNode=node.left;
node.left=leftNode.right;
leftNode.right=node;
leftNode.color=node.color;
node.color=Red;
leftNode.childCount=node.childCount;
node.childCount=[
self
childSizeCount:node.left]+[
self
childSizeCount:node.right]+1;
return
leftNode;
}
//反转颜色
-(
void
)flipColors:(RedBlackNode *)node{
node.color=Red;
node.left.color=Black;
node.right.color=Black;
}
@end
|
红黑树测试代码:
|
1
2
3
4
5
6
7
|
RedBlackTree *redBlackTree=[[RedBlackTree alloc]init];
[redBlackTree put:@
"3"
value:@
"FlyElephant"
];
[redBlackTree put:@
"9"
value:@
"原文地址:http://www.cnblogs.com/xiaofeixiang"
];
[redBlackTree put:@
"10"
value:@
"博客园"
];
[redBlackTree put:@
"0"
value:@
"技术交流:228407086"
];
NSString
*temp=[redBlackTree get:@
"9"
];
NSLog
(@
"红黑树:%@"
,temp);
|
测试效果:
红黑树能保证在最差的情况查找和删除，删除都是对数级别的，在过亿的数据处理中，红黑树能够在几十次比较之内完成这些操作，红黑树的魅力让人折服。
本文转自Fly_Elephant博客园博客，原文链接：http://www.cnblogs.com/xiaofeixiang/p/4660030.html，如需转载请自行联系原作者
