红黑树
红黑树是每个节点都带有颜色属性（红色或黑色）的二叉查找树。红黑树也属于自平衡二叉查找树。
参考：go语言中文文档：www.topgoer.com
转自：
红黑树具有如下性质：
1. 每个节点要么是红色要么是黑色。
2. 树的根结点为黑色节点。
3. 所有叶子节点都是黑色节点（叶子是NIL节点）。
4. 每个红色节点必须有两个黑色的子节点（从每个叶子到根的所有路径上不能有两个连续的红色节点）。
5. 从任意节点到其每个叶子节点的所有简单路径都包含相同数目的黑色节点。
一个红黑树的例子：
红黑树与平衡二叉树(AVL)的区别
- 二者虽然都是自平衡二叉树，但是各自对平衡的定义不同。AVL的平衡是指树中任意节点的左右子树的高度差不超过1，而在红黑树中的平衡则是由上面5点性质带来的: 红黑树中的最短子树h和最高子树H满足关系：H <= 2h。
- AVL的平衡只需要通过树的旋转即可达成平衡，而红黑树除了旋转还需要重绘节点的颜色。
- AVL中的叶子节点带有数据，而红黑树的叶子节点则是数据域为空的黑色节点，即红黑树的所有叶子节点均为黑色。
红黑树的查找操作与普通二叉树相同，但是对于插入和删除操作，因为新增或者删除一个节点可能会打破红黑树的性质，所以需要通过旋转和节点颜色变更来恢复红黑树的性质。红黑树的一切操作都是围绕红黑树的5点性质进行的。
红黑树插入节点
因为本质也是一棵二叉树，所以红黑树的插入操作与普通二叉树相同，只是为了维护红黑树的性质，需要进行节点颜色变更以及树旋转（如果需要的话）。
对于新插入的节点，我们将其标记为红色节点（如果设为黑色，就会导致根到叶子节点的路径上有一条路多出一个额外的黑节点。但是设为红色节后，没有多出黑色节点，虽然可能会出现两个连续的红色节点，但是可以通过颜色调换和树旋转来调整），对于插入操作需要进行什么操作（颜色变更和树旋转），取决于其他临近节点的颜色。为了方便阅读后面的代码，下面给出一些基础的数据结构以及方法：
type (
color uint //颜色
//添加的元素
Element interface {
Value() interface{}
Compare(Element) int //相等返回0，小于返回负数，大于返回正数
}
//红黑树节点
RedBlackNode struct {
Color color //节点颜色
Data Element //数据
Parent *RedBlackNode //父节点
Left *RedBlackNode //左孩子
Right *RedBlackNode //右孩子
}
//红黑树
RedBlackTree struct {
Root *RedBlackNode //根节点
}
)
const (
Black color = iota + 1
Red
)
//获取某个节点的祖父节点（爷爷节点）
func (t *RedBlackNode) grandParent() *RedBlackNode {
//根节点没有父节点和祖父节点
if t.Parent == nil {
return nil
}
return t.Parent.Parent
}
//获取某个节点的叔父节点（父节点的兄弟节点）
func (t *RedBlackNode) uncleNode() *RedBlackNode {
if t.grandParent() == nil {
return nil
}
if t.Parent == t.grandParent().Left {
return t.grandParent().Right
}
return t.grandParent().Left
}
在添加节点的过程中：
- 性质1和性质3总是保持着。
- 性质4只在增加红色节点、重绘黑色节点为红色，或做旋转时收到威胁。
- 性质5只在增加黑色节点、重绘红色节点为黑色，或做旋转时收到威胁。
为了方便描述，在添加节点操作中，我们将要插入的节点标为 N ，N的父节点标为 P ，N的祖父节点标为 G ， N 的叔父节点标为 U ，下面分情形讨论插入节点的情况：
- 节点N位于树的根上，没有父节点。在这种情形下，我们把N重绘为黑色以满足性质2，因为它在每个路径上对黑节点数量加1，符合性质5。所以这种情况我们只需要将节点N重绘为黑色即可，如果N不位于根上，则进入情形2。
func insertCase1(node *RedBlackNode) (root *RedBlackNode) {
if node.Parent == nil {
node.Color = Black
root = node
return
}
return insertCase2(node)
}
- N的父节点P是黑色，因为新节点是红色，所以性质4没有失效。因为没有黑色节点的增加，所以在这种情形下性质5仍然保持，虽然N有可能有两个黑色叶子节点，但是仔细想一想，如果N有两个叶子节点，那么在添加节点前N的位置一定是黑色叶子节点，所以在添加前后，通过该位置的到达任意叶子节点的黑色节点数目始终未变，所以性质5始终保持着。如果N的父节点为红色，则进入情形3。
func insertCase2(node *RedBlackNode) (root *RedBlackNode) {
if node.Parent.Color == Black {
return
}
return insertCase3(node)
}
除了上面两种情形，在接下来的情形中，N的父节点均为红色，所以N一定有祖父节点（如果没有祖父节点，那么父节点即为根结点，这与父节点为红色节点不相符），并且N一定有叔父节点（叔父节点可能是没有数据的黑色叶子节点）。
- 如果父节点P和叔父节点U二者均为红色，则我们可以将P和U重绘为黑色并将祖父节点G重绘为红色（为了保持性质5）。现在N有了一个黑色的父节点P，因为通过父节点P或者叔父节点U的任何路径都必定通过祖父节点G，所以总的来说这些路径上的黑色节点数量没有变。但如果祖父节点G为根结点，那么就违背了性质2，也有可能祖父节点G的父节点也是红色，那么就违背了性质4，为了解决这两个隐患，我们在祖父节点G上递归的进行情形1整个过程（即把祖父节点G当成新加入的节点进行各种情形的检查）。
注意：在情形3中，无论N作为P的左孩子还是右孩子出现，处理过程都一样
func insertCase3(node *RedBlackNode) (root *RedBlackNode) {
if uncle := node.uncleNode(); uncle != nil && uncle.Color == Red {
grandParent := node.grandParent()
node.Parent.Color = Black
uncle.Color = Black
grandParent.Color = Red
return insertCase1(grandParent)
}
return insertCase4(node)
}
- 父节点P是红色而叔父节点U是黑色或者缺少，并且N是P的右孩子而P又是G的左孩子，在这种情况下，我们进行一次左旋转调节N和P的角色，接着我们按情形5处理P以解决仍然失效的性质4。
func insertCase4(node *RedBlackNode) (root *RedBlackNode) {
grandParent := node.grandParent()
if node == node.Parent.Right && node.Parent == grandParent.Left {
leftRotate(node.Parent)
node = node.Left
} else if node == node.Parent.Left && node.Parent == grandParent.Right {
rightRotate(node.Parent)
node = node.Right
}
return insertCase5(node)
}
- 父节点P是红色而叔父节点U是黑色或者缺少，N是P的左孩子，而P也是G的左孩子，这种情形下，我们针对G进行一次右旋转，在旋转产生的树中，以前的父节点P现在是N和G的父节点，因为G肯定是黑色，所以我们交换P和G的颜色，交换后的树满足性质4和性质5，因为通过这三个节点中任何一个的所有路径以前都通过G，现在它们都通过P，无论哪种情形下，P现在都是三个节点中的唯一一个黑色节点。
func insertCase5(node *RedBlackNode) (root *RedBlackNode) {
grandParent := node.grandParent()
node.Parent.Color = Black
grandParent.Color = Red
if node == node.Parent.Left && node.Parent == grandParent.Left {
root = rightRotate(grandParent)
} else {
root = leftRotate(grandParent)
}
return
}
红黑树删除节点
删除节点时，我们需要先找到需要被删除的节点。对于左右孩子均为叶子节点的，如果被删除的节点为红色，则直接将节点删除即可，但如果被删除的节点是黑色，因为路径上的黑色节点数量少了一个，所以需要对树做调整以维持各性质不变。如果被删除节点存在一个叶子节点和一个子树，那么从子树中找到最大或者最小值的节点，并将其值复制到被删除的节点，最终将被复制的节点删除即可，被删除的节点最多只有一个非叶子节点的孩子节点。如果被删除节点存在左右子树，我们同样可以从子树中找到最大或者最小的值，并将其复制到需要删除的节点，并将被复制的节点删除即可，综上，删除问题最终都可以转换成删除只有一个非叶子节点的孩子节点的问题。（注意：上面说的复制只是复制值而不复制节点颜色）。
所以，我们只需要讨论删除只有一个儿子（非叶子）的节点：
- 如果被删除节点为红色，此时该节点只有叶子节点，因为它的父亲和孩子节点都为黑色，所以只需要用它的孩子节点替换它即可。
- 如果被删除节点是黑色，而它的孩子节点为红色的时候，如果用它的孩子节点顶替上来的话，会破坏性质5，但是如果重绘它的儿子节点为黑色，则曾经通过它的所有路径将通过它的黑色儿子，这样可以继续保持性质5。
- 如果被删除节点和它的孩子节点均为黑色的时候（这种情况下，该节点的两个孩子节点均为叶子节点，因为如果其中一个不为叶子节点，则从该节点通过其非叶子节点的路径上的黑色节点数最少为2，而从该节点到另一个叶子节点的黑色节点数量为1，违反了性质5，所以不成立，即这种情况下该节点的两个孩子节点一定是叶子节点。）我们首先把要删除的节点替换为它的儿子，出于方便，称呼这个儿子为 N ，称呼它的兄弟（它父亲的另一个儿子）为 S 。在后面的示意图中 P 为 N 的父亲，为S的左儿子,为S的右儿子，其中 P 才是需要删除的节点，下面为获取某个节点兄弟节点的函数以及删除节点函数的入口:
//找到某个节点的兄弟节点
func (t *RedBlackNode) siblingNode() *RedBlackNode {
if t.Parent == nil {
return nil
}
if t == t.Parent.Left {
return t.Parent.Right
}
return t.Parent.Left
}
//删除node节点, 这里被删除的节点一定最多只有一个非叶子节点的孩子节点，
func deleteNode(node *RedBlackNode) (root *RedBlackNode) {
var child *RedBlackNode
if node.Left.Data == nil {
child = node.Right
} else {
child = node.Left
}
//如果删除的是没有子树的根节点
if node.Parent == nil && node.Left.Data == nil && node.Right.Data == nil {
node.Data = nil
node.Color = Black
root = node
return
}
//将孩子节点提升, 这里已经将node删除
if node.Parent.Left == node {
node.Parent.Left = child
} else {
node.Parent.Right = child
}
child.Parent = node.Parent
//如果node为红色，删除红色节点不会影响红黑树的性质，不需要调整
//如果node是黑色，但孩子节点是红色，此时只需要将孩子节点改为黑色即可
//如果node是黑色，孩子节点也是黑色，则少了一个黑色节点，需要对树进行调整，以达到平衡
if node.Color == Black {
if child.Color == Red { //如果删除的是黑色节点并且提升的孩子节点为红色，则只需要将孩子节点调色为黑色即可
child.Color = Black
} else { //否则需要其他操作
root = deleteCase1(child)
}
}
return
}
- N是新的根，此时树的所有性质都没有被改变，所以不需要操作，否则进入情形2
//被删除的是根，孩子节点作为新的根，否则进入case2
func deleteCase1(node *RedBlackNode) (root *RedBlackNode) {
if node.Parent == nil {
return node
}
return deleteCase2(node)
}
- N的兄弟节点S是红色，这种情形下我们在N的父亲节点P上做左旋转，把兄弟节点S转换为N的祖父节点，接着我们对调P和祖父的颜色，之后虽然所有路径上的黑色节点数量没有改变，但现在N有了一个黑色的兄弟和一个红色的父亲，我们接着按照情形4、5、6来处理。
func deleteCase2(node *RedBlackNode) (root *RedBlackNode) {
var siblingNode = node.siblingNode()
if siblingNode == nil {
return
}
if siblingNode.Color == Red {
node.Parent.Color = Red
siblingNode.Color = Black
if node == node.Parent.Left {
leftRotate(node.Parent)
} else {
rightRotate(node.Parent)
}
}
return deleteCase3(node)
}
- N的父亲，S和S的儿子都是黑色的。在这种情况下，我们简单的重绘S为红色，结果是通过S的所有路径（就是之前不通过N的那些路径），都少了一个黑色节点，因为删除N的初始父亲已经使通过N的所有路径少了一个黑色节点来，所以二者平衡。但是所有通过P的路径比不通过P的路径少了一个黑色节点，我们可以重复情形1来重新恢复平衡。
func deleteCase3(node *RedBlackNode) (root *RedBlackNode) {
var siblingNode = node.siblingNode()
if (node.Parent.Color == Black) &&
(siblingNode.Color == Black) &&
(siblingNode.Left.Color == Black) &&
(siblingNode.Right.Color) == Black {
siblingNode.Color = Red
return deleteCase1(node.Parent)
} else {
return deleteCase4(node)
}
}
- S和S的儿子都是黑色，但是N的父亲是红色。这种情形下，我们简单的交换N的兄弟和父亲的颜色。这不影响不通过N的路径上的黑色节点的数量。但是通过N的路径上的黑色节点数量增加了1，填补了已经被删除了的黑色节点。
func deleteCase4(node *RedBlackNode) (root *RedBlackNode) {
var siblingNode = node.siblingNode()
if (node.Parent.Color == Red) &&
(siblingNode.Color == Black) &&
(siblingNode.Left.Color == Black) &&
(siblingNode.Right.Color == Black) {
siblingNode.Color = Red
node.Parent.Color = Black
} else {
root = deleteCase5(node)
}
return
}
- S是黑色，S的左孩子是红色，S的右孩子是黑色，而N是它父亲的左儿子，在这种情形下，我们在S上做右旋转，这样S的左儿子将成为S的父亲和N的亲兄弟。我们接着交换S和它的新父亲的颜色，这样所有路径上仍有同样数目的黑色节点，但是现在N有了一个黑色兄弟，它的右孩子是红色的，接着进入情形6。
func deleteCase5(node *RedBlackNode) (root *RedBlackNode) {
var siblingNode = node.siblingNode()
if siblingNode.Color == Black {
if (node == node.Parent.Left) &&
(siblingNode.Right.Color == Black) &&
(siblingNode.Left.Color == Red) {
siblingNode.Color = Red
siblingNode.Left.Color = Black
rightRotate(siblingNode)
} else if (node == node.Parent.Right) &&
(siblingNode.Left.Color == Black) &&
(siblingNode.Right.Color == Red) {
siblingNode.Color = Red
siblingNode.Right.Color = Black
leftRotate(siblingNode)
}
}
return deleteCase6(node)
}
- S是黑色，S的右孩子是红色，而N是它父亲的左孩子，在这种情形下，我们在N的父亲上做左旋转，这样S成为N的祖父节点，我们接着交换N的父亲和S的颜色，并使S的右孩子为黑色。子树在它的跟上仍然是同样的颜色，所以性质3没有打破，但是N现在增加了一个黑色祖先：要么N的父亲变成黑色，要么它是黑色而S被增加为一个黑色祖父。所以通过N的路径上都增加了一个黑色节点。此时，如果一个路径不通过N，则有两种可能性：*. 它通过N的新兄弟。那么它以前和现在都必定通过S和N的福清，而它们只是交换了颜色，所以路径保持了同样数目的黑色节点。
*. 它通过N的新叔父，S的右孩子，那么它以前通过S、S的父亲和S的右孩子，但是现在只通过S，它被假定为它以前的父亲的颜色，和S的右孩子，它从红色变为了黑色，最终效果是这个路径通过了同样数目的黑色节点。在任何情况下，这些路径上的黑色节点数目都没有改变。在图中的白色节点可以是红色或黑色。
func deleteCase6(node *RedBlackNode) (root *RedBlackNode) {
var siblingNode = node.siblingNode()
siblingNode.Color = node.Parent.Color
node.Parent.Color = Black
if node == node.Parent.Left {
siblingNode.Right.Color = Black
root = leftRotate(node.Parent)
} else {
siblingNode.Left.Color = Black
root = rightRotate(node.Parent)
}
return
}
不论插入还是删除节点，最终都返回了一个root，因为在旋转过程中树的根结点有可能发生改变，所以需要将每次旋转后的最顶层的节点返回，并最终与原来的root节点比较，如果不同则做替换。
