软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 架构设计 -> 红黑树、插入删除操作 -> 正文阅读

[架构设计]红黑树、插入删除操作


二叉排序树


一棵自平衡的二叉排序树(二叉搜索树)
生成二叉排序树的过程是非常容易失衡的,最坏的情况就是一边倒(只有右/左子树),这样会导致二叉树的检索效率大大降低(O(n))。
为了维持二叉树的平衡,有各种的算法,如:AVL,SBT,伸展树,TREAP ,红黑树等等。

[img]http://img.blog.csdn.net/20140523092231125?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY2hlbnNzeQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast

红黑树


红黑树需要满足5条性质:
- 节点非红即黑
- 根节点是黑色
- 所有NULL结点称为叶子节点,且认为颜色为黑
- 所有红节点的子节点都为黑色,一条路径上不能出现相邻的两个红色结点
- 从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点
比如:
[img]http://pic002.cnblogs.com/images/2011/330710/2011120115382993.png
衍生性质:树上的最长路径不可能会大于2倍最短路径。
解释:因为第1条该树上的节点非红即黑,由于第4条该树上不允许存在两个连续的红节点,那么对于从一个节点到其叶子节点的一条最长的路径一定是红黑交错的,那么最短路径一定是纯黑色的节点;而又第5条从任一节点到其叶子节点的所有路径上都包含相同数目的黑节点,这么来说最长路径上的黑节点的数目和最短路径上的黑节点的数目相等!而又第2条根结点为黑、第3条叶子节点是黑,那么可知:最长路径<=2*最短路径
注:红黑树不是平衡二叉树,区别:

1、红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。
2、平衡二叉树追求绝对平衡,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知。
平衡二叉树又被称为AVL树(有别于AVL算法),且具有以下性质:它是一
棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
构造与调整方法平衡二叉树的常用算法有红黑树、AVL、Treap等。
最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1。
这个类似于一个递归的数列,可以参考Fibonacci数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量。

红黑树基本操作


左旋、右旋、着色
[img]http://img.blog.csdn.net/20140523092135453?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY2hlbnNzeQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[img]http://img.blog.csdn.net/20140523092154062?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvY2hlbnNzeQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast

插入


首先,为了保证根节点到叶节点黑节点数目相同,每次插入的都是红节点
如果有两个红节点相邻,那么需要进行调整:
情形1:
树为空,直接插入根结点的位置,把节点颜色改为黑
情形2:
插入点的父节点为黑,那么不会破坏任何性质,直接插入。
下面讨论插入点父节点为红情况,共三种,插入点为N:
情形3:
[img]http://pic002.cnblogs.com/images/2011/330710/2011120116425251.png
如图换颜色,递归向上插入G
情形4:
[img]http://pic002.cnblogs.com/images/2011/330710/2011120117212591.png
情形5(转成情形4):
[img]http://pic002.cnblogs.com/images/2011/330710/2011120117480873.png

删除


我们删除一个节点,实际上删除的是叶节点(替代点)。
首先将删除点和替代点交换,然后删除替代点。
替代点是被删除点中序遍历的上一个或下一个节点,所以替代点一定是一棵子树的最左子或最右子。
所以,替代点一定至少有一个子节点是叶子节点。
五种情形,删除的是N:
情形1:
[img]http://pic002.cnblogs.com/images/2011/330710/2011120118423260.png
这时候删除N,需要进一步递归删除(P为父元素根,删除N的操作),因为破环了每条路径黑节点数目相同。
情形2:
[img]http://pic002.cnblogs.com/images/2011/330710/2011120121290823.png
情形3:
[img]http://pic002.cnblogs.com/images/2011/330710/2011120121315179.png
情形4:
[img]http://pic002.cnblogs.com/images/2011/330710/2011120121403620.png
情形5:变为情形4
[img]http://pic002.cnblogs.com/images/2011/330710/2011120121420449.png
......显示全文...
    点击查看全文


上一篇文章      下一篇文章      查看所有文章
2016-04-01 16:50:07  
架构设计 最新文章
Opengl教程之读取obj并绘制在picturecontro
读《企业应用架构模式》第五章并发
StepbyStepintoSpring(IOC)
设计模式(2)用例图之一
使用实体组件系统(ECS)开发”吃方块”游戏实
编程学习之简单工厂模式与策略模式
Invalidprojectdescription.
基于Redis实现分布式消息队列(2)
《开源框架那点事儿15》:借船下海还是造船
原型模式——浅复制和深复制
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年1日历
2018-1-17 17:15:58
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --