数据结构和算法(Golang实现)(29)查找算法

我是陈星星，欢迎阅读我亲自写的 数据结构和算法(Golang实现)，文章首发于阅读更友好的GitBook。

某些教程不区分普通红黑树和左倾红黑树的区别，直接将左倾红黑树拿来教学，并且称其为红黑树，因为左倾红黑树与普通的红黑树相比，实现起来较为简单，容易教学。在这里，我们区分开左倾红黑树和普通红黑树。

2-32-3-42-32-3-42-3-42-3

2-32-3

一、2-3 树

1.1. 2-3 树介绍

2-3John Edward Hopcroft3阶的B树BBalance

它不是一棵二叉树，是一棵三叉树。具有以下特征：

内部节点要么有1个数据元素和2个孩子，要么有2个数据元素和3个孩子，叶子节点没有孩子，但有1或2个数据元素。
所有叶子节点到根节点的长度一致。这个特征保证了完全平衡，非常完美的平衡。
每个节点的数据元素保持从小到大排序，两个数据元素之间的子树的所有值大小介于两个数据元素之间。

2-3

如图：

如果一个内部节点拥有一个数据元素、两个子节点，则此节点为2节点。如果一个内部节点拥有两个数据元素、三个子节点，则此节点为3节点。

可以说，所有平衡树的核心都在于插入和删除逻辑，我们主要分析这两个操作。

1.2. 2-3 树插入元素

在插入元素时，需要先找到插入的位置，使用二分查找从上自下查找树节点。

2-3

插入元素到一个2节点，直接插入即可，这样节点变成3节点。
插入元素到一个3节点，该3节点的父亲是一个2节点，先将节点变成临时的4节点，然后向上分裂调整一次。
插入元素到一个3节点，该3节点的父亲是一个3节点，先将节点变成临时的4节点，然后向上分裂调整，此时父亲节点变为临时4节点，继续向上分裂调整。

如图（来自维基百科）：

核心在于插入3节点后，该节点变为临时4节点，然后进行分裂恢复树的特征。最坏情况为插入节点后，每一次分裂后都导致上一层变为临时4节点，直到树根节点，这样需要不断向上分裂。

临时4节点的分裂，细分有六种情况，如图：

2-3

2-3B树

1.3. 2-3 树删除元素

删除操作就复杂得多了，请耐心阅读理解。

2-32-32-3ABCBC2-3

基于上面的现实，我们来分析删除的不同情况，删除中间节点和叶子节点。

情况1：删除中间节点

删除的是非叶子节点，该节点一定是有两棵或者三棵子树的，那么从子树中找到其最小后继节点，该节点是叶子节点，用该节点替换被删除的非叶子节点，然后再删除这个叶子节点，进入情况2。

如何找到最小后继节点，当有两棵子树时，那么从右子树一直往左下方找，如果有三棵子树，被删除节点在左边，那么从中子树一直往左下方找，否则从右子树一直往左下方找。

情况2：删除叶子节点

2-3

2-3

重新分布：尝试从兄弟节点那里借值，然后重新调整节点。
合并：如果兄弟借不到值，合并节点（与父亲的元素），再向上递归处理。

看图说话：

如果被删除的叶子节点有兄弟是3节点，那么从兄弟那里借一个值填补被删除的叶子节点，然后兄弟和父亲重新分布调整位置。下面是重新分布的具体例子：

如果兄弟们都是2节点呢，那么就合并节点：将父亲和兄弟节点合并，如果父亲是2节点，那么父亲就留空了，否则父亲就从3节点变成2节点，下面是合并的两个具体例子：

但是，如果合并后，父亲节点变空了，也就是说有中间节点留空要怎么办，那么可以继续递归处理，如图：

中间节点是空的，那么可以继续从兄弟那里借节点或者和父亲合并，直到根节点，如果到达了根节点呢，如图：

递归到了根节点后，如果存在空的根节点，我们可以直接把该空节点删除即可，这时树的高度减少一层。

2-3B树

二、左倾红黑树

2.1. 左倾红黑树介绍

2-3

其定义为：

根节点的链接是黑色的。
红链接均为左链接。
没有任何一个结点同时和两条红链接相连
任意一个节点到达叶子节点的所有路径，经过的黑链接数量相同，也就是该树是完美黑色平衡的。比如，某一个节点，它可以到达5个叶子节点，那么这5条路径上的黑链接数量一样。

2-3

2.2. 节点旋转和颜色转换

LLRBTreeLLRBTNode

// 定义颜色
const (
    RED   = true
    BLACK = false
)

// 左倾红黑树
type LLRBTree struct {
    Root *LLRBTNode // 树根节点
}


// 左倾红黑树节点
type LLRBTNode struct {
    Value       int64     // 值
    Times       int64      // 值出现的次数
    Left        *LLRBTNode // 左子树
    Right       *LLRBTNode // 右子树
    Color       bool       // 父亲指向该节点的链接颜色
}

// 新建一棵空树
func NewLLRBTree() *LLRBTree {
    return &LLRBTree{}
}

// 节点的颜色
func IsRed(node *LLRBTNode) bool {
    if node == nil {
        return false
    }
    return node.Color == RED
}

LLRBTNodeValueTimes

ColorIsRed()

在元素添加和实现的过程中，需要做调整操作，有两种旋转操作，对某节点的右链接进行左旋转，或者左链接进行右旋转。

代码实现如下：

// 左旋转
func RotateLeft(h *LLRBTNode) *LLRBTNode {
    if h == nil {
        return nil
    }

    // 看图理解
    x := h.Right
    h.Right = x.Left
    x.Left = h
    x.Color = h.Color
    h.Color = RED
    return x
}

代码实现如下：

// 右旋转
func RotateRight(h *LLRBTNode) *LLRBTNode {
    if h == nil {
        return nil
    }

    // 看图理解
    x := h.Left
    h.Left = x.Right
    x.Right = h
    x.Color = h.Color
    h.Color = RED
    return x
}

由于左倾红黑树不允许一个节点有两个红链接，所以需要做颜色转换，如图：

代码如下：

// 颜色转换
func ColorChange(h *LLRBTNode) {
    if h == nil {
        return
    }
    h.Color = !h.Color
    h.Left.Color = !h.Left.Color
    h.Right.Color = !h.Right.Color
}

旋转和颜色转换作为局部调整，并不影响全局。

2.3. 添加元素实现

ColorRED

接着判断其父亲是否有两个红链接（如连续的两个左红链接或者左右红色链接），或者有右红色链接，进行颜色变换或旋转操作。

主要有以下这几种情况。

插入元素到2节点，直接让节点变为3节点，不过当右插入时需要左旋使得红色链接在左边，如图：

插入元素到3节点，需要做旋转和颜色转换操作，如图：

也就是说，在一个已经是红色左链接的节点，插入一个新节点的状态变化如下：

根据上述的演示图以及旋转，颜色转换等操作，添加元素的代码为：

// 左倾红黑树添加元素
func (tree *LLRBTree) Add(value int64) {
    // 跟节点开始添加元素，因为可能调整，所以需要将返回的节点赋值回根节点
    tree.Root = tree.Root.Add(value)
    // 根节点的链接永远都是黑色的
    tree.Root.Color = BLACK
}

// 往节点添加元素
func (node *LLRBTNode) Add(value int64) *LLRBTNode {
    // 插入的节点为空，将其链接颜色设置为红色，并返回
    if node == nil {
        return &LLRBTNode{
            Value: value,
            Color: RED,
        }
    }

    // 插入的元素重复
    if value == node.Value {
        node.Times = node.Times + 1
    } else if value > node.Value {
        // 插入的元素比节点值大，往右子树插入
        node.Right = node.Right.Add(value)
    } else {
        // 插入的元素比节点值小，往左子树插入
        node.Left = node.Left.Add(value)
    }

    // 辅助变量
    nowNode := node

    // 右链接为红色，那么进行左旋，确保树是左倾的
    // 这里做完操作后就可以结束了，因为插入操作，新插入的右红链接左旋后，nowNode节点不会出现连续两个红左链接，因为它只有一个左红链接
    if IsRed(nowNode.Right) && !IsRed(nowNode.Left) {
        nowNode = RotateLeft(nowNode)
    } else {
        // 连续两个左链接为红色，那么进行右旋
        if IsRed(nowNode.Left) && IsRed(nowNode.Left.Left) {
            nowNode = RotateRight(nowNode)
        }

        // 旋转后，可能左右链接都为红色，需要变色
        if IsRed(nowNode.Left) && IsRed(nowNode.Right) {
            ColorChange(nowNode)
        }
    }

    return nowNode
}

2.4. 添加元素算法分析

2log(n)n2-32-3log(n)2-32-3

AVL1.44log(n)AVLAVLlog(n)

log(n)

我们可以优化代码，使得在某一层旋转变色后，如果其父层没有连续的左红链接或者不需要变色，那么可以直接退出，不需要逐层判断是否需要旋转和变色。

AVLlog(n)

AVLAVL

在此，我们不再纠结两种平衡树哪种更好，因为代码实现中，两种平衡树都需要自底向上的递归操作，效率差别不大。。

2.5. 删除元素实现

2-3

情况1：如果删除的是非叶子节点，找到其最小后驱节点，也就是在其右子树中一直向左找，找到的该叶子节点替换被删除的节点，然后删除该叶子节点，变成情况2。
情况2：如果删除的是叶子节点，如果它是红节点，也就是父亲指向它的链接为红色，那么直接删除即可。否则，我们需要进行调整，使它变为红节点，再删除。

2-3

我们创造两种操作，如果删除的节点在左子树中，可能需要进行红色左移，如果删除的节点在右子树中，可能需要进行红色右移。

我们介绍红色左移的步骤：

hhb，dh2-3

dehdhh2-3

红色左移可以总结为下图（被删除的节点在左子树，且进入的树根h一定为红节点）：

代码如下：

// 红色左移
// 节点 h 是红节点，其左儿子和左儿子的左儿子都为黑节点，左移后使得其左儿子或左儿子的左儿子有一个是红色节点
func MoveRedLeft(h *LLRBTNode) *LLRBTNode {
    // 应该确保 isRed(h) && !isRed(h.left) && !isRed(h.left.left)
    ColorChange(h)

    // 右儿子有左红链接
    if IsRed(h.Right.Left) {
        // 对右儿子右旋
        h.Right = RotateRight(h.Right)
        // 再左旋
        h = RotateLeft(h)
        ColorChange(h)
    }

    return h
}

hh

红色右移的步骤类似，如图（被删除的节点在右子树，且进入的树根h一定为红节点）：

代码如下：

// 红色右移
// 节点 h 是红节点，其右儿子和右儿子的左儿子都为黑节点，右移后使得其右儿子或右儿子的右儿子有一个是红色节点
func MoveRedRight(h *LLRBTNode) *LLRBTNode {
    // 应该确保 isRed(h) && !isRed(h.right) && !isRed(h.right.left);
    ColorChange(h)

    // 左儿子有左红链接
    if IsRed(h.Left.Left) {
        // 右旋
        h = RotateRight(h)
        // 变色
        ColorChange(h)
    }

    return h
}

介绍完两种操作后，我们要明确一下到底是如何删除元素的。

2-32-3

树h树h树h

可以对照着大图，继续阅读下面的左倾红黑树删除元素代码：

// 左倾红黑树删除元素
func (tree *LLRBTree) Delete(value int64) {
    // 当找不到值时直接返回
    if tree.Find(value) == nil {
        return
    }

    if !IsRed(tree.Root.Left) && !IsRed(tree.Root.Right) {
        // 左右子树都是黑节点，那么先将根节点变为红节点，方便后面的红色左移或右移
        tree.Root.Color = RED
    }

    tree.Root = tree.Root.Delete(value)

    // 最后，如果根节点非空，永远都要为黑节点，赋值黑色
    if tree.Root != nil {
        tree.Root.Color = BLACK
    }
}

tree.Find(value)

当根节点的左右子树都为黑节点时，那么先将根节点变为红节点，方便后面的红色左移或右移。

tree.Root = tree.Root.Delete(value)

核心的从子树中删除元素代码如下：

// 对该节点所在的子树删除元素
func (node *LLRBTNode) Delete(value int64) *LLRBTNode {
    // 辅助变量
    nowNode := node
    // 删除的元素比子树根节点小，需要从左子树删除
    if value < nowNode.Value {
        // 因为从左子树删除，所以要判断是否需要红色左移
        if !IsRed(nowNode.Left) && !IsRed(nowNode.Left.Left) {
            // 左儿子和左儿子的左儿子都不是红色节点，那么没法递归下去，先红色左移
            nowNode = MoveRedLeft(nowNode)
        }

        // 现在可以从左子树中删除了
        nowNode.Left = nowNode.Left.Delete(value)
    } else {
        // 删除的元素等于或大于树根节点

        // 左节点为红色，那么需要右旋，方便后面可以红色右移
        if IsRed(nowNode.Left) {
            nowNode = RotateRight(nowNode)
        }

        // 值相等，且没有右孩子节点，那么该节点一定是要被删除的叶子节点，直接删除
        // 为什么呢，反证，它没有右儿子，但有左儿子，因为左倾红黑树的特征，那么左儿子一定是红色，但是前面的语句已经把红色左儿子右旋到右边，不应该出现右儿子为空。
        if value == nowNode.Value && nowNode.Right == nil {
            return nil
        }

        // 因为从右子树删除，所以要判断是否需要红色右移
        if !IsRed(nowNode.Right) && !IsRed(nowNode.Right.Left) {
            // 右儿子和右儿子的左儿子都不是红色节点，那么没法递归下去，先红色右移
            nowNode = MoveRedRight(nowNode)
        }

        // 删除的节点找到了，它是中间节点，需要用最小后驱节点来替换它，然后删除最小后驱节点
        if value == nowNode.Value {
            minNode := nowNode.Right.FindMinValue()
            nowNode.Value = minNode.Value
            nowNode.Times = minNode.Times

            // 删除其最小后驱节点
            nowNode.Right = nowNode.Right.DeleteMin()
        } else {
            // 删除的元素比子树根节点大，需要从右子树删除
            nowNode.Right = nowNode.Right.Delete(value)
        }
    }

    // 最后，删除叶子节点后，需要恢复左倾红黑树特征
    return nowNode.FixUp()
}

这段核心代码十分复杂，会用到红色左移和右移，当删除的元素小于根节点时，我们明白要在左子树中删除，如：

// 删除的元素比子树根节点小，需要从左子树删除
    if value < nowNode.Value {
        // 因为从左子树删除，所以要判断是否需要红色左移
        if !IsRed(nowNode.Left) && !IsRed(nowNode.Left.Left) {
            // 左儿子和左儿子的左儿子都不是红色节点，那么没法递归下去，先红色左移
            nowNode = MoveRedLeft(nowNode)
        }

        // 现在可以从左子树中删除了
        nowNode.Left = nowNode.Left.Delete(value)
    }

nowNode.Left = nowNode.Left.Delete(value)!IsRed(nowNode.Left) && !IsRed(nowNode.Left.Left)

如果删除的值不小于根节点，那么进入以下逻辑（可仔细阅读注释）：

// 删除的元素等于或大于树根节点

        // 左节点为红色，那么需要右旋，方便后面可以红色右移
        if IsRed(nowNode.Left) {
            nowNode = RotateRight(nowNode)
        }

        // 值相等，且没有右孩子节点，那么该节点一定是要被删除的叶子节点，直接删除
        // 为什么呢，反证，它没有右儿子，但有左儿子，因为左倾红黑树的特征，那么左儿子一定是红色，但是前面的语句已经把红色左儿子右旋到右边，不应该出现右儿子为空。
        if value == nowNode.Value && nowNode.Right == nil {
            return nil
        }

        // 因为从右子树删除，所以要判断是否需要红色右移
        if !IsRed(nowNode.Right) && !IsRed(nowNode.Right.Left) {
            // 右儿子和右儿子的左儿子都不是红色节点，那么没法递归下去，先红色右移
            nowNode = MoveRedRight(nowNode)
        }

        // 删除的节点找到了，它是中间节点，需要用最小后驱节点来替换它，然后删除最小后驱节点
        if value == nowNode.Value {
            minNode := nowNode.Right.FindMinValue()
            nowNode.Value = minNode.Value
            nowNode.Times = minNode.Times

            // 删除其最小后驱节点
            nowNode.Right = nowNode.Right.DeleteMin()
        } else {
            // 删除的元素比子树根节点大，需要从右子树删除
            nowNode.Right = nowNode.Right.Delete(value)
        }

IsRed(nowNode.Left)nowNode = RotateRight(nowNode)

value == nowNode.Value && nowNode.Right == nil

!IsRed(nowNode.Right) && !IsRed(nowNode.Right.Left)

value == nowNode.Value

minNode := nowNode.Right.FindMinValue()nowNode.Right = nowNode.Right.DeleteMin()

// 对该节点所在的子树删除最小元素
func (node *LLRBTNode) DeleteMin() *LLRBTNode {
    // 辅助变量
    nowNode := node

    // 没有左子树，那么删除它自己
    if nowNode.Left == nil {
        return nil
    }

    // 判断是否需要红色左移，因为最小元素在左子树中
    if !IsRed(nowNode.Left) && !IsRed(nowNode.Left.Left) {
        nowNode = MoveRedLeft(nowNode)
    }

    // 递归从左子树删除
    nowNode.Left = nowNode.Left.DeleteMin()

    // 修复左倾红黑树特征
    return nowNode.FixUp()
}

nowNode.FixUp()

// 修复左倾红黑树特征
func (node *LLRBTNode) FixUp() *LLRBTNode {
    // 辅助变量
    nowNode := node

    // 红链接在右边，左旋恢复，让红链接只出现在左边
    if IsRed(nowNode.Right) {
        nowNode = RotateLeft(nowNode)
    }

    // 连续两个左链接为红色，那么进行右旋
    if IsRed(nowNode.Left) && IsRed(nowNode.Left.Left) {
        nowNode = RotateRight(nowNode)
    }

    // 旋转后，可能左右链接都为红色，需要变色
    if IsRed(nowNode.Left) && IsRed(nowNode.Right) {
        ColorChange(nowNode)
    }

    return nowNode
}

如果不是删除内部节点，依然是从右子树继续递归：

// 删除的元素比子树根节点大，需要从右子树删除
    nowNode.Right = nowNode.Right.Delete(value)

FixUp()

删除操作很难理解，可以多多思考，红色左移和右移不断地递归都是为了确保删除叶子节点时，其是一个3节点。

2-3树

完整代码见最下面。

2.6. 删除元素算法分析

log(n)

2.7. 查找元素等实现

查找最小值，最大值，或者某个值，代码如下：

// 找出最小值的节点
func (tree *LLRBTree) FindMinValue() *LLRBTNode {
    if tree.Root == nil {
        // 如果是空树，返回空
        return nil
    }

    return tree.Root.FindMinValue()
}

func (node *LLRBTNode) FindMinValue() *LLRBTNode {
    // 左子树为空，表面已经是最左的节点了，该值就是最小值
    if node.Left == nil {
        return node
    }

    // 一直左子树递归
    return node.Left.FindMinValue()
}

// 找出最大值的节点
func (tree *LLRBTree) FindMaxValue() *LLRBTNode {
    if tree.Root == nil {
        // 如果是空树，返回空
        return nil
    }

    return tree.Root.FindMaxValue()
}

func (node *LLRBTNode) FindMaxValue() *LLRBTNode {
    // 右子树为空，表面已经是最右的节点了，该值就是最大值
    if node.Right == nil {
        return node
    }

    // 一直右子树递归
    return node.Right.FindMaxValue()
}

// 查找指定节点
func (tree *LLRBTree) Find(value int64) *LLRBTNode {
    if tree.Root == nil {
        // 如果是空树，返回空
        return nil
    }

    return tree.Root.Find(value)
}

func (node *LLRBTNode) Find(value int64) *LLRBTNode {
    if value == node.Value {
        // 如果该节点刚刚等于该值，那么返回该节点
        return node
    } else if value < node.Value {
        // 如果查找的值小于节点值，从节点的左子树开始找
        if node.Left == nil {
            // 左子树为空，表示找不到该值了，返回nil
            return nil
        }
        return node.Left.Find(value)
    } else {
        // 如果查找的值大于节点值，从节点的右子树开始找
        if node.Right == nil {
            // 右子树为空，表示找不到该值了，返回nil
            return nil
        }
        return node.Right.Find(value)
    }
}

// 中序遍历
func (tree *LLRBTree) MidOrder() {
    tree.Root.MidOrder()
}

func (node *LLRBTNode) MidOrder() {
    if node == nil {
        return
    }

    // 先打印左子树
    node.Left.MidOrder()

    // 按照次数打印根节点
    for i := 0; i <= int(node.Times); i++ {
        fmt.Println(node.Value)
    }

    // 打印右子树
    node.Right.MidOrder()
}

查找操作逻辑与通用的二叉查找树一样，并无区别。

2.8. 验证是否是一棵左倾红黑树

如何确保我们的代码实现的就是一棵左倾红黑树呢，可以进行验证：

// 验证是不是棵左倾红黑树
func (tree *LLRBTree) IsLLRBTree() bool {
    if tree == nil || tree.Root == nil {
        return true
    }

    // 判断树是否是一棵二分查找树
    if !tree.Root.IsBST() {
        return false
    }

    // 判断树是否遵循2-3树，也就是红链接只能在左边，不能连续有两个红链接
    if !tree.Root.Is23() {
        return false
    }

    // 判断树是否平衡，也就是任意一个节点到叶子节点，经过的黑色链接数量相同
    // 先计算根节点到最左边叶子节点的黑链接数量
    blackNum := 0
    x := tree.Root
    for x != nil {
        if !IsRed(x) { // 是黑色链接
            blackNum = blackNum + 1
        }
        x = x.Left
    }

    if !tree.Root.IsBalanced(blackNum) {
        return false
    }
    return true
}

// 节点所在的子树是否是一棵二分查找树
func (node *LLRBTNode) IsBST() bool {
    if node == nil {
        return true
    }

    // 左子树非空，那么根节点必须大于左儿子节点
    if node.Left != nil {
        if node.Value > node.Left.Value {
        } else {
            fmt.Printf("father:%#v,lchild:%#v,rchild:%#v\n", node, node.Left, node.Right)
            return false
        }
    }

    // 右子树非空，那么根节点必须小于右儿子节点
    if node.Right != nil {
        if node.Value < node.Right.Value {
        } else {
            fmt.Printf("father:%#v,lchild:%#v,rchild:%#v\n", node, node.Left, node.Right)
            return false
        }
    }

    // 左子树也要判断是否是平衡查找树
    if !node.Left.IsBST() {
        return false
    }

    // 右子树也要判断是否是平衡查找树
    if !node.Right.IsBST() {
        return false
    }

    return true
}

// 节点所在的子树是否遵循2-3树
func (node *LLRBTNode) Is23() bool {
    if node == nil {
        return true
    }

    // 不允许右倾红链接
    if IsRed(node.Right) {
        fmt.Printf("father:%#v,rchild:%#v\n", node, node.Right)
        return false
    }

    // 不允许连续两个左红链接
    if IsRed(node) && IsRed(node.Left) {
        fmt.Printf("father:%#v,lchild:%#v\n", node, node.Left)
        return false
    }

    // 左子树也要判断是否遵循2-3树
    if !node.Left.Is23() {
        return false
    }

    // 右子树也要判断是否是遵循2-3树
    if !node.Right.Is23() {
        return false
    }

    return true
}

// 节点所在的子树是否平衡，是否有 blackNum 个黑链接
func (node *LLRBTNode) IsBalanced(blackNum int) bool {
    if node == nil {
        return blackNum == 0
    }

    if !IsRed(node) {
        blackNum = blackNum - 1
    }

    if !node.Left.IsBalanced(blackNum) {
        fmt.Println("node.Left to leaf black link is not ", blackNum)
        return false
    }

    if !node.Right.IsBalanced(blackNum) {
        fmt.Println("node.Right to leaf black link is not ", blackNum)
        return false
    }

    return true
}

运行请看完整代码。

2.9. 完整程序

package main

import "fmt"

// 左倾红黑树实现
// Left-leaning red-black tree

// 定义颜色
const (
    RED   = true
    BLACK = false
)

// 左倾红黑树
type LLRBTree struct {
    Root *LLRBTNode // 树根节点
}

// 新建一棵空树
func NewLLRBTree() *LLRBTree {
    return &LLRBTree{}
}

// 左倾红黑树节点
type LLRBTNode struct {
    Value int64      // 值
    Times int64      // 值出现的次数
    Left  *LLRBTNode // 左子树
    Right *LLRBTNode // 右子树
    Color bool       // 父亲指向该节点的链接颜色
}

// 节点的颜色
func IsRed(node *LLRBTNode) bool {
    if node == nil {
        return false
    }
    return node.Color == RED
}

// 左旋转
func RotateLeft(h *LLRBTNode) *LLRBTNode {
    if h == nil {
        return nil
    }

    // 看图理解
    x := h.Right
    h.Right = x.Left
    x.Left = h
    x.Color = h.Color
    h.Color = RED
    return x
}

// 右旋转
func RotateRight(h *LLRBTNode) *LLRBTNode {
    if h == nil {
        return nil
    }

    // 看图理解
    x := h.Left
    h.Left = x.Right
    x.Right = h
    x.Color = h.Color
    h.Color = RED
    return x
}

// 红色左移
// 节点 h 是红节点，其左儿子和左儿子的左儿子都为黑节点，左移后使得其左儿子或左儿子的左儿子有一个是红色节点
func MoveRedLeft(h *LLRBTNode) *LLRBTNode {
    // 应该确保 isRed(h) && !isRed(h.left) && !isRed(h.left.left)
    ColorChange(h)

    // 右儿子有左红链接
    if IsRed(h.Right.Left) {
        // 对右儿子右旋
        h.Right = RotateRight(h.Right)
        // 再左旋
        h = RotateLeft(h)
        ColorChange(h)
    }

    return h
}

// 红色右移
// 节点 h 是红节点，其右儿子和右儿子的左儿子都为黑节点，右移后使得其右儿子或右儿子的右儿子有一个是红色节点
func MoveRedRight(h *LLRBTNode) *LLRBTNode {
    // 应该确保 isRed(h) && !isRed(h.right) && !isRed(h.right.left);
    ColorChange(h)

    // 左儿子有左红链接
    if IsRed(h.Left.Left) {
        // 右旋
        h = RotateRight(h)
        // 变色
        ColorChange(h)
    }

    return h
}

// 颜色变换
func ColorChange(h *LLRBTNode) {
    if h == nil {
        return
    }
    h.Color = !h.Color
    h.Left.Color = !h.Left.Color
    h.Right.Color = !h.Right.Color
}

// 左倾红黑树添加元素
func (tree *LLRBTree) Add(value int64) {
    // 跟节点开始添加元素，因为可能调整，所以需要将返回的节点赋值回根节点
    tree.Root = tree.Root.Add(value)
    // 根节点的链接永远都是黑色的
    tree.Root.Color = BLACK
}

// 往节点添加元素
func (node *LLRBTNode) Add(value int64) *LLRBTNode {
    // 插入的节点为空，将其链接颜色设置为红色，并返回
    if node == nil {
        return &LLRBTNode{
            Value: value,
            Color: RED,
        }
    }

    // 插入的元素重复
    if value == node.Value {
        node.Times = node.Times + 1
    } else if value > node.Value {
        // 插入的元素比节点值大，往右子树插入
        node.Right = node.Right.Add(value)
    } else {
        // 插入的元素比节点值小，往左子树插入
        node.Left = node.Left.Add(value)
    }

    // 辅助变量
    nowNode := node

    // 右链接为红色，那么进行左旋，确保树是左倾的
    // 这里做完操作后就可以结束了，因为插入操作，新插入的右红链接左旋后，nowNode节点不会出现连续两个红左链接，因为它只有一个左红链接
    if IsRed(nowNode.Right) && !IsRed(nowNode.Left) {
        nowNode = RotateLeft(nowNode)
    } else {
        // 连续两个左链接为红色，那么进行右旋
        if IsRed(nowNode.Left) && IsRed(nowNode.Left.Left) {
            nowNode = RotateRight(nowNode)
        }

        // 旋转后，可能左右链接都为红色，需要变色
        if IsRed(nowNode.Left) && IsRed(nowNode.Right) {
            ColorChange(nowNode)
        }
    }

    return nowNode
}

// 找出最小值的节点
func (tree *LLRBTree) FindMinValue() *LLRBTNode {
    if tree.Root == nil {
        // 如果是空树，返回空
        return nil
    }

    return tree.Root.FindMinValue()
}

func (node *LLRBTNode) FindMinValue() *LLRBTNode {
    // 左子树为空，表面已经是最左的节点了，该值就是最小值
    if node.Left == nil {
        return node
    }

    // 一直左子树递归
    return node.Left.FindMinValue()
}

// 找出最大值的节点
func (tree *LLRBTree) FindMaxValue() *LLRBTNode {
    if tree.Root == nil {
        // 如果是空树，返回空
        return nil
    }

    return tree.Root.FindMaxValue()
}

func (node *LLRBTNode) FindMaxValue() *LLRBTNode {
    // 右子树为空，表面已经是最右的节点了，该值就是最大值
    if node.Right == nil {
        return node
    }

    // 一直右子树递归
    return node.Right.FindMaxValue()
}

// 查找指定节点
func (tree *LLRBTree) Find(value int64) *LLRBTNode {
    if tree.Root == nil {
        // 如果是空树，返回空
        return nil
    }

    return tree.Root.Find(value)
}

func (node *LLRBTNode) Find(value int64) *LLRBTNode {
    if value == node.Value {
        // 如果该节点刚刚等于该值，那么返回该节点
        return node
    } else if value < node.Value {
        // 如果查找的值小于节点值，从节点的左子树开始找
        if node.Left == nil {
            // 左子树为空，表示找不到该值了，返回nil
            return nil
        }
        return node.Left.Find(value)
    } else {
        // 如果查找的值大于节点值，从节点的右子树开始找
        if node.Right == nil {
            // 右子树为空，表示找不到该值了，返回nil
            return nil
        }
        return node.Right.Find(value)
    }
}

// 中序遍历
func (tree *LLRBTree) MidOrder() {
    tree.Root.MidOrder()
}

func (node *LLRBTNode) MidOrder() {
    if node == nil {
        return
    }

    // 先打印左子树
    node.Left.MidOrder()

    // 按照次数打印根节点
    for i := 0; i <= int(node.Times); i++ {
        fmt.Println(node.Value)
    }

    // 打印右子树
    node.Right.MidOrder()
}

// 修复左倾红黑树特征
func (node *LLRBTNode) FixUp() *LLRBTNode {
    // 辅助变量
    nowNode := node

    // 红链接在右边，左旋恢复，让红链接只出现在左边
    if IsRed(nowNode.Right) {
        nowNode = RotateLeft(nowNode)
    }

    // 连续两个左链接为红色，那么进行右旋
    if IsRed(nowNode.Left) && IsRed(nowNode.Left.Left) {
        nowNode = RotateRight(nowNode)
    }

    // 旋转后，可能左右链接都为红色，需要变色
    if IsRed(nowNode.Left) && IsRed(nowNode.Right) {
        ColorChange(nowNode)
    }

    return nowNode
}

// 对该节点所在的子树删除最小元素
func (node *LLRBTNode) DeleteMin() *LLRBTNode {
    // 辅助变量
    nowNode := node

    // 没有左子树，那么删除它自己
    if nowNode.Left == nil {
        return nil
    }

    // 判断是否需要红色左移，因为最小元素在左子树中
    if !IsRed(nowNode.Left) && !IsRed(nowNode.Left.Left) {
        nowNode = MoveRedLeft(nowNode)
    }

    // 递归从左子树删除
    nowNode.Left = nowNode.Left.DeleteMin()

    // 修复左倾红黑树特征
    return nowNode.FixUp()
}

// 左倾红黑树删除元素
func (tree *LLRBTree) Delete(value int64) {
    // 当找不到值时直接返回
    if tree.Find(value) == nil {
        return
    }

    if !IsRed(tree.Root.Left) && !IsRed(tree.Root.Right) {
        // 左右子树都是黑节点，那么先将根节点变为红节点，方便后面的红色左移或右移
        tree.Root.Color = RED
    }

    tree.Root = tree.Root.Delete(value)

    // 最后，如果根节点非空，永远都要为黑节点，赋值黑色
    if tree.Root != nil {
        tree.Root.Color = BLACK
    }
}

// 对该节点所在的子树删除元素
func (node *LLRBTNode) Delete(value int64) *LLRBTNode {
    // 辅助变量
    nowNode := node
    // 删除的元素比子树根节点小，需要从左子树删除
    if value < nowNode.Value {
        // 因为从左子树删除，所以要判断是否需要红色左移
        if !IsRed(nowNode.Left) && !IsRed(nowNode.Left.Left) {
            // 左儿子和左儿子的左儿子都不是红色节点，那么没法递归下去，先红色左移
            nowNode = MoveRedLeft(nowNode)
        }

        // 现在可以从左子树中删除了
        nowNode.Left = nowNode.Left.Delete(value)
    } else {
        // 删除的元素等于或大于树根节点

        // 左节点为红色，那么需要右旋，方便后面可以红色右移
        if IsRed(nowNode.Left) {
            nowNode = RotateRight(nowNode)
        }

        // 值相等，且没有右孩子节点，那么该节点一定是要被删除的叶子节点，直接删除
        // 为什么呢，反证，它没有右儿子，但有左儿子，因为左倾红黑树的特征，那么左儿子一定是红色，但是前面的语句已经把红色左儿子右旋到右边，不应该出现右儿子为空。
        if value == nowNode.Value && nowNode.Right == nil {
            return nil
        }

        // 因为从右子树删除，所以要判断是否需要红色右移
        if !IsRed(nowNode.Right) && !IsRed(nowNode.Right.Left) {
            // 右儿子和右儿子的左儿子都不是红色节点，那么没法递归下去，先红色右移
            nowNode = MoveRedRight(nowNode)
        }

        // 删除的节点找到了，它是中间节点，需要用最小后驱节点来替换它，然后删除最小后驱节点
        if value == nowNode.Value {
            minNode := nowNode.Right.FindMinValue()
            nowNode.Value = minNode.Value
            nowNode.Times = minNode.Times

            // 删除其最小后驱节点
            nowNode.Right = nowNode.Right.DeleteMin()
        } else {
            // 删除的元素比子树根节点大，需要从右子树删除
            nowNode.Right = nowNode.Right.Delete(value)
        }
    }

    // 最后，删除叶子节点后，需要恢复左倾红黑树特征
    return nowNode.FixUp()
}

// 验证是不是棵左倾红黑树
func (tree *LLRBTree) IsLLRBTree() bool {
    if tree == nil || tree.Root == nil {
        return true
    }

    // 判断树是否是一棵二分查找树
    if !tree.Root.IsBST() {
        return false
    }

    // 判断树是否遵循2-3树，也就是红链接只能在左边，不能连续有两个红链接
    if !tree.Root.Is23() {
        return false
    }

    // 判断树是否平衡，也就是任意一个节点到叶子节点，经过的黑色链接数量相同
    // 先计算根节点到最左边叶子节点的黑链接数量
    blackNum := 0
    x := tree.Root
    for x != nil {
        if !IsRed(x) { // 是黑色链接
            blackNum = blackNum + 1
        }
        x = x.Left
    }

    if !tree.Root.IsBalanced(blackNum) {
        return false
    }
    return true
}

// 节点所在的子树是否是一棵二分查找树
func (node *LLRBTNode) IsBST() bool {
    if node == nil {
        return true
    }

    // 左子树非空，那么根节点必须大于左儿子节点
    if node.Left != nil {
        if node.Value > node.Left.Value {
        } else {
            fmt.Printf("father:%#v,lchild:%#v,rchild:%#v\n", node, node.Left, node.Right)
            return false
        }
    }

    // 右子树非空，那么根节点必须小于右儿子节点
    if node.Right != nil {
        if node.Value < node.Right.Value {
        } else {
            fmt.Printf("father:%#v,lchild:%#v,rchild:%#v\n", node, node.Left, node.Right)
            return false
        }
    }

    // 左子树也要判断是否是平衡查找树
    if !node.Left.IsBST() {
        return false
    }

    // 右子树也要判断是否是平衡查找树
    if !node.Right.IsBST() {
        return false
    }

    return true
}

// 节点所在的子树是否遵循2-3树
func (node *LLRBTNode) Is23() bool {
    if node == nil {
        return true
    }

    // 不允许右倾红链接
    if IsRed(node.Right) {
        fmt.Printf("father:%#v,rchild:%#v\n", node, node.Right)
        return false
    }

    // 不允许连续两个左红链接
    if IsRed(node) && IsRed(node.Left) {
        fmt.Printf("father:%#v,lchild:%#v\n", node, node.Left)
        return false
    }

    // 左子树也要判断是否遵循2-3树
    if !node.Left.Is23() {
        return false
    }

    // 右子树也要判断是否是遵循2-3树
    if !node.Right.Is23() {
        return false
    }

    return true
}

// 节点所在的子树是否平衡，是否有 blackNum 个黑链接
func (node *LLRBTNode) IsBalanced(blackNum int) bool {
    if node == nil {
        return blackNum == 0
    }

    if !IsRed(node) {
        blackNum = blackNum - 1
    }

    if !node.Left.IsBalanced(blackNum) {
        fmt.Println("node.Left to leaf black link is not ", blackNum)
        return false
    }

    if !node.Right.IsBalanced(blackNum) {
        fmt.Println("node.Right to leaf black link is not ", blackNum)
        return false
    }

    return true
}

func main() {
    tree := NewLLRBTree()
    values := []int64{2, 3, 7, 10, 10, 10, 10, 23, 9, 102, 109, 111, 112, 113}
    for _, v := range values {
        tree.Add(v)
    }

    // 找到最大值或最小值的节点
    fmt.Println("find min value:", tree.FindMinValue())
    fmt.Println("find max value:", tree.FindMaxValue())

    // 查找不存在的99
    node := tree.Find(99)
    if node != nil {
        fmt.Println("find it 99!")
    } else {
        fmt.Println("not find it 99!")
    }

    // 查找存在的9
    node = tree.Find(9)
    if node != nil {
        fmt.Println("find it 9!")
    } else {
        fmt.Println("not find it 9!")
    }

    tree.MidOrder()

    // 删除存在的9后，再查找9
    tree.Delete(9)
    tree.Delete(10)
    tree.Delete(2)
    tree.Delete(3)
    tree.Add(4)
    tree.Add(3)
    tree.Add(10)
    tree.Delete(111)
    node = tree.Find(9)
    if node != nil {
        fmt.Println("find it 9!")
    } else {
        fmt.Println("not find it 9!")
    }

    if tree.IsLLRBTree() {
        fmt.Println("is a llrb tree")
    } else {
        fmt.Println("is not llrb tree")
    }
}

运行：

find min value: &{2 0 <nil> <nil> false}
find max value: &{113 0 0xc0000941e0 <nil> false}
not find it 99!
find it 9!
2
3
7
9
10
10
10
10
23
102
109
111
112
113
not find it 9!
is a llrb tree

PS：我们的程序是递归程序，如果改写为非递归形式，效率和性能会更好，在此就不实现了，理解左倾红黑树添加和删除的总体思路即可。

三、应用场景

valuekey:value

Java 语言基础类库中的 HashMap，TreeSet，TreeMap 都有使用到，C++ 语言的 STL 标准模板库中，map 和 set 类也有使用到。很多中间件也有使用到，比如 Nginx，但 Golang 语言标准库并没有它。

最后，上述应用场景使用的红黑树都是普通红黑树，并不是本文所介绍的左倾红黑树。

左倾红黑树作为红黑树的一个变种，只是被设计为更容易理解而已，变种只能是变种，工程上使用得更多的还是普通红黑树，所以我们仍然需要学习普通的红黑树，请看下一章节。

系列文章入口

我是陈星星，欢迎阅读我亲自写的 数据结构和算法(Golang实现)，文章首发于阅读更友好的GitBook。

数据结构和算法(Golang实现)(29)查找算法

一、2-3 树

1.1. 2-3 树介绍

1.2. 2-3 树插入元素

1.3. 2-3 树删除元素

二、 左倾红黑树

2.1. 左倾红黑树介绍

2.2. 节点旋转和颜色转换

2.3. 添加元素实现

2.4. 添加元素算法分析

2.5. 删除元素实现

2.6. 删除元素算法分析

2.7. 查找元素等实现

2.8. 验证是否是一棵左倾红黑树

2.9. 完整程序

三、应用场景

系列文章入口

二、左倾红黑树