红黑树作为一个高效的平衡二叉树实现，查找、插入和删除操作有着O(log n)的时间复杂度。然而作为一个学习样例，实现起来却十分繁琐，一想到那些繁复的指针操作，我就开始打退堂鼓。为了提供一个对红黑树的蓝图式理解，区别于之前比较出名的红黑树讲解文章，教你透彻了解红黑树（by July），本文借助模式匹配的强大功能，用更加清晰的思路实现红黑树。
不了解模式匹配也没有关系，以为它很容易被人理解。更多关于模式匹配的文章有
- 怎样写一个解释器 的“模式匹配”部分
- 数据类型和匹配（
OCaml教程）
本文用OCaml语言书写代码，不了解OCaml也没有关系，因为它的语法足够简单。可以使用 try OCaml 熟悉一下OCaml的基本语法，同时可以将下面的代码在其上运行。
按照惯例，从二叉搜索树的构建开始说起，
二叉搜索树（非平衡）
二叉树是一个递归结构，一棵树可以被定义为两种类型，1)非叶子节点TNode包含一个値和左右子树，2)叶子节点不包含任何値（在我们实现的二叉树版本中，叶子节点不存储値，相当于null节点）。用BNF范式表示会更加清晰，
<tree> ::= TNode value <tree> <tree>
| TLeaf
当'a为int类型时，这样一棵二叉树，用递归下降的方式表示为，
TNode 5
TNode 3 TLeaf TLeaf
TNode 20
TNode 10
TLeaf
TNode 11 TLeaf
TLeaf
用OCaml可以轻松实现上边的tree类型，
type 'a tree = TNode of 'a * 'a tree * 'a tree
| TLeaf
（其中
-
'a用来实现泛型，这样允许我们构造int二叉树或者string二叉树等等各种类型的二叉树。 -
*代表将'a,'a tree,'a tree三者连接成为一个tuple）。
二叉搜索树的特性是
某节点的値总是大于左子树中的値，并且总是小于右子树中的値。
这样我们在二叉树中查找某一个元素时，如果当前节点的値等于要找的値，查找结束。不然，就递归查找左子树（如果小于此节点的値）或者右子树（如果大于此节点的値）。一旦查询到TLeaf节点则查询失败。用递归函数定义查询过程，以下的代码足够清晰和简洁，
let rec contains x bt =
match bt with
TLeaf -> false
| TNode (y, l, r) ->
x = y || (x < y && contains x l) || contains x r
向二叉树中添加元素与上边的查找过程十分类似，插入新的元素并不会对原来的树结构造成破坏。
let rec add x bt =
match bt with
TLeaf -> TNode (x, TLeaf, TLeaf) (* If at a leaf, put new node there 这是注释*)
| TNode (y, l, r) -> (* Recursively search for value 这是注释 *)
if x = y then bt
else if x > y then TNode (y, l, add x r)
else (* x < y *) TNode (y, add x l, r)
对以上几个过程进行小小的测试：
在插入过程中如果二叉树接近于平衡的话，查找操作的时间复杂度是维持在O(log n)，其中n为所有元素的个数。然而在极端的情况下，树的深度将会接近于n，使二叉树的形状很竖直而使查找操作的时间复杂度上升为O(n)。
如果一棵树可以维持平衡的特性，树的高度将维持在O(log n)，那么查找操作的时间复杂度也会渐进为O(log n)。红黑树就是一种在平凡二叉树的基础上加入更强的平衡特性的数据结构。
红黑树（平衡）
我们在二叉树的基础上，标记树中的节点要么为红色要么为黑色。定义如下，
type color = Red | Black
type 'a rbtree =
Node of color * 'a * 'a rbtree * 'a rbtree
| Leaf
并且在二叉树特性的基础上，再加入如下的特性
1 任何一个路径上不允许有两个相邻的红色节点。
2 从根节点到叶子节点的每条路径上有相同数目的黑色节点。
因为红黑树也是递归定义的，所以如果一棵树满足以上两个条件，那么它的所有子树也同样满足。如果一棵二叉树的任一子树违反以上的任一条件，则它必定不是一棵红黑树。
通过以上的特性规定，从根节点到任意的叶子节点可能的最长路径上必定是红黑节点交替出现，所以是可能的最短路径（只有黑色节点）的两倍长。以此保证红黑树的高度为O(log n)。
在红黑树中查找元素，其过程与在二叉树中查找一样，
let rec mem x rbt =
match rbt with
Leaf -> false
| Node (_, y, left, right) -> (* rbt is equivalent to (_, y, left, right) *)
x = y || (x < y && mem x left) || (x > y && mem x right)
终于到了最关键的地方，如何向红黑树中插入新元素呢。可以将插入操作分成两步，1)与非平衡二叉树插入类似，将新元素插入并将其标记为红色；2)将插入元素标记为红色有可能会违反红黑树的特性2，所以需要重新调整红黑树。
为了调整到符合红黑树的特性，不仅要考虑插入节点的红色父节点，还要考虑插入节点的黑色祖父节点，综合起来共有以下4种可能的情形，如下图
因为1图中的 Rx，2图中的 Ry，3图中的 Ry，以及4图中的 Rz，均是依照大小关系新插入的节点，与原来树中的节点组成的新的树同样符合二叉树的大小关系。所有4种情形均满足a < x < b < y < c < z < d。那么以上的4种情形已经包括了所有的可能情形，并且都可以转化为以下的结构。红黑树的黑高度在应用balance前后并不发生改变。
用模式匹配可以很容易并且清晰地表达我们想要的转换。
let balance rbt =
match rbt with
Black, z, Node (Red, y, Node (Red, x, a, b), c), d
| Black, z, Node (Red, x, a, Node (Red, y, b, c)), d
| Black, x, a, Node (Red, z, Node (Red, y, b, c), d)
| Black, x, a, Node (Red, y, b, Node (Red, z, c, d)) ->
Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d))
| a, b, c, d -> Node (a, b, c, d) (* if not in above 4 cases, donnot need do balance. *)
到此，就能看到模式匹配的强大之处了。
这种调整可能会将连续2个红色节点的结果传递到红黑树的上一层（相对于插入新元素的位置），以下是完整的插入操作的定义，它将balance持续地应用到插入位置的上一层，最坏情况是到达红黑树的根节点并将根节点标记为红色，insert过程总是将根节点标记为黑色，使树的黑高度增加1。
let insert x rbt =
let rec ins s = (* 内部定义递归过程ins *)
match s with
Leaf -> Node (Red, x, Leaf, Leaf)
| Node (color, y, a, b) ->
if x < y then balance (color, y, ins a, b)
else if x > y then balance (color, y, a, ins b)
else s in
match ins rbt with (* 调用ins过程并匹配返回结果，返回结果为根节点 *)
Node (_, y, a, b) ->
Node (Black, y, a, b) (* 始终标记根节点为黑色 *)
| Leaf -> (* guaranteed to be nonempty *)
failwith "RBT insert failed with ins returning leaf"
Scala实现
使用Scala语言的模式匹配实现红黑树，插入节点的类型为Int，节点个数为500万时，插入总耗时约7秒，黑高度为22，可以说性能非常高效。教学式算法为了简化实现，一般都基于递归实现，生产环境中需要改写为尾递归或者迭代形式。
源代码地址：红黑树github
abstract class Color
case object Red extends Color
case object Black extends Color
class RedBlackTree[T <% Ordered[T]] {
abstract class Node
case class Leaf() extends Node
case class RBNode(color:Color, value: T, left:Node, right:Node) extends Node
var root: Node = Leaf()
def search(value: T) = this.search_recursive(this.root, value)
def search_recursive(node: Node, value: T): Boolean = node match {
case Leaf() => false
case RBNode(_, v, left, right) =>
v == value ||
(value < v && this.search_recursive(left, value)) ||
(value>v && this.search_recursive(right, value))
}
def insert(value: T): Unit = {
this.root = this.insert_recursive(this.root, value)
this.root = this.root match {
case RBNode(color, value, left, right) => RBNode(Black, value, left, right)
}
}
def insert_recursive(node: Node, newval: T): Node = node match {
case Leaf() => RBNode(Red, newval, Leaf(), Leaf())
case RBNode(color, v, left, right) =>
if (newval < v) balance(RBNode(color, v, insert_recursive(left, newval), right))
else if (newval > v) balance(RBNode(color, v, left, insert_recursive(right, newval)))
else node
}
def balance(node: Node): Node = node match {
case RBNode(Black, z, RBNode(Red, y, RBNode(Red, x, a, b), c), d) =>
RBNode (Red, y, RBNode(Black, x, a, b), RBNode(Black, z, c, d))
case RBNode(Black, z, RBNode(Red, x, a, RBNode(Red, y, b, c)), d) =>
RBNode (Red, y, RBNode(Black, x, a, b), RBNode(Black, z, c, d))
case RBNode(Black, x, a, RBNode (Red, z, RBNode (Red, y, b, c), d)) =>
RBNode (Red, y, RBNode(Black, x, a, b), RBNode(Black, z, c, d))
case RBNode(Black, x, a, RBNode (Red, y, b, RBNode (Red, z, c, d))) =>
RBNode (Red, y, RBNode(Black, x, a, b), RBNode(Black, z, c, d))
case n: Node => n
}
def blackHeight(): Int = {
var tmp = this.root
var h = 0
while(tmp.isInstanceOf[RBNode]) {
tmp match {
case RBNode(color, _, left, _) => {
tmp = left
h += 1
}
}
}
return h
}
}
