紅黑樹-添加

本質還是一顆二叉搜索樹，只是在其基礎上增加了AddFix和RemoveFix來做平衡性修正，確保不會出現極端不平衡的情況，

【規則】

a) 根節點為黑

b) 紅色節點的子節點只能是2個黑

c) 黑色節點的子節點只能是：1個紅，2個紅，2個黑或沒有子節點，不可能出現1個黑（如下圖所示）

d) 任一結點到各個葉子結點的路徑都包含數量相同的黑色結點

e) 新添加的節點一開始總是為紅色，后面根據需要調整顏色

# 根據上面的規則，下面的這些情況也不可能出現

a) 

 b)

c)

# 紅黑樹看似很復雜，其實只是程序比較繁瑣而已，他對什么情況做什么操作都已經規定死了，只要照著這些規定的步驟走就行了，

【添加】

# 當遇到新添加節點后，出現連續的紅色時，需要做修正

# 添加會遇到的所有情況：

uncle表示父節點的兄弟節點，gparent表示祖父節點，root表示根節點

# 情況1-1，parent和uncle設為黑色

 # 情況1-2，parent，uncle設為黑色，gparent設為紅色；然后將gparent作為當前節點繼續往上處理，直到不再有連續的紅色

# 情況2-1，右旋(繞藍色描邊節點)，gparent設為紅，parent設為黑

a) 不存在uncle

 b) 存在uncle

# 情況2-2，左旋，gparent設為紅，parent設為黑

a) 不存在uncle

b) 存在uncle

# 情況3-1，先左旋，變為情況2-1，然后再右旋

a) 不存在uncle

b) 存在uncle

# 情況3-2，先右旋，變為情況2-2，然后再左旋

a) 不存在uncle

b) 存在uncle

# 添加的代碼同二叉搜索樹，這邊只展示添加后的修正

function BRTree:_AddFix(curNode, curNodeIsLeft, parent, parentLevel, stack)
    while nil ~= parent and not parent.isBlack do
        local gparent = stack[parentLevel-1]
        local uncle = nil
        local parentIsLeft = gparent.left == parent
        if parentIsLeft then
            uncle = gparent.right
        else
            uncle = gparent.left
        end

        if nil ~= uncle and not uncle.isBlack then --uncle存在且為紅
            parent.isBlack = true
            uncle.isBlack = true
            if gparent == self.root then --情況1-1: gparent為root
                return
            end
            gparent.isBlack = false

            local ggparentLevel = parentLevel - 2
            local ggparent = stack[ggparentLevel]
            if ggparent.isBlack then
                return
            end
            --情況1-2: ggparent肯定存在且不為root
            curNode = gparent
            parentLevel = ggparentLevel
            parent = ggparent
            curNodeIsLeft = (parent.left == curNode)
        elseif nil == uncle or uncle.isBlack then --uncle不存在或為黑
            local ggparent = stack[parentLevel-2]
            if parentIsLeft then
                if curNodeIsLeft then --同側1, 情況2-1
                    self:_RightRotate(gparent, ggparent)
                    parent.isBlack = true
                    gparent.isBlack = false
                else --不同側1, 情況3-1
                    self:_LeftRotate(parent, gparent)
                    local temp = parent
                    parent = curNode
                    curNode = temp
                    self:_RightRotate(gparent, ggparent)
                    parent.isBlack = true
                    gparent.isBlack = false
                end
            else
                if curNodeIsLeft then --不同側2, 情況3-2
                    self:_RightRotate(parent, gparent)
                    local temp = parent
                    parent = curNode
                    curNode = temp
                    self:_LeftRotate(gparent, ggparent)
                    parent.isBlack = true
                    gparent.isBlack = false
                else --同側2, 情況2-2
                    self:_LeftRotate(gparent, ggparent)
                    parent.isBlack = true
                    gparent.isBlack = false
                end
            end
            return
        end
    end
end

# 紅黑樹的節點定義，比BSTree的節點多了個isBlack來記錄顏色

local Node = {}
Node.__cname = "util.BRTree.Node"
Node.__index = Node

function Node.new(v)
    local obj = {}
    setmetatable(obj, Node)
    obj:ctor(v)
    return obj
end

function Node:ctor(v)
    self.value = v
    self.left = nil
    self.right = nil
    self.isBlack = false
end

# 左旋和右旋

---@param subTreeRoot "旋轉節點"
---@param subTreeParent "旋轉節點的父節點"
function BRTree:_LeftRotate(subTreeRoot, subTreeParent)
    local newSubTreeRoot = subTreeRoot.right
    subTreeRoot.right = newSubTreeRoot.left
    newSubTreeRoot.left = subTreeRoot

    if subTreeRoot == self.root then
        self.root = newSubTreeRoot
    else
        if subTreeRoot == subTreeParent.left then
            subTreeParent.left = newSubTreeRoot
        else
            subTreeParent.right = newSubTreeRoot
        end
    end
end

function BRTree:_RightRotate(subTreeRoot, subTreeParent)
    local newSubTreeRoot = subTreeRoot.left
    subTreeRoot.left = newSubTreeRoot.right
    newSubTreeRoot.right = subTreeRoot

    if subTreeRoot == self.root then
        self.root = newSubTreeRoot
    else
        if subTreeRoot == subTreeParent.left then
            subTreeParent.left = newSubTreeRoot
        else
            subTreeParent.right = newSubTreeRoot
        end
    end
end

【參考】

# 淺析紅黑樹（RBTree）原理及實作_芮小譚的博客-CSDN博客_紅黑樹

# 紅黑樹之洗掉節點 - 青兒哥哥 - 博客園 (cnblogs.com)

# 紅黑樹從頭至尾插入和洗掉結點的全程演示圖_v_JULY_v的博客-CSDN博客

標籤：其他

上一篇：湖倉一體天花板，大資料一站式互動式SQL分析技術

下一篇：什么是3D建模？