Go语言学习之手撕红黑树

作者: 饿虎嗷呜 | 来源:发表于2020-06-09 20:26 被阅读0次

最近一直在看内核相关的资料以及相关的源码，抠到细节里面就差点出不来，有些小郁闷，于是我打算调剂一下，练练go语言。之所以选择红黑树是因为这确实是一种比较复杂的数据结构，对于我自己来说也是有一些挑战。这些常见的数据结构也会是我写作计划的一部分，就从最难的红黑树开始吧。

红黑树的特点

红黑树的应用非常广泛，这是一种相对平衡的二叉查找树，由于其O(log（n))的查询速度，相对较少的平衡操作，在工程中有广泛的应用。比如在Linux内核中，就有很多地方使用了红黑树。

顾名思义，红黑树中有两种颜色的节点，即红色和黑色。红黑树的实现方式据我所知现在有两种，他们有一些共性的特定：

根节点是黑色。
从根到各个子树叶节点路径上的黑色节点数目相同。
叶节点是空节点（null），认为该节点是黑色。
路径上不存在连续两个红色节点。

在红黑树里，所谓的平衡即指的是黑色节点的平衡，如果把其中所有的红色节点移除，我们可以看到，剩余的是一颗平衡的多叉树。

在实现上，红黑树有两种，一种从2-3树演化而来，这种实现有一个额外的限制，即只有一个节点的左子节点可以是红色节点，这种情况，可以认为该节点和其子节点可以组成一个3型节点。具体可以参考这篇文章：https://riteme.site/blog/2016-3-12/2-3-tree-and-red-black-tree.html#fn:red-is-left 此处不对2-3树做更多赘述。

另外一种实现即Linux内核中的实现方式，而我这次使用的就是这一种。

首先要定义一下本文中使用的数据结构，首先是红黑树的节点：

const (
    RED   = 0
    BLACK = 1
)

// RbNode Servers as Node of Red-Black Tree
type RbNode struct {
    data     int
    color    int
    rbFather *RbNode
    rbLeft   *RbNode
    rbRight  *RbNode
}

为简单起见，我使用了一个int类型的字段作为节点的数据，定义了一个int类型字段用来标记节点的颜色。另外定义了3个指针，除了执行左右子节点的指针外，还有一个执行其父节点的指针。

由于整颗红黑树的根节点在插入，删除和平衡的过程中是有可能发生调整的，我另外定义了一个root类型来指向一颗红黑树。

// RbRoot point to the root node of Rb-tree
type RbRoot struct {
    root *RbNode
}

平衡操作

相对于其他二叉查找树/平衡二叉树，红黑树的特点有：1，左右子树相对平衡，2，平衡操作所需的资源消耗较少。在进行平衡时，有三种基本操作：左旋，右旋以及颜色翻转。

左旋，右旋

rb-tree.png

上图中2号节点和4号节点是我们需要调整的，左旋和右旋互为镜像操作，以右旋为例，我们把关注点设置在4号节点上，我们需要调整以下关系：

将4号节点父节点的相应左节点/右节点指针指向其左子节点2号。
将4号节点的左节点指针指向2号节点的右子节点
将4号节点的父节点指针指向2号节点
将2号节点的右节点指针指向4号节点
将2号节点的父节点指针指向4号节点的父节点
将3号节点的父节点指针指向四号节点

这样看起来有一些绕，其实我们所做的一切就是上图标成棕色的3条线，调整一共6个指针即可。

右旋的代码如下，供参考:

// RollRight
func rollRight(node *RbNode) *RbNode {
    if nil == node || nil == node.rbLeft {
        return nil
    }

    var father *RbNode = node.rbFather
    var left *RbNode = node.rbLeft
    var leftRight *RbNode = left.rbRight

    if father.rbRight == node {
        father.rbRight = left
    } else {
        father.rbLeft = left
    }

    left.rbFather = father
    left.rbRight = node
    node.rbFather = left
    node.rbLeft = leftRight
    leftRight.rbFather = node
  
    return left
}

下面是左旋操作的代码，可以看到，结构几乎是完全一致的：

// RollLeft
func rollLeft(node *RbNode) *RbNode {
    if nil == node || nil == node.rbRight {
        return nil
    }

    var father *RbNode = node.rbFather
    var right *RbNode = node.rbRight
    var rightLeft *RbNode = right.rbLeft

    if father.rbRight == node {
        father.rbRight = right
    } else {
        father.rbLeft = right
    }

    right.rbFather = father
    right.rbLeft = node
    node.rbFather = right
    node.rbRight = rightLeft
    rightLeft.rbFather = node
  
    return right
}

左旋右旋时的颜色操作较复杂，在后面讲解插入时再进行讨论。

颜色翻转

颜色翻转相对简单，只有一个节点的两个子节点都是红节点时，才需要进行这种操作。

rb-tree-翻转.png

操作非常简单，只有修改相应节点的颜色即可：

func filpColorOneNode(node *RbNode) {
    if nil == node {
        return
    }
    if RED == node.color {
        node.color = BLACK
    } else {
        node.color = RED
    }
}

// Flip Color
func filpColor(node *RbNode) {
    if nil == node || nil == node.rbLeft || nil == node.rbRight {
        return
    }

    filpColorOneNode(node)
    filpColorOneNode(node.rbLeft)
    filpColorOneNode(node.rbRight)
}

插入操作

插入操作相对较简单，我将它划分为两个阶段：

寻找插入点。
插入并进行平衡调整

寻找插入点

插入首先要找到相应的插入点，红黑树是一个二叉查找树，寻找插入点的操作是一个查询的操作，这里我们可以简单的用递归来实现。由于红黑树是一个相对平衡的二叉树，在由于3亿节点的情况下，其高度也只有30多层，因此，我们不用太担心递归层数太高导致栈内存耗尽的情况。（一般进程的栈空间有8MB的限制）

// FindAndReturnInsertPos find and return the insert pos
func FindAndReturnInsertPos(root *RbNode, node *RbNode) *RbNode {
    if nil == root || nil == node || root.data == node.data {
        return nil
    }

    if root.data > node.data && nil != root.rbLeft {
        return FindAndReturnInsertPos(root.rbLeft, node)
    } else if root.data < node.data && nil != root.rbRight {
        return FindAndReturnInsertPos(root.rbRight, node)
    } else {
        return root
    }
}

可以看到，我们认为如果data域的值相同时，不应该插入节点，这种情况下会将节点丢弃。

而下面两种情况下，我们认为找到了插入点：

当前节点的数据大于插入节点数据，且其左子节点为空。
当前节点的数据小于插入节点数据，且其右子节点为空。

插入节点并处理平衡

为了不改变红黑树的黑节点平衡，插入节点均为红色节点，这时，根据其父节点的不同，我们有几种不同的处理方式，我们设置插入的这个节点为我们的关注节点：

场景1：如果关注节点是根节点，把颜色改为黑色，插入完成。

rb-tree-Page-5.png

场景2：如果关注节点的父节点是黑色节点，直接完成。

如果关注节点的父节点是红色节点，插入后会产生连续两个红色节点，需要进行调整以避免这种情况。有3种典型场景需要进行处理：

场景3：如果关注节点父节点的兄弟节点（即祖父节点的另一个子节点，叔叔节点）是红色节点时，将祖父节点及其两个子节点（父节点，叔叔节点）进行反色操作，将关注节点设为其祖父节点。

rb-tree-Page-4.png

如果叔叔节点为黑色节点，且其父节点是其祖父节点的左节点时。

场景4.1：如果关注节点是其父节点的右子节点，将关注节点及其父节点做左旋操作。将关注节点设为调整后的子节点，即原先的父节点（图中节点4），目前这个情况任然存在两个连续的红色节点，需要继续调整。

rb-tree-Page-6.png

场景4.2：如果关注节点是其父节点的左子节点，将其父节点和祖父节点进行右旋操作，并交换其颜色。

rb-tree-Page-7.png

如果叔叔节点为黑色节点，且其父节点是其祖父节点的右节点时。

场景5.1：如果关注节点是其父节点的左子节点，将关注节点及其父节点做右旋操作。将关注节点设为调整后的子节点，即原先的父节点5，目前这个情况任然存在两个连续的红色节点，需要继续调整。

rb-tree-Page-8.png

场景5.2：如果关注节点是其父节点的右子节点，将其父节点和祖父节点进行左旋操作，并交换其颜色。

rb-tree-Page-9.png

观察上面的场景，只有4个场景发生的颜色变化：根节点，父亲和叔叔节点为红色，场景4.2，场景5.2，在后面这两个场景中，我们发现其实是最初的插入节点和祖父节点发生了颜色变化，因此平衡的代码可以这样写：

// Balance Rb-Tree
func balance(node *RbNode) {
    if nil == node {
        return
    }

    for {
        var father *RbNode = node.rbFather
        if nil == father.rbFather {
            father.color = BLACK
            return
        }
        if BLACK == father.color {
            return
        }

        var grandFather *RbNode = father.rbFather
        if nil != grandFather.rbLeft &&
            nil != grandFather.rbRight &&
            grandFather.rbLeft.color == RED &&
            grandFather.rbRight.color == RED {

            filpColor(grandFather)
            node = grandFather
            continue
        }

        if father == grandFather.rbLeft {
            if node == father.rbRight {
                rollLeft(father)
            }
    
            rollRight(grandFather)
            filpColorOneNode(node)
            filpColorOneNode(grandFather)
            return
        } else {
            if node == father.rbLeft {
                rollRight(father)
            }

            rollLeft(grandFather)
            filpColorOneNode(node)
            filpColorOneNode(grandFather)
            return
        }

    }
}

删除操作

相比较而言，插入操作还算比较简单，更复杂的是红黑树的删除节点操作。网络上有很多种对这种情况的讲解，很多讲得非常复杂，有的解释甚至是错误的，因此我会尝试以结构化的方式说明红黑树的删除，以帮助更多人来理解它。

我把插入过程分为3个部分：

找到需要删除的节点NodeToDelete
找到NodeToDelete的前继或者后继节点NodeToReplace，这个节点应该是一个叶节点（没有非空子节点的节点）
交换NodeToDelete和NodeToReplace的数据域，删除NodeToReplace，然后处理红黑平衡。

通过这样的步骤，我们把问题简化成了一个删除红黑树叶节点的问题。

寻找需删除节点

和插入时一样，我们利用二叉查找树的特性对待删除节点进行搜索，同样使用递归的方法进行：

// FindNodeByData Find the Node with data in Rb-Tree
func FindNodeByData(root *RbNode, data int) *RbNode {
    if nil == root {
        return nil
    }

    if root.data == data {
        return root
    } else if root.data > data {
        return FindNodeByData(root.rbLeft, data)
    } else {
        return FindNodeByData(root.rbRight, data)
    }
}

可以看到，只有找到数据一样的点，函数才会返回那个节点的指针，如果找不到的话，会返回一个nil。

寻找替代节点

如果直接删除该节点，红黑树的调整会非常复杂。对于复杂的问题，一般的解决思路是，将这个复杂问题转换成几个简单问题的组合，然后再解决这些简单问题。删除一个叶节点需要考虑的场景会比删除一个中间节点的场景要简单很多，那么我们怎样把问题转换成删除叶节点的问题呢？这个叶节点一定是在需要删除的节点的左子树或者右子树中的，在数据域中与要删除节点靠在一起的节点是我们的候选，这个节点一般是其前继或者后继节点。

rb-tree-前继后继.png

如图所示，图中紫色是待删除节点，使用蓝色标记的是前继节点的搜索路径，前继节点是这个路径下最低端的叶节点。同理，棕色则是后继节点的搜索路径，最低端的是后继节点。

其相关代码如下：

func findReplacementNode(node *RbNode) *RbNode {
    if nil == node || (nil == node.rbLeft && nil == node.rbRight) {
        return nil
    }

  // 搜索前继节点
    if nil != node.rbLeft {
        var current = node.rbLeft
        for {
            if nil != current.rbRight {
                current = current.rbRight
            } else {
                break
            }
        }
        return current
    }
    // 搜索后继节点
    if nil != node.rbRight {
        var current = node.rbRight
        for {
            if nil != current.rbLeft {
                current = current.rbLeft
            } else {
                break
            }
        }
        return current
    }

    return nil
}

实际上，被替换节点理论上还是可能有单个红色儿子的情况，但是这种情况非常好处理，只要再做一次replacement即可，最终场景会变成删除单个红叶节点的情况。

删除并进行平衡

我们现在已经把问题简化为了删除叶节点的操作了，但是这样的场景还是比较多，让我们一一来分析。我们先看一这个问题的问题空间是什么样的，我们如果要删除一个叶节点会涉及这样几个节点：

待删除节点
父节点
兄弟节点
兄弟节点的左子节点
兄弟节点的右子节点

场景1：

假设待删除节点是红色，这种情况下，其对应的子树应当处于黑色平衡状态，那么其他几个节点的情况是什么样呢？

父节点的颜色可能是红色吗？由于待删除节点是红色，根据红黑树的定义，其父节点一定是黑色。因为如果父节点是红色，那就会出现两个连续的红色节点，不符合红黑树的定义。
兄弟节点可能是什么颜色呢？假设兄弟节点是红色，这时是满足红黑树定义的。但是，该兄弟节点一定没有非空子节点。那么如果是黑色呢？这时红黑树的黑节点平衡就不满足了，因此兄弟节点只能是红色。
兄弟节点也有可能是空节点，这样同样满足红黑树的定义。

rb-tree-待删节点为红.png

这种情况，直接删除待删除节点即可，不会引起红黑树黑节点平衡的变化。

下表是opNode为红色时可能的状态，其中：

Red，该节点为红色。
Black，该节点为黑色。
nil，该节点为空节点。
not nil，该节点非空。
Any，该节点可以是上述任意情况。

opNode	father	brother	brother's left	brother's right	状态
Red	Black	Red	nil	nil	平衡
Red	Black	nil	nil	nil	平衡
Red	Red	any	any	any	不平衡
Red	Black	Black	any	any	不平衡
Red	Black	red	not nil	not nil	不平衡

以下是对应的实现。

    var father = opNode.rbFather
    if nil == father.rbRight || nil == father.rbLeft {
        // Case1
        // If the opNode's father has only one child
        // Directly remove this node
        // This node should always be Red
        removeSingleNode(opNode)
        return SUCCESS
    }

场景2：

假设待删除节点opNode是黑色，那情况又会是什么样的呢？

场景2.0:

兄弟节点是红色的情况，如果平衡的状况，其兄弟节点的子节点如果存在一定也是黑色的。在该场景中，我们不关心父节点的颜色。

rb-tree-3.0.png

在这种场景下，在其父节点做左旋，并交换父节点和兄弟节点的颜色。在调整后，以原父节点所在的子树，由于要删除一个节点，任何是黑色不平衡的。需要进行后续调整。

            if RED == brother.color {
                // When brother is Red
                // The father should always be Black
                // Brother has 2 Black children
                rollLeft(father)
        var color = father.color
                father.color = brother.color
                brother.color = color
                // father's child changed during rolling
                brother = father.rbRight
            }

场景2.1：

兄弟节点是黑色，这种情况是可能存在的。如下图：

rb-tree-3.1.png

当父节点为黑色时，需要进行的操作是将兄弟节点的颜色变成红色，然后将opNode删除。这样该子树的黑色平衡了，但是整体的黑色节点层数降低了1，需要将父节点重新设置为关注节点进行调整。只是此时关注节点不需要再被删除了。

当父节点为红色时，直接将父节点设为黑色，兄弟节点颜色设为红色，调整完成，实际上，这种情况下兄弟节点不应该有子节点。

场景2.2

当兄弟节点为黑色，且兄弟节点的左儿子为红色，如果此时将待删除节点删除，左子树比右子树的高度小1。需要想办法进行调整。我们将其兄弟节点进行右旋操作。

rb-tree-3.2.png

此时操作尚未结束，状态转换成了后面的场景3.3.

场景2.3

兄弟节点为黑色，其右儿子为红色，我们需要将其更据其父节点进行左旋操作。在完成后，交换父节点和兄弟节点的颜色。然后将兄弟节点的右儿子的颜色置为黑色。

rb-tree-3.3.png

现在我们可以就N作为父节点的左节点的情况，再整理一个表格出来：

场景	N	F	B	BL	BR	操作	状态
2.1.0	黑	黑	黑	空	空	B->红色，F->黑色	完成
2.1.1	黑	黑	黑	黑/空	黑/空	B->红色，设置F为N，重新开始调整，新的N仍然是黑色。如果新的父节点是根节点，则调整结束	继续
2.0	黑	Any	红	Any	Any	在父节点做左旋，交换父节点和兄弟节点的颜色。设兄弟节点左节点为新的兄弟节点	继续
2.2	黑	Any	黑	红	Any	在兄弟节点做右旋，交换兄弟节点与其左子节点的颜色	继续
2.3	黑	Any	黑	Any	红	在父节点做左旋，交换父节点和兄弟节点的颜色，兄弟节点右节点颜色置为黑色	完成

可以看到，2场景中，有2种情况会导致调整结束，其余情况需要继续调整。

其中，2.0情况，调整范围会变得更小，对应状态能在1条件下满足。

2.2调整完后，一定会继续进行2.3中的调整。

而2.1.1的情况，将父节点重新设为调整操作点后，我们可以发现，所有的情况都可以在2场景中找到，这是一种自迭代的情况。因此现在整个条件是完备的。

附上调整的源码

func balance(father *RbNode) int {
    var opNode *RbNode = nil
    for {
        var brother = father.rbRight
        if opNode != brother {
            if RED == brother.color {
                // When brother is Red
                // The father should always be Black
                // Brother has 2 Black children
                rollLeft(father)
                var color = father.color
                father.color = brother.color
                brother.color = color
                // father's child changed during rolling
                brother = father.rbRight
            }
            var brotherRight = brother.rbRight
            if nil == brotherRight || BLACK == brotherRight.color {
                var brotherLeft = brother.rbLeft
                if nil == brotherLeft || BLACK == brotherLeft.color {
                    // When brother is Black, Change it to RED
                    // When father is RED
                    // Change it to Black and adjustion finished
                    // When father is BLACK
                    // Set the Node to it and restart the adjustion
                    brother.color = RED
                    if RED == father.color {
                        father.color = BLACK
                    } else {
                        opNode = father
                        father = opNode.rbFather
                        if nil != father {
                            continue
                        }
                    }
                    return SUCCESS
                }

                // The situation When the brother's left is Red
                rollRight(brother)
                var color = brotherLeft.color
                brotherLeft.color = brother.color
                brother.color = color
                // Set the brother to brotherLeft and continue
                // Now new brother is Black and its right is Red
                brotherRight = brother
                brother = brotherLeft
            }
            // The situation When the brother's right is Red
            rollLeft(father)
            var color = father.color
            father.color = brother.color
            brother.color = color

            brotherRight.color = BLACK
            return SUCCESS
        }
        brother = father.rbLeft
        if RED == brother.color {
            // When brother is Red
            // The father should always be Black
            // Brother has 2 Black children
            rollRight(father)
            var color = father.color
            father.color = brother.color
            brother.color = color
            brother = father.rbLeft
        }

        var brotherLeft = brother.rbLeft
        if nil == brotherLeft || BLACK == brotherLeft.color {
            var brotherRight = brother.rbRight
            if nil == brotherRight || BLACK == brotherRight.color {
                // When brother is Black, Change it to RED
                // When father is RED
                // Change it to Black and adjustion finished
                // When father is BLACK
                // Set the Node to it and restart the adjustion
                brother.color = RED
                if RED == father.color {
                    father.color = BLACK
                } else {
                    opNode = father
                    father = opNode.rbFather
                    if nil != father {
                        continue
                    }
                }
                return SUCCESS
            }

            // The situation When the brother's left is Red
            rollLeft(brother)
            var color = brotherRight.color
            brotherRight.color = brother.color
            brother.color = color
            // Set the brother to brotherLeft and continue
            // Now new brother is Black and its right is Red
            brotherLeft = brother
            brother = brotherRight
        }
        // The situation When the brother's right is Red
        rollRight(father)
        var color = father.color
        father.color = brother.color
        brother.color = color
        brotherLeft.color = BLACK
        return SUCCESS
    }
}

后记

红黑树确实是最难的数据结构之一，我花了大概7个晚上才完成本文，其中理解红黑树花了大部分时间。红黑树的多种实现方式，让人在不知情的情况下会十分迷惑，左旋右旋，颜色变换也让人眼花缭乱。不过，最大的障碍在于，网络上大部分有关红黑树的博文，在涉及删除的部分都是错的或者关键节点上一笔带过，让人很难把握。最后，我是通过阅读Linux源码中的红黑树实现完成了go语言版本的实现。在此记录一下。2020年6月9日于南京家中。

Go语言学习之手撕红黑树

红黑树的特点

平衡操作

左旋，右旋

rb-tree.png

颜色翻转

插入操作

寻找插入点

插入节点并处理平衡

删除操作

寻找需删除节点

寻找替代节点

删除并进行平衡

后记

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读