这篇文章http://www.cnblogs.com/yangecnu/p/Introduce-Red-Black-Tree.html讲红黑树讲得非常好,直接拿过来放到ITEYE上,
定义
红黑树的主要是像是对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类 型,红色链接,他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的,使用红色链接的两个2- nodes来表示一个3-nodes节点,并且向左倾斜,即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修 改,和普通的二叉查找树相同。
根据以上描述,红黑树定义如下:
红黑树是一种具有红色和黑色链接的平衡查找树,同时满足:
- 红色节点向左倾斜
- 一个节点不可能有两个红色链接
- 整个书完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同。
下图可以看到红黑树其实是2-3树的另外一种表现形式:如果我们将红色的连线水平绘制,那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。
表示
我们可以在二叉查找树的每一个节点上增加一个新的表示颜色的标记。该标记指示该节点指向其父节点的颜色。
private const bool RED = true; private const bool BLACK = false; private Node root; class Node { public Node Left { get; set; } public Node Right { get; set; } public TKey Key { get; set; } public TValue Value { get; set; } public int Number { get; set; } public bool Color { get; set; } public Node(TKey key, TValue value,int number, bool color) { this.Key = key; this.Value = value; this.Number = number; this.Color = color; } } private bool IsRed(Node node) { if (node == null) return false; return node.Color == RED; }
实现
查找
红黑树是一种特殊的二叉查找树,他的查找方法也和二叉查找树一样,不需要做太多更改。
但是由于红黑树比一般的二叉查找树具有更好的平衡,所以查找起来更快。
//查找获取指定的值 public override TValue Get(TKey key) { return GetValue(root, key); } private TValue GetValue(Node node, TKey key) { if (node == null) return default(TValue); int cmp = key.CompareTo(node.Key); if (cmp == 0) return node.Value; else if (cmp > 0) return GetValue(node.Right, key); else return GetValue(node.Left, key); }
平衡化
在介绍插入之前,我们先介绍如何让红黑树保持平衡,因为一般的,我们插入完成之后,需要对树进行平衡化操作以使其满足平衡化。
旋转
旋转又分为左旋和右旋。通常左旋操作用于将一个向右倾斜的红色链接旋转为向左链接。对比操作前后,可以看出,该操作实际上是将红线链接的两个节点中的一个较大的节点移动到根节点上。
左旋操作如下图:
//左旋转 private Node RotateLeft(Node h) { Node x = h.Right; //将x的左节点复制给h右节点 h.Right = x.Left; //将h复制给x右节点 x.Left = h; x.Color = h.Color; h.Color = RED; return x; }
左旋的动画效果如下:
右旋是左旋的逆操作,过程如下:
代码如下:
//右旋转 private Node RotateRight(Node h) { Node x = h.Left; h.Left = x.Right; x.Right = h; x.Color = h.Color; h.Color = RED; return x; }
右旋的动画效果如下:
颜色反转
当出现一个临时的4-node的时候,即一个节点的两个子节点均为红色,如下图:
这其实是个A,E,S 4-node连接,我们需要将E提升至父节点,操作方法很简单,就是把E对子节点的连线设置为黑色,自己的颜色设置为红色。
有了以上基本操作方法之后,我们现在对应之前对2-3树的平衡操作来对红黑树进行平衡操作,这两者是可以一一对应的,如下图:
现在来讨论各种情况:
Case 1 往一个2-node节点底部插入新的节点
先热身一下,首先我们看对于只有一个节点的红黑树,插入一个新的节点的操作:
这种情况很简单,只需要:
- 标准的二叉查找树遍历即可。新插入的节点标记为红色
- 如果新插入的节点在父节点的右子节点,则需要进行左旋操作
Case 2往一个3-node节点底部插入新的节点
先热身一下,假设我们往一个只有两个节点的树中插入元素,如下图,根据待插入元素与已有元素的大小,又可以分为如下三种情况:
- 如果带插入的节点比现有的两个节点都大,这种情况最简单。我们只需要将新插入的节点连接到右边子树上即可,然后将中间的元素提升至根节点。这样根节点的左右子树都是红色的节点了,我们只需要调研FlipColor方法即可。其他情况经过反转操作后都会和这一样。
- 如果插入的节点比最小的元素要小,那么将新节点添加到最左侧,这样就有两个连接红色的节点了,这是对中间节点进行右旋操作,使中间结点成为根节点。这是就转换到了第一种情况,这时候只需要再进行一次FlipColor操作即可。
- 如果插入的节点的值位于两个节点之间,那么将新节点插入到左侧节点的右子节点。因为该节点的右子节点是红色的,所以需要进行左旋操作。操作完之后就变成第二种情况了,再进行一次右旋,然后再调用FlipColor操作即可完成平衡操作。
有了以上基础,我们现在来总结一下往一个3-node节点底部插入新的节点的操作步骤,下面是一个典型的操作过程图:
可以看出,操作步骤如下:
- 执行标准的二叉查找树插入操作,新插入的节点元素用红色标识。
- 如果需要对4-node节点进行旋转操作
- 如果需要,调用FlipColor方法将红色节点提升
- 如果需要,左旋操作使红色节点左倾。
- 在有些情况下,需要递归调用Case1 Case2,来进行递归操作。如下:
代码实现
经过上面的平衡化讨论,现在就来实现插入操作,一般地插入操作就是先执行标准的二叉查找树插入,然后再进行平衡化。对照2-3树,我们可以通过前面讨论的,左旋,右旋,FlipColor这三种操作来完成平衡化。
具体操作方式如下:
- 如果节点的右子节点为红色,且左子节点位黑色,则进行左旋操作
- 如果节点的左子节点为红色,并且左子节点的左子节点也为红色,则进行右旋操作
- 如果节点的左右子节点均为红色,则执行FlipColor操作,提升中间结点。
根据这一逻辑,我们就可以实现插入的Put方法了。
public override void Put(TKey key, TValue value) { root = Put(root, key, value); root.Color = BLACK; } private Node Put(Node h, TKey key, TValue value) { if (h == null) return new Node(key, value, 1, RED); int cmp = key.CompareTo(h.Key); if (cmp < 0) h.Left = Put(h.Left, key, value); else if (cmp > 0) h.Right = Put(h.Right, key, value); else h.Value = value; //平衡化操作 if (IsRed(h.Right) && !IsRed(h.Left)) h = RotateLeft(h); if (IsRed(h.Right) && IsRed(h.Left.Left)) h = RotateRight(h); if (IsRed(h.Left) && IsRed(h.Right)) h = FlipColor(h); h.Number = Size(h.Left) + Size(h.Right) + 1; return h; } private int Size(Node node) { if (node == null) return 0; return node.Number; }
分析
对红黑树的分析其实就是对2-3查找树的分析,红黑树能够保证符号表的所有操作即使在最坏的情况下都能保证对数的时间复杂度,也就是树的高度。
在分析之前,为了更加直观,下面是以升序,降序和随机构建一颗红黑树的动画:
- 以升序插入构建红黑树:
- 以降序插入构建红黑树:
- 随机插入构建红黑树
从上面三张动画效果中,可以很直观的看出,红黑树在各种情况下都能维护良好的平衡性,从而能够保证最差情况下的查找,插入效率。
下面来详细分析下红黑树的效率:
1. 在最坏的情况下,红黑树的高度不超过2lgN
最坏的情况就是,红黑树中除了最左侧路径全部是由3-node节点组成,即红黑相间的路径长度是全黑路径长度的2倍。
下图是一个典型的红黑树,从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍:
2. 红黑树的平均高度大约为lgN
下图是红黑树在各种情况下的时间复杂度,可以看出红黑树是2-3查找树的一种实现,他能保证最坏情况下仍然具有对数的时间复杂度。
下图是红黑树各种操作的时间复杂度。
应用
红黑树这种数据结构应用十分广泛,在多种编程语言中被用作符号表的实现,如:
- Java中的java.util.TreeMap,java.util.TreeSet
- C++ STL中的:map,multimap,multiset
- .NET中的:SortedDictionary,SortedSet 等
下面以.NET中为例,通过Reflector工具,我们可以看到SortedDictionary的Add方法如下:
public void Add(T item) { if (this.root == null) { this.root = new Node<T>(item, false); this.count = 1; } else { Node<T> root = this.root; Node<T> node = null; Node<T> grandParent = null; Node<T> greatGrandParent = null; int num = 0; while (root != null) { num = this.comparer.Compare(item, root.Item); if (num == 0) { this.root.IsRed = false; ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate); } if (TreeSet<T>.Is4Node(root)) { TreeSet<T>.Split4Node(root); if (TreeSet<T>.IsRed(node)) { this.InsertionBalance(root, ref node, grandParent, greatGrandParent); } } greatGrandParent = grandParent; grandParent = node; node = root; root = (num < 0) ? root.Left : root.Right; } Node<T> current = new Node<T>(item); if (num > 0) { node.Right = current; } else { node.Left = current; } if (node.IsRed) { this.InsertionBalance(current, ref node, grandParent, greatGrandParent); } this.root.IsRed = false; this.count++; this.version++; } }
可以看到,内部实现也是一个红黑树,其操作方法和本文将的大同小异,感兴趣的话,您可以使用Reflector工具跟进去查看源代码。
总结
前文讲解了自平衡查找树中的2-3查找树, 这种数据结构在插入之后能够进行自平衡操作,从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难, 红黑树是2-3树的一种简单高效的实现,他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树,应 用非常广泛,很多编程语言的内部实现都或多或少的采用了红黑树。
希望本文对您了解红黑树有所帮助,下文将介绍在文件系统以及数据库系统中应用非常广泛的另外一种平衡树结构:B树。
相关推荐
红黑树(Red-Black Tree)是一种自平衡二叉查找树,由计算机科学家鲁道夫·贝尔在1978年提出。它在保持二叉查找树特性的同时,通过引入颜色属性来确保树的平衡,从而提高了数据操作的效率。红黑树的主要目标是保证在...
红黑树(Red-Black Tree)是一种自平衡二叉查找树,它的每个节点都带有颜色属性,可以是红色或黑色。这种数据结构被广泛应用于计算机科学的许多领域,特别是操作系统、数据库系统以及编译器中,用于高效地执行插入、...
在计算机科学领域,各种数据结构在实际应用中...尽管实现红黑树的插入和删除操作相对复杂,但其背后的原理和操作策略仍然清晰且系统化,从而确保了在维护树平衡方面,红黑树总是能够快速适应变化,实现最优的运行效率。
红黑树是一种自平衡二叉查找树,由Rudolf Bayer于1972年提出。它的设计目标是在保持二叉查找树基本属性的同时,通过引入颜色(红色或黑色)来保证树的平衡,从而在插入和删除操作后能够快速恢复平衡状态,减少查找、...
### 红黑树的插入与删除:详细解析 红黑树是一种自平衡二叉查找树,由Rudolf Bayer在1972年发明,最初被称为“对称二叉B树”。它在1978年Leo J. Guibas和Robert Sedgewick的论文中获得了现代名称“红黑树”。红黑树...
红黑树和AVL树是两种自平衡二叉查找树,它们在计算机科学中的数据结构领域扮演着重要的角色,主要用于高效地存储和检索数据。这两种数据结构的主要目标是在插入和删除操作后保持树的平衡,从而确保搜索、插入和删除...
红黑树(Red-Black Tree)是一种自平衡二叉查找树,它在计算机科学中扮演着重要的角色,尤其是在实现高效的数据结构和算法时。在Java中,虽然标准库并未直接提供红黑树的类,但我们可以自定义实现,如提供的`Red...
红黑树是一种自平衡二叉查找树,由Rudolf Bayer在1972年提出。它的设计目标是在保持二叉查找树基本属性的同时,通过引入颜色(红色或黑色)来保证树的平衡,从而提高查找、插入和删除操作的效率。在红黑树中,每个...
红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树红黑树...
红黑树是一种自平衡二叉查找树,它的设计目的是为了在保持查找效率的同时,尽可能地减少插入和删除操作带来的性能损失。在计算机科学中,它是一种广泛应用的数据结构,特别是在动态排序和高效查找方面。 二叉搜索树...
通用红黑树 说明: 用Linux内核红黑树封装的一个通用型的红黑树 如何使用该红黑树: 见rbtest1.c和rbtest2.c 直接make生成rbtest1和rbtest2 作者:rcyh 日期:2011年7月21日 ---------------------------------...
红黑树是一种自平衡二叉查找树,由Rudolf Bayer在1972年提出。它的设计目标是在保持二叉查找树基本性质的同时,通过引入颜色属性来保证树的平衡,从而达到高效的插入、删除和查找操作。红黑树的关键特性是: 1. 每...
### 红黑树知识点详解 #### 一、红黑树定义与性质 红黑树是一种自平衡二叉查找树,其每个节点除了保存键值、左子节点、右子节点和父节点的信息外,还额外保存了一个表示颜色的属性(红色或黑色)。红黑树在进行...
红黑树和区间树是两种在计算机科学中广泛使用的数据结构,主要应用于高效的数据存储和检索。它们在算法和数据结构领域具有重要地位,尤其在处理动态集合或需要快速查找和更新操作的问题时。 首先,我们来详细了解...
红黑树是一种自平衡二叉查找树(self-balancing binary search tree),由计算机科学家Rudolf Bayer在1972年提出。它在保持二叉查找树特性的同时,通过引入颜色属性来确保树的平衡,从而提高数据操作的效率。在红黑...
红黑树(Red-Black Tree)是一种自平衡二叉查找树,它在计算机科学中扮演着重要的角色,尤其是在数据结构和算法领域。红黑树的名字来源于它的节点颜色属性:红色或黑色。这种颜色属性被用来确保树的某些关键性质,...
红黑树是一种自平衡二叉查找树,它的主要特点是在保持二叉查找树特性的同时,通过特定的颜色规则来确保树的平衡,以达到快速查找、插入和删除的目的。红黑树的每个节点都有一个颜色属性,可以是红色或黑色。在插入新...
红黑树是一种自平衡二叉查找树,由Rudolf Bayer在1972年提出。它的设计目标是在保持查询效率高的同时,尽可能地减少由于插入和删除操作引起的树的不平衡。红黑树的主要特点包括: 1. **颜色属性**:每个节点都有...
红黑树(Red-Black Tree)是一种自平衡二叉查找树,它在计算机科学中扮演着重要的角色,尤其是在数据结构和算法领域。红黑树的名字来源于它的节点颜色属性:红色或黑色。这种颜色属性用于确保树的平衡,使得在树中的...
红黑树(Red-Black Tree)是一种自平衡二叉查找树,由计算机科学家Rudolf Bayer在1972年提出。它在数据结构和算法领域具有重要地位,被广泛应用于各种系统和软件中,包括数据库索引、编译器、虚拟机等。在Delphi编程...