青涩的红黑树Python实现

很难想象有这么一天我能写出这么抽象的代码。
一般我是将这类代码归结为脑残一类，但是由于是我自己码的，所以暂以青涩称呼 : )。
好消息是根据红黑树插入和删除的每种情况分别写了不同的代码并打上了详细的注释(并不)，以后忘了的时候方便复习。
言归正传，为了方便调试，我用pyside2给红黑树写了一个简单的显示界面：


viewer.png

界面的代码如下(也很青涩)：

from PySide2 import QtCore, QtGui, QtWidgets
import sys
import RBtree

def fillTree(tree:RBtree.RBTree):
    tree.insert(40)
    tree.insert(30)
    tree.insert(2)
    tree.insert(10)
    tree.insert(60)
    tree.insert(55)
    tree.insert(51)
    tree.insert(48)

    tree.delete(60)
    pass

class RBNode(QtWidgets.QGraphicsItem):
    def __init__(self, value, color, parent= None):
        super(RBNode, self).__init__()
        self.item = QtCore.QRectF(0, 0, 40, 40)
        self.value = str(value)
        self.parent = parent
        #print(value)
        self.color = QtGui.QColor(255, 0, 0) if color else QtGui.QColor(0, 0, 0)

    def boundingRect(self):
        return self.item
    
    def paint(self, painter, option, widget = None):
        painter.setRenderHint(QtGui.QPainter.Antialiasing, True)
        if self.parent:
            painter.setPen(QtCore.Qt.blue)
            painter.drawLine(QtCore.QPointF(20, 20), self.mapFromScene(self.parent.scenePos()+ QtCore.QPointF(20, 20)) )

        painter.setBrush(self.color)
        painter.drawEllipse(self.item)
        painter.setPen(QtCore.Qt.white)
        painter.drawText(QtCore.QRectF(10, 10, 50, 50), self.value)


class RBScene(QtWidgets.QGraphicsScene):
    def __init__(self):
        super(RBScene, self).__init__()
        self.tree = RBtree.RBTree(50)
        fillTree(self.tree)
        self.fillScene()

    def fillScene(self):
        rbnode = self.tree.base.left
        node = RBNode(rbnode.value, rbnode.color)
        self.addItem(node)
        self.circle(rbnode.left, node, False, 1.0)
        self.circle(rbnode.right, node, True, 1.0)

    def circle(self, rbNode:RBtree.RBTree, parent:RBNode, dir:bool, k):
        if not rbNode:
            return
        node = RBNode(rbNode.value, rbNode.color, parent)
        pos = parent.scenePos()

        k = k* 0.5
        time = k* 400

        if dir:
            pos += QtCore.QPointF(time, time)
        else:
            pos += QtCore.QPointF(-time, time)
        node.setPos(pos)
        self.addItem(node)

        self.circle( rbNode.left, node, False, k)
        self.circle( rbNode.right, node, True, k)
    
    def addNode(self, rbNode, pos):
        node = RBNode(rbNode.value, rbNode.color)
        node.setPos(pos)
        self.addItem(node)
        return node

class RBView(QtWidgets.QGraphicsView):
    def __init__(self):
        super(RBView, self).__init__()
        self.setScene(RBScene())

class RBWindow(QtWidgets.QMainWindow):
    def __init__(self):    
        super(RBWindow, self).__init__()
        self.view = RBView()
        self.setCentralWidget(self.view)

if __name__ == "__main__":
    app = QtWidgets.QApplication(sys.argv)
    window = RBWindow()
    window.setGeometry(500, 300, 1200, 1200)
    window.show()
    sys.exit(app.exec_())

RB-Tree：

class Node():
    def __init__(self, value):
        self.color = False # False: Black, #True: Black
        self.value = value

        self.parent = None
        self.lr = False # False: left, True: right

        self.left = None
        self.right = None

class RBTree():
    def __init__(self, rootValue):
        self.base = Node(-1)
        self.root = Node(rootValue)
        self.root.parent = self.base
        self.root.lr = False
        self.base.left = self.root
        self.count = 1
    
    def findNode(self, value):
        node = self.base.left
        while True:
            if value == node.value:
                return node

            elif value > node.value:
                if node.right:
                    node = node.right
                else:
                    return False
            else:
                if node.left:
                    node = node.left
                else:
                    return False

    def leftRot(self, newNode, parent, grand):
        brother = parent.right
        parent.parent = grand.parent
        parent.right = grand
        parent.lr = grand.lr
        if grand.lr:
            grand.parent.right = parent
        else:
            grand.parent.left = parent
        parent.color = False
        grand.parent = parent
        grand.left = brother
        grand.color = True
        grand.lr = True
        if brother:
            brother.parent = grand


    def rightRot(self, newNode, parent, grand):
        brother = parent.left
        parent.parent = grand.parent
        parent.left = grand
        parent.color = False
        parent.lr = grand.lr
        if grand.lr:
            grand.parent.right = parent
        else:
            grand.parent.left = parent

        grand.right = brother
        grand.parent = parent
        grand.color = True
        grand.lr = False
        if brother:
            brother.parent = grand

    def insert(self, value):
        #part 1 find pos and insert
        node = self.base.left
        newNode = Node(value)
        newNode.color = True
        while True:
            if value > node.value:
                if node.right:
                    node = node.right
                else:
                    node.right = newNode
                    newNode.parent = node
                    newNode.lr = True
                    break
            else:
                if node.left:
                    node = node.left
                else:
                    node.left = newNode
                    newNode.parent = node
                    newNode.lr = False
                    break
        
        #part2 resort
        while True:
            # parent is black
            parent = newNode.parent
            if not parent.color:
                break
            
            uncle = None
            uncleColor = False
            grand = parent.parent
            parentLR = parent.lr
            if grand:
                uncle = grand.left if parentLR else grand.right
            if uncle:
                uncleColor = uncle.color
            # parent is red, uncle is black or None
            if not uncleColor:
                #parent on left
                if not parentLR:
                    #new node on left
                    if not newNode.lr:
                        self.leftRot( newNode, parent, grand)
                    #new node on right
                    else:
                        newNode.left = parent
                        newNode.parent = grand
                        newNode.lr = False
                        parent.right = None
                        parent.parent = newNode
                        parent.lr = False
                        grand.left = newNode

                        self.leftRot( parent, newNode, grand)
                #parent on right
                else:
                    #new node on left
                    if not newNode.lr:
                        newNode.parent = grand
                        newNode.right = parent
                        newNode.lr = True
                        parent.left =  None
                        parent.parent = newNode
                        parent.lr = True
                        grand.right = newNode

                        self.rightRot(parent, newNode, grand)
                    #new node on right
                    else:
                        self.rightRot(newNode, parent, grand)

                break
            # parent is red, uncle is red
            else:
                if uncle:
                    uncle.color = False
                parent.color = False
                # if is root, break  
                if self.base.left == grand:
                    grand.color = False
                    break
                #else: loop
                grand.color = True

                newNode = grand

    def nullNode(self, node):
        node.parent = None
        Node.left = None
        Node.right = None

    def delete(self, value):
        delNode = self.findNode(value)
        if not delNode: return False

        parent = delNode.parent
        grand = parent.parent
        brother = parent.left if delNode.lr else parent.right

        lchild = delNode.left
        rchild = delNode.right

        # left loop search single branch node or zero branch node
        while lchild and rchild:
            delNode.value = lchild.value
            delNode = lchild
            parent = delNode.parent
            grand = parent.parent
            brother = parent.left if delNode.lr else parent.right
            lchild = delNode.left
            rchild = delNode.right
        
        # if delnode is red
        # just del node
        if delNode.color:
            if delNode.lr:
                parent.right = None
            else:
                parent.left = None
            self.nullNode(delNode)
            return True
        # del Node is black
        if lchild or rchild:
            #child must be red
            if lchild:
                if delNode.lr:
                    parent.right = lchild
                else:
                    parent.left= lchild
                lchild.parent = parent
                lchild.lr = delNode.lr
                lchild.color = False
            else:
                if delNode.lr:
                    parent.right = rchild
                else:
                    parent.left= rchild
                rchild.parent = parent
                rchild.lr = delNode.lr
                rchild.color = False
                self.nullNode(delNode)
            return True
        
        # no child
        
        # if brother is red
        # brother must have two black child
                #step 1: del frist
        brother = parent.left if delNode.lr else parent.right
        if delNode.lr:
            parent.right = None
        else:
            parent.left = None
        self.nullNode(delNode)

        while True:
            blNode = brother.left
            brNode = brother.right

            if brother.color:
                #step 2: resort

                # parent left rot

                brother.color = False
                brother.parent = parent.parent
                brother.lr = parent.lr

                parent.color = True
                parent.parent = brother
                if delNode.lr:
                    brother.right = parent
                    parent.left = brNode
                    parent.right = None
                    parent.lr = True
                else:
                    brother.left = parent
                    parent.right = blNode
                    parent.left = None
                    parent.lr = False
                
                return True
            
            # brother is black
            # brother child is all null : error
            # brother child have |1 red |

            # if bl is red
            if blNode:
                # step 1: brother right rot
                # step 2: parent left rot
                if brother.lr:
                    parent.right = blNode
                    blNode.parent = parent
                    blNode.lr = brother.lr
                    blNode.right = brother
                    brother.parent = blNode
                    brother.left = None

                    blNode.parent = parent.parent
                    blNode.lr = parent.lr
                    blNode.color = parent.color
                    blNode.left = parent
                    if parent.lr:
                        parent.parent.right = blNode
                    else:
                        parent.parent.left = blNode
                    parent.parent = blNode
                    parent.lr = False
                    parent.color = False
                    parent.right = None
                    
                else:
                    # parent right rot
                    brother.parent = parent.parent
                    brother.right = parent
                    brother.lr = parent.lr
                    brother.color = parent.color
                    if parent.lr:
                        parent.parent.right = brother
                    else:
                        parent.parent.left = brother
                    parent.lr = True
                    parent.color = False
                    parent.parent = brother
                    parent.left = brNode
                    blNode.color = False
                return True
            # if bl is red
            if brNode:
                if brother.lr:
                    brother.parent = parent.parent
                    brother.lr = parent.lr
                    brother.left = parent
                    brother.color = parent.color
                    if parent.lr:
                        parent.parent.right = brother
                    else:
                        parent.parent.left = brother
                    parent.parent = brother
                    parent.lr = False
                    parent.color = False
                    parent.right = blNode
                    brNode.color = False
                
                else:
                    brNode.parent = parent
                    brNode.right = brother
                    brNode.lr = brother.lr
                    parent.left = brNode
                    brother.parent = brNode
                    brother.lr = True
                    brother.left = None

                    brNode.lr = parent.lr
                    brNode.color = parent.color
                    brNode.right = parent
                    brNode.parent = parent.parent
                    if parent.lr:
                        parent.parent.right = brNode
                    else:
                        parent.parent.left = brNode
                    parent.parent = brNode
                    parent.lr = True
                    parent.color = False
                    parent.right = None
                return True
            
            #if brother have no child
            # parent is red
            if parent.color:
                parent.color = False
                brother.color = True
                return True
            
            # parent and brother is black

            brother.color = True
            delNode = parent
            parent = parent.parent
            brother = parent.left if delNode.lr else parent.right
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 230,563评论 6赞 544
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 99,694评论 3赞 429
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 178,672评论 0赞 383
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 63,965评论 1赞 318
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 72,690评论 6赞 413
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 56,019评论 1赞 329
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 44,013评论 3赞 449
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 43,188评论 0赞 290
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 49,718评论 1赞 336
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 41,438评论 3赞 360
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 43,667评论 1赞 374
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 39,149评论 5赞 365
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 44,845评论 3赞 351
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 35,252评论 0赞 28
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 36,590评论 1赞 295
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 52,384评论 3赞 400
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 48,635评论 2赞 380