AVL tree python

272 просмотра
0
0 Комментариев

Здравствуйте. При написании алгоритма для AVL столкнулся с проблемой. На больших объемах данных (от 10000 элементов) при удалении каждого 10 элемента алгоритм ломается в связи с тем, что какой-то элемент оказывается типа None. Ручной debuging не помог. Мог бы кто-нибудь подсказать почему или же посоветовать более простую имплементацию данного алгоритма в данном языке программирования? Заранее благодарен.

Update: Проблема в удалениии элемента. Однако не известно до сих под где именно.

from colored import fg, attr
import random
 
order = []
with_par = []
res = ""
tmp = 0
 
 
# operations with elements
class BSTNode:
 
    def __init__(self, val = None, left=None, right=None, parent=None):
        self.valtemp = val
        self.leftCh = left
        self.rightCh = right
        self.parent = parent
        self.status = 0
 
    # is right /left child
    def isRch(self):
        return self.parent.rightCh == self
 
    def isLch(self):
        return self.parent.leftCh == self
 
    # has right / left child
    def hRch(self):
        return self.rightCh != None
 
    def hLch(self):
        return self.leftCh != None
 
    def isRoot(self):
        return not self.parent
 
    # check if it's leaf
    def isLeaf(self):
        return not (self.hLch() or self.hRch())
 
    # check if has al least one child
    def hCh(self):
        return (self.hRch() or self.hLch() and not self.hChs())
 
    # check if have both children
    def hChs(self):
        return (self.hLch() and self.hRch())
 
    def replaceData(self, val, leftCh, rightCh):
        self.valtemp = val
        self.leftCh = leftCh
        self.rightCh = rightCh
        if self.leftCh:
            self.leftCh.parent = self
        if self.rightCh:
            self.rightCh.parent = self
 
    def findSucc(self):
        succ = None
        if self.rightCh:
            succ = self.rightCh
            while succ.leftCh:
                succ = succ.leftCh
        else:
            if self.parent:
                if self.isLch():
                    succ = self.parent
                else:
                    self.parent.rightCh = None
                    succ = self.parent.findSucc()
                    self.parent.rightCh = self
        return succ
 
 
 
class BST:
    # python standard options
    # initialization
    def __init__(self):
        self.root = None
        self.size = 0
 
    # check if items exist in BST
    def __contains__(self, val):
        if self.tempGet(val, self.root):
            return True
        else:
            return False
 
    # function to add item
    def reset(self):
        if self.root is None:
            return False
        else:
            self.resetTemp(self.root)
            self.root = None
 
    def resetTemp(self, start):
        if start is not None:
            self.resetTemp(start.leftCh)
            self.resetTemp(start.rightCh)
            start.leftCh = None
            start.rightCh = None
            start.valtemp = None
            start.parent = None
 
    def add(self, val):
        # if items exist add element with subfunction tempAdd
        if self.root:
            self.tempAdd(val, self.root)
        # else make them as a root
        else:
            self.root = BSTNode(val)
        self.size += 1
        # print("Success, element №", int(self.size), "was added")
 
    def tempAdd(self, val, curNode):
        # checking elements and compare with their values
        if val <= curNode.valtemp:
            if curNode.hLch():
                # if item has left child, go next to this element with recursive function
                self.tempAdd(val, curNode.leftCh)
            else:
                # if current item has no left child, make temp item as their left child
                curNode.leftCh = BSTNode(val, parent=curNode)
                self.updateBalance(curNode.leftCh)
        else:
            # if item is more then checking element and have right child - go recursive to the right child with this function
            if curNode.hRch():
                self.tempAdd(val, curNode.rightCh)
            # if item is more then checking element and have no right child, make them as a child of current element
            else:
                curNode.rightCh = BSTNode(val, parent=curNode)
                self.updateBalance(curNode.rightCh)
 
    def rotateLeft(self, rotRoot):
        newRoot = rotRoot.rightCh
        rotRoot.rightCh = newRoot.leftCh
        if newRoot.leftCh != None:
            newRoot.leftCh.parent = rotRoot
        newRoot.parent = rotRoot.parent
        if rotRoot.isRoot():
            self.root = newRoot
        else:
            if rotRoot.isLch():
                rotRoot.parent.leftCh = newRoot
            else:
                rotRoot.parent.rightCh = newRoot
        newRoot.leftCh = rotRoot
        rotRoot.parent = newRoot
        rotRoot.status = rotRoot.status + 1 - min(newRoot.status, 0)
        newRoot.status = newRoot.status + 1 + max(rotRoot.status, 0)
 
    def rotateRight(self, rotRoot):
        newRoot = rotRoot.leftCh
        rotRoot.leftCh = newRoot.rightCh
        if newRoot.rightCh != None:
            newRoot.rightCh.parent = rotRoot
        newRoot.parent = rotRoot.parent
        if rotRoot.isRoot():
            self.root = newRoot
        else:
            if rotRoot.isLch():
                rotRoot.parent.leftCh = newRoot
            else:
                rotRoot.parent.rightCh = newRoot
        newRoot.rightCh = rotRoot
        rotRoot.parent = newRoot
        rotRoot.status = rotRoot.status - 1 - max(newRoot.status, 0)
        newRoot.status = newRoot.status - 1 + min(0, rotRoot.status)
 
    def updateBalance(self, node):
        if node.status > 1 or node.status < -1:
            self.reBalance(node)
            return
        if node.parent != None:
            if node.isLch():
                node.parent.status += 1
            else:
                node.parent.status -= 1
            if node.parent.status != 0:
                self.updateBalance(node.parent)
 
    def reBalance(self, node):
        if node.status < 0:
            if node.rightCh.status > 0:
                self.rotateRight(node.rightCh)
                self.rotateLeft(node)
            else:
                self.rotateLeft(node)
        elif node.status > 0:
            if node.leftCh.status < 0:
                self.rotateLeft(node.leftCh)
                self.rotateRight(node)
            else:
                self.rotateRight(node)
 
    # function to get element with it's value
    def get(self, value):
        # check if root exist, if yes - go to subfunction tempGet
        if self.root:
            res = self.tempGet(value, self.root)
            # if item with such value exist: return them key
            if res:
                return res
            else:
                print("Error, element is not exist")
        else:
            print("Error, BST is empty")
 
    def tempGet(self, val, curNode):
        # check if element exist
        if not curNode:
            return None
        # check if element's value is this that was needed
        elif curNode.valtemp == val:
            return curNode
        # check if element's value is mare then was searching
        elif val < curNode.valtemp:
            return self.tempGet(val, curNode.leftCh)
        # check if element's value is less then was searching
        else:
            return self.tempGet(val, curNode.rightCh)
 
    def remove(self, val):
        if self.size > 1:
            curNode = self.tempGet(val, self.root)
            if curNode:
                if curNode.isLeaf():  # this is leaf
                    if curNode == curNode.parent.leftCh:
                        curNode.parent.leftCh = None
                        curNode.parent.status -= 1
                        if curNode.parent.status < -1:
                            self.updateBalance(curNode.parent)
                    else:
                        curNode.parent.rightCh = None
                        curNode.parent.status += 1
                        if curNode.parent.status > 1:
                            self.updateBalance(curNode.parent)
                elif curNode.hChs():  # this is interior node
                    succ = curNode.findSucc()
                    if succ.isLeaf():
                        if succ.isLch():
                            succ.parent.leftCh = None
                        else:
                            succ.parent.rightCh = None
                    elif succ.hCh():
                        if succ.leftCh:
                            if succ.isLch():
                                succ.parent.leftCh = succ.leftCh
                            else:
                                succ.parent.rightCh = succ.leftCh
                            succ.leftCh.parent = succ.parent
                        else:
                            if succ.isLch():
                                succ.parent.leftCh = succ.rightCh
                            else:
                                succ.parent.rightCh = succ.rightCh
                            succ.rightCh.parent = succ.parent
                    if succ.isLch():
                        succ.parent.status -= 1
                        self.updateBalance(succ.parent)
                    elif succ.isRch():
                        succ.parent.status += 1
                        self.updateBalance(succ.parent)
                    curNode.valtemp = succ.valtemp
 
                else:  # this node has one child
                    if curNode.leftCh:
                        if curNode.isLch():
                            curNode.leftCh.parent = curNode.parent
                            curNode.parent.leftCh = curNode.leftCh
                            curNode.parent.status -= 1
                            self.updateBalance(curNode.parent)
                        elif curNode.isRch():
                            curNode.leftCh.parent = curNode.parent
                            curNode.parent.rightCh = curNode.leftCh
                            curNode.parent.status += 1
                            self.updateBalance(curNode.parent)
                        else:
                            curNode.replaceData(curNode.leftCh.valtemp, curNode.leftCh.leftCh, curNode.leftCh.rightCh)
                    else:
                        if curNode.isLch():
                            curNode.rightCh.parent = curNode.parent
                            curNode.parent.leftCh = curNode.rightCh
                            curNode.parent.status -= 1
                            self.updateBalance(curNode.parent)
                        elif curNode.isRch():
                            curNode.rightCh.parent = curNode.parent
                            curNode.parent.rightCh = curNode.rightCh
                            curNode.parent.status += 1
                            self.updateBalance(curNode.parent)
                        else:
                              curNode.replaceData(curNode.rightCh.valtemp,curNode.rightCh.leftCh, curNode.rightCh.rightCh)
                self.size -= 1
            else:
                print("Error, element is not exist")
        elif self.size == 1 and self.root.valtemp == val:
            self.root = None
            self.size -= 1
        elif self.root is None:
            print("Sorry, your tree is clean")
 
    def inOrd(self):
        global order
        order = []
        if self.root:
            self.inOrdtmp(self.root)
            print("{}{:*^150}{}".format(fg(46), "Elements wroten with help of inorder method", attr(0)))
            print(order)
        else:
            print("{}{:*^150}{}".format(fg(1), " Sorry, your tree is clear ", attr(0)))
 
    def inOrdtmp(self, start):
        if start is not None:
            self.inOrdtmp(start.leftCh)
            order.append(start.valtemp)
            self.inOrdtmp(start.rightCh)
 
ls = []
tree = BST()
n=1000
while len(ls) != n:
    a = random.randrange(n * 5)
    if a not in ls:
        ls.append(a)
        tree.add(a)
for i in range(len(ls), 0, -10):
    tree.remove(ls[i])
    ls.remove(ls[i])


Добавить комментарий

0 Answers

Python Опубликовано 12.12.2018
Напишите свой ответ на данный вопрос.
Scroll Up