文档章节

动态查找---->红黑树(Red-Black Tree)

小强斋太
 小强斋太
发布于 2016/11/09 20:07
字数 725
阅读 1
收藏 0

红黑树 (Red-Black Tree)

 

红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组。它是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的: 它可以在O(logn)时间内做查找,插入和删除,这里的n是树中元素的数目。包含n个内部节点的红黑树的高度是 O(log(n))。

一、性质

红黑树是每个节点都带有颜色属性的二叉查找树,颜色为红色黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3. 所有叶子都是黑色(叶子是NIL节点)。

性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。

这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树

要知道为什么这些特性确保了这个结果,注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点,最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点,这就表明了没有路径能多于任何其他路径的两倍长。

二、操作

因为每一个红黑树也是一个特化的二叉查找树,因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而,在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的属性需要少量(O(logn))的颜色变更(实际是非常快速的)和不超过三次树旋转(对于插入操作是两次)。虽然插入和删除很复杂,但操作时间仍可以保持为 O(log n) 次。

2.1插入:

 

2.2删除:

 

 

本文转载自:http://www.cnblogs.com/xqzt/archive/2013/04/06/5637104.html

共有 人打赏支持
小强斋太
粉丝 0
博文 181
码字总数 0
作品 0
广州
常见数据结构(二)-树(二叉树,红黑树,B树)

常见数据结构(二)-树(二叉树,红黑树,B树) 标签: algorithms [TOC] 本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课...

brianway
2016/10/14
763
2
Red-Black Tree 的Java实现

Every node is either red or black. The root is black. Every leaf (NIL) is black. If a node is red, then both its children are black. For each node, all paths from the node to de......

Storm.X
2010/12/19
0
0
详解TreeMap的红黑树实现

红黑树 二叉查找树 二叉查找树(Binary Search Tree,简称BST)是一棵二叉树,它的左子节点的值比父节点的值要小,右节点的值要比父节点的值大。它的高度决定了它的查找效率。 BST存在的主要...

那位先生
2016/12/16
33
0
JDK TreeMap Red-Black Tree

介绍另一种平衡二叉树:红黑树(Red Black Tree),红黑树由Rudolf Bayer于1972年发明,当时被称为平衡二叉B树(symmetric binary B-trees),1978年被Leonidas J. Guibas 和 Robert Sedgewi...

zuoer
2011/12/18
0
0
读书笔记-红黑树

前言 大家好,头回写博客,欢迎批评,以后我会尽量做到一个月2更,最近在重新温故算法。今日提供读书笔记红黑树 目的 记录所学,温故知新 Java中对应的结构 TreeMap,以下是自己安装书中实现...

温安适
2016/11/27
812
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

移除或自定义 WordPress 仪表盘欢迎面板

第一次登录 WordPress 后台仪表盘页面,默认都会显示 WordPress 的欢迎面板: 如果我们要移除这个面板,在主题的 functions.php 中添加下面的代码即可: 12 //移除 WordPress 仪表盘欢迎面...

james_laughing
21分钟前
0
0
HashMap实现原理及源码分析

HashMap实现原理及源码分析   哈希表(hash table)也叫散列表,是一种非常重要的数据结构,应用场景及其丰富,许多缓存技术(比如memcached)的核心其实就是在内存中维护一张大的哈希表,...

DemonsI
25分钟前
0
0
eggjs学习笔记

快速初始化 生成项目(要求最低的node版本8.x) npm i egg-init -gegg-init egg-example --type=simplecd egg-examplenpm i 启动项目 npm run dev 配置 环境配置会覆盖默认配置 config...

别人说我名字很长
28分钟前
1
0
Winform Timer控件时间间隔

sender as System.Timers.Timer).Interval = 23 * 60 * 60 * 1000.0;//将时间间隔改为23小时,23小时后重新发生timer_Elapsed事件。 //60000:时间间隔1分钟,300000:时间间隔5分钟,600000:...

笑丶笑
29分钟前
0
0
在win10系统下怎样快速切换任务视图

切换窗口:Alt + Tab 任务视图:Win + Tab (松开键盘界面不会消失) 切换任务视图:Win + Ctrl +左/右 创建新的虚拟桌面:Win + Ctrl + D 关闭当前虚拟桌面:Win + Ctrl + F4...

SummerGao
33分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部