Golang實作紅黑樹

盼望已久的五一終于到來了！我一直在考慮要不要利用這幾天時間好好睡上一覺，習慣成自然，宅也是如此。睡覺都覺得無聊的時候，就有了寫點什麼的念頭。也借此機會提高一下寫作能力，看看什麼時候能寫一部長篇小說。

用Golang實作紅黑樹算是一次嘗試，畢竟工作環境沒用到，不知道以後會不會用。自己也是看着玩，開闊一下思路。從我開始看Golang的doc到寫這篇文章利用的是大概2周中的業餘時間，是以Golang的文法掌握的還有欠缺；很多特性，例如高并發等都還沒有測試，如文中出現錯誤或不合理的地方，請指正。

本文應用的基本邏輯參考自wiki的紅黑樹，依據golang的語言特性部分結構可能稍有改動。同時這篇文章裡也加入了我在實作過程中的想法和實作時可能會遇到的問題。wiki上的紅黑樹中文版本，不過建議直接看英文版本，不知道是翻譯的原因還是版本沒跟上，中文版本很多有助于了解的重要資訊丢失了。而且最後附的源碼我也大概看了一下，和上面解釋的邏輯在細節上也稍有不同，如果看的話要注意。

由于代碼比較占空間，我在文章裡隻說重點代碼結構，完整代碼在我的github上，有興趣的可以去看一下，位址：rbtree源碼

進入正題，下面我将介紹紅黑樹基于Golang的實作，及實作過程中我自己的了解。主要有以下内容：

1. 紅黑樹特點

紅黑樹的特點說明來自wiki，我這裡簡單翻譯一下，括号裡面的注是我自己的了解。

節點不是紅色就是黑色

節點的根是黑色。這條有時會被忽略。過程中根一般由紅色轉為黑色，卻沒必要由黑色轉為紅色，這條規則會在分析時有一定影響（注：沒明白這影響指什麼……）

所有的空葉子節點都是黑色的（注：注意是空葉子節點，這個特性在插入裡面用不到；在節點删除裡面起作用，有點小坑，講删除時會提到）

如果一個節點是紅色，那麼它的兩個子節點都是黑色（注：也就是說樹裡面不會出父子節點都是紅色的情況）

從任意一個節點到這個節點後代的每一個空葉子節點的直接路徑都要經過相同個數的黑色節點。這裡有幾個定義：從根節點到某個節點所經過的黑色節點的數目成為這個節點的 black depth；從根節點到葉子節點的所經過的黑色節點數目成為這個樹的 black-height

black-height可以用來計算時間複雜度，通過性質4、5可以計算出紅黑樹查詢的時間複雜度為O( log2n )，這裡不細證明。

再補充一點，每次插入的節點初始時都是紅色，這個在添加的時候會說到，提前說一下有助于了解。

後兩條是重點，當然，從這兩條也能看出紅黑樹并不是一個完全的平衡二叉樹，它的平衡在于黑色節點的平衡，上圖（注：每個葉子節點都有2個空的葉子節點，文章中所有紅黑樹的圖裡面不是必要時我就不畫了，顯得太亂）:

Golang實作紅黑樹

紅黑樹的特征就是這些，下面我們将按照這些特征利用Golang建樹

2. 紅黑樹結構的建立

2.1 節點結構

節點有紅黑兩色，我們先定義2個常量。布爾型足夠：

const (
    // RED 紅樹設為true
    RED bool = true
    // BLACK 黑樹設為false
    BLACK bool = false
)

然後是節點結構，包括樹共有的特性：節點的值，指向父節點、左右兒子節點的3個指針；還有紅黑樹特有的：顔色。下面是樹的結構：

// RBNode 紅黑樹
type RBNode struct {
    value               int64
    color               bool
    left, right, parent *RBNode
}

還有一些查找父節點，兄弟節點的方法，很簡單，就不細說了。

// getGrandParent() 擷取父級節點的父級節點
func (rbnode *RBNode) getGrandParent() *RBNode {'代碼略……'}

// getSibling() 擷取兄弟節點
func (rbnode *RBNode) getSibling() *RBNode {'代碼略……'}

// GetUncle() 父節點的兄弟節點
func (rbnode *RBNode) getUncle() *RBNode {'代碼略……'}

2.2 樹的結構

樹的結構隻包含一個根節點Root，還有很多方法，等介紹插入删除時再細說，代碼結構如下:

type RBTree struct {
    root *RBNode
}

2.3 樹的旋轉

節點的結構裡面有個方法很重要，是整個紅黑樹的一個核心功能，那就是樹的旋轉。添加和删除過程中都多次應用到了樹的旋轉。下面就講一下旋轉的細節。對旋轉比較熟的就可以直接看下一部分了。

先定義旋轉常量：

const (
    // 左旋
    LEFTROTATE bool = true
    // 右旋
    RIGHTROTATE bool = false
)

樹的旋轉包括左旋和右旋，下面圖解說明

Golang實作紅黑樹

左旋：以P為軸心左旋，N原來的父節點P作為N節點的左孩子，原N節點的左孩子變為P節點的右孩子，左旋就完成了。

Golang實作紅黑樹

右旋：與左旋類似，隻是把N節點的右孩子變為了P節點的左孩子。

需幾點注意：

節點左旋必須有右孩子，右旋必須有左孩子。

如果N經過旋轉變成了根節點，一定要記得将RBTree結構體中的根節點指針root指向N，這是容易出錯的地方。

旋轉代碼如下：

// rotate() true左旋/false右旋
// 若有根節點變動則傳回根節點
func (rbnode *RBNode) rotate(isRotateLeft bool) (*RBNode, error) {
    var root *RBNode
    if rbnode == nil {
        return root, nil
    }
    if !isRotateLeft && rbnode.left == nil {
        return root, errors.New("右旋左節點不能為空")
    } else if isRotateLeft && rbnode.right == nil {
        return root, errors.New("左旋右節點不能為空")
    }

    parent := rbnode.parent
    var isleft bool
    if parent != nil {
        isleft = parent.left == rbnode
    }
    if isRotateLeft {
        grandson := rbnode.right.left
        rbnode.right.left = rbnode
        rbnode.parent = rbnode.right
        rbnode.right = grandson
    } else {
        grandson := rbnode.left.right
        rbnode.left.right = rbnode
        rbnode.parent = rbnode.left
        rbnode.left = grandson
    }
    // 判斷是否換了根節點
    if parent == nil {
        rbnode.parent.parent = nil
        root = rbnode.parent
    } else {
        if isleft {
            parent.left = rbnode.parent
        } else {
            parent.right = rbnode.parent
        }
        rbnode.parent.parent = parent
    }
    return root, nil
}

3. 節點的插入

插入相對來說簡單一些，首先是一個查找樹的插入，然後是分治法進行樹的變化以符合紅黑樹特征

3.1 資料的插入

二叉查找樹的插入方式，沒啥好說的，直接上代碼：

func (rbtree *RBTree) insertNode(pnode *RBNode, data int64) {
    if pnode.value >= data {
        // 插入資料不大于父節點，插入左節點
        if pnode.left != nil {
            rbtree.insertNode(pnode.left, data)
        } else {
            tmpnode := NewRBNode(data)
            tmpnode.parent = pnode
            pnode.left = tmpnode
            rbtree.insertCheck(tmpnode)
        }
    } else {
        // 插入資料大于父節點，插入右節點
        if pnode.right != nil {
            rbtree.insertNode(pnode.right, data)
        } else {
            tmpnode := NewRBNode(data)
            tmpnode.parent = pnode
            pnode.right = tmpnode
            // 插入驗證
            rbtree.insertCheck(tmpnode)
        }
    }
}

3.2 插入時樹結構的檢查及變化

檢查分幾種情況，下面依次說明：

1. 要檢查的節點沒有父節點，意為此節點為root，則設定此節點的顔色為黑色（一開始提到過，插入時的節點初始時都是紅色），直接傳回，若不是根節點，則進行情況2的檢查。

2. 如果添加節點的父節點是黑色，那就省事兒多了。插入的是紅色，不影響黑色數量，且由于父節點是黑色，不會出現父子節點都是紅色的情況。性質4、5都不受影響。

3. 若添加點的父節點也是紅色，那就得考慮考慮了，這裡應用了分治法，包括添加的節點N，N的父節點P，N的叔父節點U，N的祖父節點G。

Golang實作紅黑樹

下一步就是根據U節點的顔色進入不同流程，G左邊的節點中有相鄰的2個紅色節點，肯定有一個要變成黑色，相應右邊也要有變成黑色的點。這樣，如果U是紅色，則可直接變成黑色；若本身就是黑色，那就得用旋轉的方法尋找平衡了，下面先說U節點是紅色的情況。

a) 若U為紅色，則P與U都直接變成黑色，這樣這部分每條路線上都多了一個黑色節點，需再減去一個以達到外部的平衡，然後把G改為紅色。這樣又會出現一個問題，那就是G的父節點的顔色未知，如果也是紅色，那就又不符合規則了。又出現了要檢查的内容。我們直接把這個問題扔給上一級，讓上一級去解決，直到解決完成，即用遞歸的方式處理（N或P是左孩子還是右孩子沒有關系，這裡為了友善，隻寫出一個）。

Golang實作紅黑樹

b) 若U為黑色，則進入旋轉平衡階段。

3.3 插入節點時的樹的旋轉情況

内容比較多，就拿出來單說了。這裡是紅黑樹插入的重要步驟。樹的旋轉需注意把根節點的情況考慮進去，我們先寫左旋和右旋的方法，實作如下：

func (rbtree *RBTree) rotateLeft(node *RBNode) {
    if tmproot, err := node.rotate(LEFTROTATE); err == nil {
        if tmproot != nil {
            rbtree.root = tmproot
        }
    } else {
        log.Printf(err.Error())
    }
}

以上是左旋的實作，右旋類似，不再贅述。

下面是旋轉平衡的幾種情況：

N是P的左（右）孩子，P同樣是G的左（右）孩子，則隻需以G為軸進行左（右）旋，然後把P改為黑色，G改為紅色。左右黑色節點數目不變，且不影響外部的規則。

Golang實作紅黑樹
N是P的右（左）孩子，而P是G的左（右）孩子

我們需以P為軸左旋（右邊那種情況為右旋）。這時我們會發現樹現在變成了1的情況，再用1的邏輯去處理就行了，同樣這種旋轉方式不會影響每個路徑上的黑色節點數目，且結果頂點處的節點為黑色，不破壞外部的資料。

Golang實作紅黑樹

這樣，插入的情況便都考慮到了，下面是實作代碼：

func (rbtree *RBTree) insertNode(pnode *RBNode, data int64) {
    if pnode.value >= data {
        // 插入資料不大于父節點，插入左節點
        if pnode.left != nil {
            rbtree.insertNode(pnode.left, data)
        } else {
            tmpnode := NewRBNode(data)
            tmpnode.parent = pnode
            pnode.left = tmpnode
            rbtree.insertCheck(tmpnode)
        }
    } else {
        // 插入資料大于父節點，插入右節點
        if pnode.right != nil {
            rbtree.insertNode(pnode.right, data)
        } else {
            tmpnode := NewRBNode(data)
            tmpnode.parent = pnode
            pnode.right = tmpnode
            rbtree.insertCheck(tmpnode)
        }
    }
}
func (rbtree *RBTree) insertCheck(node *RBNode) {
    if node.parent == nil {
        // 檢查1：若插入節點沒有父節點，則該節點為root
        rbtree.root = node
        // 設定根節點為black
        rbtree.root.color = BLACK
        return
    }

    // 父節點是黑色的話直接添加，紅色則進行處理
    if node.parent.color == RED {
        if node.getUncle() != nil && node.getUncle().color == RED {
            // 父節點及叔父節點都是紅色，則轉為黑色
            node.parent.color = BLACK
            node.getUncle().color = BLACK
            // 祖父節點改成紅色
            node.getGrandParent().color = RED
            // 遞歸處理
            rbtree.insertCheck(node.getGrandParent())
        } else {
            // 父節點紅色，父節點的兄弟節點不存在或為黑色
            isleft := node == node.parent.left
            isparentleft := node.parent == node.getGrandParent().left
            if !isleft && isparentleft {
                rbtree.rotateLeft(node.parent)
                rbtree.rotateRight(node.parent)

                node.color = BLACK
                node.left.color = RED
                node.right.color = RED
            } else if isleft && !isparentleft {
                rbtree.rotateRight(node.parent)
                rbtree.rotateLeft(node.parent)

                node.color = BLACK
                node.left.color = RED
                node.right.color = RED
            } else if isleft && isparentleft {
                node.parent.color = BLACK
                node.getGrandParent().color = RED
                rbtree.rotateRight(node.getGrandParent())
            } else if !isleft && !isparentleft {
                node.parent.color = BLACK
                node.getGrandParent().color = RED
                rbtree.rotateLeft(node.getGrandParent())
            }
        }
    }
}

4. 節點的删除

4.1 删除節點的轉換

删除主要有3種情況

要删除的節點N沒有子節點，可直接删除，然後驗證平衡性
要删除的節點N有一個子節點S，則需将S的父節點設為N的父節點P，如果N是P的左兒子節點，就把P的左子節點設成S，右邊同理。
要删除的節點N有2個兒子S1和S2，這樣直接删除會麻煩很多。我們利用一下排序二叉樹的性質，進行一下轉換。過程如下：

a) 選擇右子樹中的節點作替換（左右無所謂，道理是一樣的，我們以替換右子樹中的節點為例）

b) 找到節點N右子樹中最靠左邊的非空節點M（不一定是葉子節點），将M的值複制到N，然後把要删除的節點改為M，則轉換成了删除節點中包含有一個子節點（或沒有子節點）的問題，例如下圖中我們如果要删除5，則尋找節點7的最左側的非空節點6，将6複制到5的位置，然後排序樹仍然成立（原來的6要删除了，不考慮在内）

Golang實作紅黑樹

4.2 删除含單個子節點的節點

删除含單個子節點的節點也包括删除沒有子節點的節點。如果要删除的節點沒有子節點，為了轉換友善，我們需在沒有子節點的節點上加上一個臨時節點，顔色為黑色，作為左孩子還是右孩子都可以。新加的節點雖然暫時破環了平衡，但是不影響旋轉等操作（下面處理過程中能看出來）。最後記得删除即可。

删除含單個子節點的節點也包括幾種情況：

删除的是根節點，且節點沒有子節點，則直接删除，root置空。
删除的是根節點，且節點隻有一個子節點，直接删除，将根節點指向子節點，并設定顔色為黑色
删除的是非根節點，又分幾種情況

a) 要删除的節點是紅色，則它的父節點與子節點（如果有的話）都是黑色，直接把子節點或空節點替換要删除節點的位置即可，不會影響黑節點的平衡

Golang實作紅黑樹
b) 要删除的是黑色節點，但它的子節點存在且是紅色，我們要做到隻是用子節點替換它，然後改變子節點為黑色，使黑色平衡

Golang實作紅黑樹
c) 要删除的是黑色節點且子節點也是黑色，這就需要檢驗平衡了，檢查替換後的孩子節點，下面一節會說明

4.3 删除時樹結構的檢查及變化

由上一節我們能了解到需要檢查平衡的是要删除的節點與它的子節點N都是黑色的情況，很大程度上簡化了樹的檢查。

我們把替換後的節點用N表示，N是黑色。N的兄弟節點為了不和子節點弄混，我們用B表示。B的2個兒子分别用S1和S2表示。N的父節點稱為P。

下面是幾種情況:

N是根節點，直接設成黑色，退出。（存在遞歸的情況，這個必須有）
B是紅色。由性質4和5，及N及N的原始父親都是黑色可判斷，如果B是紅色，則它的父親P是黑色，它的2個子樹都是存在的且都是黑色（這點在邏輯過程中判斷是否為空很重要）。

我們以N節點是P節點的左孩子為例，需要以P為軸左旋。把B作為最頂層，顔色設為黑色。P的顔色設為紅色。這個單元上所有路徑上的黑色節點數量不變。這裡需注意，N節點的兄弟節點變成了S1。由于N的路徑上還少一個黑色節點（已删除的父節點），整體平衡尚未成功，我們仍需努力，還有内部的解決辦法，接着往下走。

Golang實作紅黑樹
P為黑色，B和它的2個子節點都是黑色（若子節點為空也算是黑色，由于golang的指針沒有cpp那麼神奇，這裡需在邏輯中寫明），為了維護單元内的平衡，我們需把B節點設為紅色，這樣内部黑色節點是平衡的，不過單元整體少了一個黑色節點。自己解決不了那就扔給上一層去解決吧，不在其位不謀其政。這裡有個遞歸需注意。

Golang實作紅黑樹
如果P是紅色，B和它的2個子節點（或空節點）都是黑色，我們隻需把P設成黑色，B設成紅色即可，還記得情形1中的那種情況嗎？這樣就補全丢失的黑色了

Golang實作紅黑樹
如果B是黑色，S1是紅色，S2是黑色（N是P的左孩子的情況下）。則需以B為軸進行右旋，讓B的左子樹指針變空（為了統一到第6種情況處理），這時N的路徑還還少一個黑色節點

Golang實作紅黑樹
大部分情況都考慮的差不多了，還有一種情況就是B節點為黑色，B節點的右孩子為紅色（5形成的這種情況）。這時需要以P為軸進行左旋，然後交換P與B的顔色，即P為黑色，B未知。S2變為黑色。這樣使單元内恢複平衡，且整個樹的各個路徑與删除前一緻

Golang實作紅黑樹

樹的删除分析就結束了，下面是實作代碼：

// 删除對外方法
func (rbtree *RBTree) Delete(data int64) {
    rbtree.delete_child(rbtree.root, data)
}

// 删除節點
func (rbtree *RBTree) delete_child(n *RBNode, data int64) bool {
    if data < n.value {
        if n.left == nil {
            return false
        }
        return rbtree.delete_child(n.left, data)
    }
    if data > n.value {
        if n.right == nil {
            return false
        }
        return rbtree.delete_child(n.right, data)
    }

    if n.right == nil || n.left == nil {
        // 兩個都為空或其中一個為空，轉為删除一個子樹節點的問題
        rbtree.delete_one(n)
        return true
    }

    //兩個都不為空，轉換成删除隻含有一個子節點節點的問題
    mostLeftChild := n.right.getLeftMostChild()
    tmpval := n.value
    n.value = mostLeftChild.value
    mostLeftChild.value = tmpval

    rbtree.delete_one(mostLeftChild)

    return true
}

// 删除隻有一個子節點的節點
func (rbtree *RBTree) delete_one(n *RBNode) {
    var child *RBNode
    isadded := false
    if n.left == nil {
        child = n.right
    } else {
        child = n.left
    }

    if n.parent == nil && n.left == nil && n.right == nil {
        n = nil
        rbtree.root = n
        return
    }
    if n.parent == nil {
        n = nil
        child.parent = nil
        rbtree.root = child
        rbtree.root.color = BLACK
        return
    }

    if n.color == RED {
        if n == n.parent.left {
            n.parent.left = child

        } else {
            n.parent.right = child
        }
        if child != nil {
            child.parent = n.parent
        }
        n = nil
        return
    }

    if child != nil && child.color == RED && n.color == BLACK {
        if n == n.parent.left {
            n.parent.left = child

        } else {
            n.parent.right = child
        }
        child.parent = n.parent
        child.color = BLACK
        n = nil
        return
    }

    // 如果沒有孩子節點，則添加一個臨時孩子節點
    if child == nil {
        child = NewRBNode)
        child.parent = n
        isadded = true
    }

    if n.parent.left == n {
        n.parent.left = child
    } else {
        n.parent.right = child
    }

    child.parent = n.parent

    if n.color == BLACK {
        if !isadded && child.color == RED {
            child.color = BLACK
        } else {
            rbtree.deleteCheck(child)
        }
    }

    // 如果孩子節點是後來加的，需删除
    if isadded {
        if child.parent.left == child {
            child.parent.left = nil
        } else {
            child.parent.right = nil
        }
        child = nil
    }
    n = nil
}

// deleteCheck() 删除驗證
func (rbtree *RBTree) deleteCheck(n *RBNode) {
    if n.parent == nil {
        n.color = BLACK
        return
    }
    if n.getSibling().color == RED {
        n.parent.color = RED
        n.getSibling().color = BLACK
        if n == n.parent.left {
            rbtree.rotateLeft(n.parent)
        } else {
            rbtree.rotateRight(n.parent)
        }
    }
    //注意：這裡n的兄弟節點發生了變化，不再是原來的兄弟節點
    is_parent_red := n.parent.color
    is_sib_red := n.getSibling().color
    is_sib_left_red := BLACK
    is_sib_right_red := BLACK
    if n.getSibling().left != nil {
        is_sib_left_red = n.getSibling().left.color
    }
    if n.getSibling().right != nil {
        is_sib_right_red = n.getSibling().right.color
    }
    if !is_parent_red && !is_sib_red && !is_sib_left_red && !is_sib_right_red {
        n.getSibling().color = RED
        rbtree.deleteCheck(n.parent)
        return
    }
    if is_parent_red && !is_sib_red && !is_sib_left_red && !is_sib_right_red {
        n.getSibling().color = RED
        n.parent.color = BLACK
        return
    }
    if n.getSibling().color == BLACK {
        if n.parent.left == n && is_sib_left_red && !is_sib_right_red {
            n.getSibling().color = RED
            n.getSibling().left.color = BLACK
            rbtree.rotateRight(n.getSibling())
        } else if n.parent.right == n && !is_sib_left_red && is_sib_right_red {
            n.getSibling().color = RED
            n.getSibling().right.color = BLACK
            rbtree.rotateLeft(n.getSibling())
        }
    }
    n.getSibling().color = n.parent.color
    n.parent.color = BLACK
    if n.parent.left == n {
        n.getSibling().right.color = BLACK
        rbtree.rotateLeft(n.parent)
    } else {
        n.getSibling().left.color = BLACK
        rbtree.rotateRight(n.parent)
    }
}

後記

第一次這麼寫東西實在是沒經驗，也沒計劃好時間，本來計劃是拿來練手的，原本計劃一天寫完，沒想中途遇上各種問題，拖了将近2天才完成。不過一回生二回熟，相信如果下一次再碰到這種情況就快多了。

說實話，我寫的這些裡面介紹golang的很少，主要是紅黑樹的邏輯。在用golang實作的過程中，我也參考了一些Docker等架構源碼的寫法或方式。給我的感覺是這個語言很特别，單從代碼結構上就能感覺出來，文法類似C語系，不過一個類型名後置就能感受到它的不同。期間也嘗試着寫服務，試着寫過幾個route，效率、負載什麼的還沒具體測試，不過從建構方式上就能感覺到它确實很友善。用不用先放在一邊，看一看還是有好處的。

Golang實作紅黑樹

1. 紅黑樹特點

2. 紅黑樹結構的建立

2.1 節點結構

2.2 樹的結構

2.3 樹的旋轉

3. 節點的插入

3.1 資料的插入

3.2 插入時樹結構的檢查及變化

3.3 插入節點時的樹的旋轉情況

4. 節點的删除

4.1 删除節點的轉換

4.2 删除含單個子節點的節點

4.3 删除時樹結構的檢查及變化

後記

繼續閱讀

Golang學習筆記 - 13 :結構體

Golang學習——結構體struct(二)一.匿名結構體和匿名字段二.結構體嵌套三.結構體模拟繼承性

Golang 基礎知識(十一.struct結構體)

Golang 内聯結構體 Struct embedding

golang 學習（二十四）結構體struct 和 json之間的轉換結構體struct 和 json之間的轉換

golang中結構體與jsongolang中結構體與json

golang結構體tag編譯錯誤的問題

Golang結構體中的tag

Go語言之map與結構體初入map結構體初入（場景map的value通常為struct）

Go初探 (5) – 結構體與接口

Go 結構體方法指針和值的差別

06結構體、接口結構體接口

【Electron】Error: A dynamic link library (DLL) initialization routine failed.

Golang如何寫能進入文檔的測試先看看效果吧可測試的Example結語

PAT (Top Level) Practise 1007 Red-black Tree (35)

最小化DevOps自動化流程(Golang)