浅谈算法和数据结构（9）：平衡查找树之红黑树

816 查看

前面一篇文章介绍了2-3查找树，可以看到，2-3查找树能保证在插入元素之后能保持树的平衡状态，最坏情况下即所有的子节点都是2-node，树的高度为lgN，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，本文介绍一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）

定义

红黑树的主要是像是对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;

态，最坏情况下即所有的子节点都是2-node，树的高度为lgN，从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂，本文介绍一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）

定义