算法-红黑树
本文共 5327 字，大约阅读时间需要 17 分钟。
之前的一片博客中关于二叉查找树在最差的情况是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，如需转载请自行联系原作者
你可能感兴趣的文章
[转] Win7下安装VC6.0的完美解决方案
查看>>
Python DayDayUp —— 字符串操作（二）
查看>>
【转】Update plug-in ant from 1.7 to 1.8
查看>>
利用@media screen实现网页布局的自适应
查看>>
ajax取json数据——简单的
查看>>
css一像素问题
查看>>
使用Eclipse进行远程调试【转】
查看>>
【POJ】2418 Hardwood Species
查看>>
powerDesigner16.5 -导入数据库表结构
查看>>
css3动画：执行前不显示，执行后显示
查看>>
passport.js学习笔记
查看>>
PHP - 用户异常断开连接，脚本强制继续执行，异常退出回调
查看>>
常见端口 HTTP代码
查看>>
eclipse进行Debug的时候，发出“java breakpoint unable to install breakpoint”错误
查看>>
从Hub与Router入手，了解广播域与冲突域
查看>>
[Android Studio] Android Studio常用快捷键
查看>>
[Android Security] Smali和逆向分析
查看>>
scroll 方法 获取滚轴距离顶部高度
查看>>
页面间(窗口间)的取值赋值及获取iframe下的window对象
查看>>
javascript 数组以及对象的深拷贝（复制数组或复制对象）的方法
查看>>