注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Mihooke's blog

IT之恋

 
 
 

日志

 
 

红黑树介绍  

2017-03-01 18:35:39|  分类: C++ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
红黑树,一种二叉查找树。
二叉查找树,有如下性质:
  • 若任意节点的左子树不为空,则左子树的值均小于它的根节点的值
  • 若任意节点的右子树不为空,则右子树的值均大于它的根节点的值
  • 任意节点的左、右子树均为二叉查找树
  • 没有键值相等的节点
  • 空树也是二叉查找树
那么,红黑树就是在二叉查找树的每个结点上增加一个存储位来表示节点的颜色,只能是红色或黑色,通过对任何一个节点着色方式的限制,红黑树确保没有一条路径比其它路径长出两倍。它有如下性质:
  • 每个节点要么是红的,要么是黑的
  • 根节点是黑的
  • 每个叶子节点也是黑的
  • 如果一个节点是红色的,那么它的左右儿子节点是黑的
  • 对于任何一个节点,其到叶子节点的每条路径都包含相同数目的黑节点。
这样的特性保证了红黑树相对平衡,从而使得查找、删除、增加操作时间复杂度最坏为O(logn)。
当对红黑树进行插入删除操作时,会破坏树的结构,从而红黑性质也会破坏,通过对树的旋转和重新着色来调整。
STL中set和map容器都是采用红黑树的结构来维护的,具有自动调整树结构的特性。
这就是为什么set和map的插入删除操作效率比其他序列容器要高的原因,插入和删除的时候,只要变动对应指针指向即可,,并不需要做内存拷贝和内存移动;既然内存没有变化,那么相应的iterator也没有变化了,还是保存先前的值,所以在插入和删除操作之后,先前保存的iterator并不会失效
  评论这张
 
阅读(40)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017