编程开发 购物 网址 游戏 小说 歌词 地图 快照 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 开发 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
移动开发 架构设计 编程语言 互联网 开发经验 Web前端 开发总结
开发杂谈 系统运维 研发管理 数据库 云 计 算 Java开发
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
  编程开发知识库 -> 互联网 -> 二叉查找树(BST) | 平衡二叉查找树(AVL) | 红黑树(RBT) -> 正文阅读
 

[互联网]二叉查找树(BST) | 平衡二叉查找树(AVL) | 红黑树(RBT)[第1页]

二叉查找树(BST)
特点:对任意节点而言,左子树(若存在)的值总是小于本身,而右子(若存在)的值总是大于本身。
查找:从根开始,小的往左找,大的往右找,不大不小的就是这个节点了;
插入:从根开始,小的往左,大的往右,直到叶子,就插入,
时间复杂度期望为Ο(logn);
删除:如果是叶子节点,直接删除;如果不是,则去找这个节点左子树的最大值,与之交换;如果交换后还不是叶子节点就继续找做字数的最大值,重复操作至成为叶子节点,删除;
左子树如果不存在就去找右子树的最小节点,交换,重复操作,与上同理;
平衡二叉查找树(AVL)
二叉查找树中的Ο(logn),是个期望值,如果出现比较差的情况,比如根节点为1,后依次插入2、3、4、5、6、7、8、9.。。。。那么,数据结构上来说,树就退化为链表了,但概念上还是二叉查找树,那么操作的时间复杂度也就变为了O(n),导致的原因为树不平衡,不对称;
概念:
左高 = 左节点空 ? 0 : (左节点高+1)
右高 = 右节点空 ? 0 : (右节点高+1)
AVL的定义为:ABS(左高 - 右高) <= 1;(ABS求绝对值):即任意节点的左右高的绝对值之差为0/1;
如何是二叉查找树在添加数据的同时保持平衡?
基本思想就是:当在二叉排序树中插入一个节点时,首先检查是否因插入而破坏了平衡,若 破坏,则找出其中的最小不平衡二叉树,在保持二叉排序树特性的情况下,调整最小不平衡子树中节点之间的关系,以达 到新的平衡。所谓最小不平衡子树 指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。
平衡二叉树的添加
LL型:X节点的左高本来就大,插入点还在左子树的左子树上;

直接以X的左子树根节点为中心向右旋转;
RR型:X节点的右高本来就大,插入点还在右子树的右子树上;

直接以X的右子树根节点为中心向左旋转;
LR型:以上同理不赘述

先将左子树左旋转,再整体右旋转;
RL型:

先将右子树右旋转,再整体左旋转;
平衡二叉树的删除:
从平衡二叉树中删除节点更为复杂。首先第一步需要找到要删除的节点x,并分情况进行处理:
如果要删除的节点为叶子节点,就找到了要删除的节点
如果要删除的节点为只有一棵子树的节点就找到了要删除的节点
如果要删除的节点既有左子树,又有右子树。。。
与二叉查找树同理:
如果是叶子节点,直接删除;如果不是,则去找这个节点左子树的最大值,与之交换;如果交换后还不是叶子节点就继续找做字数的最大值,重复操作至成为叶子节点,删除;
左子树如果不存在就去找右子树的最小节点,交换,重复操作,与上同理;
然后判断是否破坏了平衡二叉树的平衡;
关键点在于调整过程:
类似于插入,不过也有区别;
以从节点X的左子树删除节点导致其左子树高度降低而需要调整为例进行分析:
删除的左子树,要调整,影响的是右子树,所以要看右子树的状态;
X的右子树的平衡因子为-1;

以X为轴,直接进行左旋操作;
X的右子树的平衡因子为0;

以X为轴,直接进行左旋操作;
X的右子树的平衡因子为1;

先将X的右子树右旋,再以X为轴左旋;
平衡二叉树性能分析
平衡二叉树的性能优势:很显然,平衡二叉树的优势在于不会出现普通二叉查找树的最差情况。其查找的时间复杂度为O(logN)。
平衡二叉树的缺陷:
(1) 很遗憾的是,为了保证高度平衡,动态插入和删除的代价也随之增加。
(2) 所有二叉查找树结构的查找代价都与树高是紧密相关的,能否通过减少树高来进一步降低查找代价呢。我们可以通过多路查找树的结构来做到这一点。
(3) 在大数据量查找环境下(比如说系统磁盘里的文件目录,数据库中的记录查询 等),所有的二叉查找树结构(BST、AVL、RBT)都不合适。如此大规模的数据量(几G数据),全部组织成平衡二叉树放在内存中是不可能做到的。那么把这棵树放在磁盘中吧。问题就来了:假如构造的平衡二叉树深度有1W层。那么从根节点出发到叶子节点很可能就需要1W次的硬盘IO读写。大家都知道,硬盘的机械部件读写数据的速度远远赶不上纯电子媒体的内存。 查找效率在IO读写过程中将会付出巨大的代价。在大规模数据查询这样一个实际应用背景下,平衡二叉树的效率就很成问题了。
红黑树(Red-Black Tree ( RBT))
红黑树实际上是AVL的一种变形,但是其比AVL(平衡二叉搜索树)具有更高的插入效率,当然查找效率会平衡二叉树稍微低一点点,毕竟平衡二叉树太完美了。但是这种查找效率的损失是非常值得的。它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n是树中元素的数目。
性质1 节点是红色或黑色。
性质2 根节点是黑色。
性质3 每个叶节点(NIL节点,空节点)是黑色的。
性质4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些约束的好处是:保持了树的相对平衡,同时又比AVL的插入删除操作的复杂性要低许多。
注意的点:
红黑树和AVL树的区别在于它使用颜色来标识结点的高度,它所追求的是局部平衡而不是AVL树中的非常严格的平衡。
红黑树和平衡二叉树区别如下:
1、红黑树放弃了追求完全平衡,追求大致平衡,在与平衡二叉树的时间复杂度相差不大的情况下,保证每次插入最多只需要三次旋转就能达到平衡,实现起来也更为简单。
2、平衡二叉树追求绝对平衡,条件比较苛刻,实现起来比较麻烦,每次插入新节点之后需要旋转的次数不能预知。
最小二叉平衡树的节点的公式如下 F(n)=F(n-1)+F(n-2)+1 这个类似于一个递归的数列,可以参考Fibonacci数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量。
  互联网 最新文章
Stanford 英文词性标注(Part-of-speech)缩
基于窗口的实时统计
求解矩阵最短路径问题
SSL握手通信详解及linux下c/c++ SSL Socket
关于服务器上(Docker中)运行Java程序时区
python爬虫系列(六):强大的beautifulsou
[计算机网络笔记]第四部分——网络层 选路算
11.28 北京,念腾讯暑假,不思则惘吧!
web安全之
滑块验证码识别 java版本
上一篇文章      下一篇文章      查看所有文章
加:2017-09-07 22:32:59  更:2017-09-07 22:35:02 
VC(MFC) Delphi VB C++(C语言) C++ Builder 其它开发语言 云计算 Java开发 .Net开发 IOS开发 Android开发 PHP语言 JavaScript
ASP语言 HTML(CSS) HTML5 Apache MSSQL数据库 Oracle数据库 PowerBuilder Informatica 其它数据库 硬件及嵌入式开发 Linux开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2018年7日历
2018-7-19 4:07:51
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  编程开发知识库