BRTree红黑树-添加修正

2022/3/28 23:52:46

本文主要是介绍BRTree红黑树-添加修正,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

本质还是一颗二叉搜索树,只是在其基础上增加了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博客

 



这篇关于BRTree红黑树-添加修正的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程