2

CLRS の教科書に従って赤黒木を実装しようとしています。TreeNode クラスはノードを定義し、ノードを定義するための関数を持ち、ノードが右ノードか左ノードかを判別します。クラス BST はツリー用です。プログラムを実行すると (順番に印刷)、無限ループに入り、ノード self.nil が検出されません。これにより、問題は「insertFix」メソッドにあると思われます。私はおそらくどこかで台無しにしています。

class TreeNode:
    def __init__(self,val,left = None,right = None, parent = None,color = None):
        self.val = val
        self.leftChild = left
        self.rightChild = right
        self.parent = parent
        self.color = color

    def hasLeftChild(self):
        return self.leftChild

    def hasRightChild(self):
        return self.rightChild

    def isLeftChild(self):
        return (self.parent and (self.parent.leftChild == self))

    def isRightChild(self):
        return (self.parent and (self.parent.rightChild == self))

class BST(TreeNode):
    def __init__(self):
        self.root = None
        self.size = 0
        self.nil = TreeNode(None)
        self.nil.color = "black"

    def addNode(self,val):
        self.size += 1
        y = self.nil
        x = self.root
        if self.root == None:
            self.root = TreeNode(val,self.nil,self.nil,self.nil,"black")
        else:
            z = TreeNode(val,self.nil,self.nil, None, "red")
            while x!=self.nil:
                y = x
                if z.val < x.val:
                    x = x.hasLeftChild()
                else:
                    x = x.hasRightChild()
            z.parent = y 
            if y == self.nil:
                self.root = z
            elif z.val < y.val:
                y.leftChild = z
            else:
                y.rightChild = z
            self.treeInsFixer(z)

    def treeInsFixer(self,z):
        while z.parent.color == "red":
            if z.parent == z.parent.parent.leftChild:
                y = z.parent.parent.rightChild
                if y.color == "red":
                    z.parent.color = "black"
                    y.color = "black"
                    z.parent.parent.color = "red"
                    z = z.parent.parent
                else:
                    if z == z.parent.rightChild:
                        z = z.parent
                        self.leftRotate(z)
                    z.parent.color = "black"
                    z.parent.parent.color = "red"
                    self.rightRotate(z.parent.parent)
            elif z.parent == z.parent.parent.rightChild:
                y = z.parent.parent.leftChild
                if y.color == "red":
                    z.parent.color = "black"
                    y.color = "black"
                    z.parent.parent.color = "red"
                    z = z.parent.parent
                else:
                    if z == z.parent.leftChild:
                        z = z.parent
                        self.rightRotate(z)
                    z.parent.color = "black"
                    z.parent.parent.color = "red"
                    self.leftRotate(z.parent.parent)
        self.root.color = "black"               

    def leftRotate(self,x):
        y = x.rightChild
        x.rightChild = y.leftChild
        if y.leftChild != self.nil:
            y.leftChild.parent = x
        y.parent = x.parent
        if x.parent == self.nil:
            self.root = y
        elif x == x.isLeftChild():
            x.parent.leftChild = y
        else:
            x.parent.rightChild = y
        y.leftChild = x
        x.parent = y

    def rightRotate(self,x): 
        y = x.leftChild
        x.leftChild = y.rightChild
        if y.rightChild != self.nil:
            y.rightChild.parent = x
        y.parent = x.parent
        if x.parent == self.nil:
            self.root = y 
        elif x == x.isRightChild():
            x.parent.rightChild = y
        else:
            x.parent.leftChild = y
        y.rightChild = x 
        x.parent = y

    def inOrder(self,x):
        if(x!=self.nil):
            self.inOrder(x.leftChild)
            print(x.val, x.color)
            self.inOrder(x.rightChild)



a = BST()
a.addNode(5)
a.addNode(7)
a.addNode(4)
a.addNode(14)
a.addNode(6)
a.addNode(11)
a.addNode(9)
a.addNode(17)
a.addNode(2)
a.addNode(10)
a.addNode(8)
a.inOrder(a.root)

これには多くのコードを実行する必要があることはわかっていますが、問題を理解しようとして完全に知恵を絞っています。どんな提案でも大歓迎です。

4

1 に答える 1

0

問題はここにあります：

def inOrder(self,x):
    if(x!=self.nil):
        self.inOrder(x.leftChild)
        print(x.val, x.color)
        self.inOrder(x.rightChild)

いつもTrueです。__eq__ __cmp__ __ne__Python は、ノードの値を比較するためにオーバーライドするまで、オブジェクトの ID を比較することによってこれを行うためです。

于 2014-01-29T13:15:57.180 に答える