BST with connection to parent - loop

Question

I have problem with infinite loop in getMinimal() method. It works in this way : 1)Take node, 2)If node has other node on the left - go to other one. 3)Repeat as far as node has sth on the left side 4)Return the minimal node.

But sometimes it works in infinite loop for example from 1000 to 400, then to 4 then..to 1000! I have no ide where I make mistake. I reviewed this code many times,every single "pointer" to parent/left/right node is okay! Please - help. Algorithm works okay to "handwritten" trees - ~20nodes. I wanted to test it in better cases - 2500nodes,generated by random lib (from -10k to 10k).

import random


class Node:
    def __init__(self, val):
    self.val = val
    self.parent = None
    self.right = None
    self.left = None
    # Class of node.
def str(self):
    return str(self.val)


class MyTree:
        def __init__(self, node):
            self.root = node

        def insert(self, node):
            current = self.root
            a = True
            while a:
                if node.val > current.val:
                    if current.right is not None:
                        current = current.right
                        continue
                    else:
                        current.right = node
                        node.parent = current
                        a = False
                if node.val <= current.val:
                    if current.left is not None:
                        current = current.left
                        continue
                    else:
                        current.left = node
                        node.parent = current
                        a = False

        def search(self, node):
            current = self.root

            while node.val != current.val:
                if node.val > current.val:
                    current = current.right
                    continue
                elif node.val <= current.val:
                    current = current.left
                    continue
            if node.val == current.val:
                return current
            else:
                print("There is no such node!")

        def delete(self, node):

            if isinstance(node, (float, int)):
                node = self.search(node)

            if node is self.root:
                self.__deleteRoot()
                return
            else:
                if node.right is None and node.left is None:
                    self.__deleteNN(node)
                    return
                if node.right is None and node.left is not None:
                    self.__deleteLN(node)
                    return
                if node.right is not None and node.left is None:
                    self.__deleteNR(node)
                    return
                if node.right is not None and node.left is not None:
                    self.__deleteLR(node)
                    return

        def __deleteNN(self, node):
            if node.parent.left is node:
                node.parent.left = None
            if node.parent.right is node:
                node.parent.right = None

        def __deleteLN(self, node):
            parent = node.parent
            son = node.left
            # parent replaced
            if parent.left is node:
                parent.left = son
            if parent.right is node:
                parent.right = son
            son.parent = parent


        def __deleteNR(self,node):
            parent = node.parent
            son = node.right
            # replace parent
            if parent.left is node:
                parent.left = son
            if parent.right is node:
                parent.right = son
            son.parent = parent

        def __deleteLR(self, node):

            minimal = self.getMinimal(node.right)
            if minimal.parent.left is minimal:
                minimal.parent.left = None
            if minimal.parent.right is minimal:
                minimal.parent.right = None
            # parent of minimal done..
            if node.parent.left is node:
                node.parent.left = minimal
            if node.parent.right is node:
                node.parent.right = minimal
            minimal.right = node.right
            minimal.left = node.left

        def getMinimal(self, node):
            k = node
            while k.left is not None:
                k = k.left
            return k

        def getMax(self):
            current = self.root
            while current.right:
                current = current.right
            return current

        def __trav(self, node):
            if not node:
                return
            print(node.val)
            self.__trav(node.left)
            self.__trav(node.right)

        def printTrav(self):
            self.__trav(self.root)

        def __deleteRoot(self):
            if self.root.left is None and self.root.right is None:
                self.root = None
                return
            if self.root.left is None and self.root.right is not None:
                # left empty,right full
                self.root.right.parent = None
                self.root = self.root.right
                return
            if self.root.left is not None and self.root.right is None:
                # right empty, left full
                self.root.left.parent = None
                self.root = self.root.left
                return
            # node has both children
            if self.root.left is not None and self.root.right is not None:
                temp = self.getMinimal(self.root.right)  # minimal from right subtree
                # sometimes it could be like this..
                # r
                #   \
                #    x
                if temp.parent.left is temp:
                    temp.parent.left = None
                else:
                    temp.parent.right = None

                self.root.left.parent = temp
                self.root.right.parent = temp
                temp.right = self.root.right
                temp.left = self.root.left
                self.root = temp
                self.root.parent = None

                return

        def search(self, val):
            node = self.root
            if node.val == val:
                return node
            if val > node.val and node.right is not None:
                node = node.right
            if val < node.val and node.left is not None:
                node = node.left
            else:
                print("There's no such value!")
                return
        def printMax(self):
            print(self.getMax().val)
        def printMin(self):
            print(self.getMinimal(self.root).val)

arr=[None]*2500
for x in range(2500):
     arr[x]=Node(random.randint(-10000,10000))

myTree = MyTree(arr[0])
for x in range(1,2500):
     myTree.insert(arr[x])

for x in range(2500):
     myTree.delete(arr[x])

What is the purpose of the `getMinimal` method? Please edit the question to explain what problem you are trying to solve. It is rather difficult to say what's wrong with the code if we don't know what it's trying to do. See https://stackoverflow.com/help/how-to-ask — kaya3, Nov 29 '19 at 22:27
So - https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/ If I want to delete node with two nodes (left and right) I have to find a minimal node on right subtree. Then I have to delete my node, and insert minimal instead. My problem is (I think) a bug in code (maybe in deleting). Search "causes" infinite loop. — , Nov 29 '19 at 22:41
Please fix the indentation of your code and fix the duplicate method name `search`. — trincot, Nov 30 '19 at 17:05
@trincot - It's not duplicate - it's overloaded. One searches node as a object, other one searches first node by passed value. — , Nov 30 '19 at 17:12
Can you please fix the indentation though, as currently it is not clear what belongs to what? — trincot, Nov 30 '19 at 17:24
And this is not overloading, but (useless) overwriting as Python does not support overloading like in (for instance) Java. See [here](https://stackoverflow.com/questions/10202938/how-do-i-use-method-overloading-in-python) — trincot, Nov 30 '19 at 17:29
@patrykoz You are still ignoring the fact that Python does not support overloading. Have one search method, and an if based on whether you got a node or not. — btilly, Dec 02 '19 at 19:21
@btilly I changed a lot of in code, Finally - it works okay. Now I'm testing for 100k nodes. Thanks for help,but actionally I found bug in pointers. Ofc I rearranged the code,and deleted one search. — , Dec 03 '19 at 01:09

score 0 · Answer 1 · answered Nov 29 '19 at 23:51

It is suspicious that you define search twice.

Still that said, here is how I would debug this. I would modify your program to read from a file, try to run, and then detect an endless loop and bail out. Now write random files until you have one that causes you to crash.

Once you have a random file that shows the bug, the next step is to make it minimal. Here is a harness that can let you do that.

import itertools
flatten = itertools.chain.from_iterable

# bug_found should be a function that takes a list of elements and runs your test.
# example should be an array that demonstrates the bug.
def find_minimal (bug_found, example):
    parts = [example]
    while 1 < max(len(part) for part in parts):
        i = 0
        while i < len(parts):
            if 1 == len(parts[i]):
                i = i + 1
            else:
                part = parts.pop(i)
                # Divide in 2.
                mid = len(part)/2
                part1 = part[0:mid]
                part2 = part[mid:len(part)]

                # Do we need part1?
                parts.insert(i, part1)
                if bug_found(flatten(parts)):
                    i = i + 1
                    parts.insert(i, part2)
                else:
                    parts[i] = part2

                # Do we need part2?
                if bug_found_func(flatten(parts)):
                    i = i + 1
                else:
                    parts.pop(i)
    return list(flatten(parts))

Just let it run, and after some time it is likely to find a small example. Which will greatly aid in debugging.

So, endless loop is in search, because pointers in nodes are wrond. For example (sometimes): node a has itself as left. In other case it's like this a.left = b, b.left = c,c.left=a - it causes infinite loop. But I don't know what is wrong in my pointers - in deleting roots, or in deleting nodes? — , Dec 01 '19 at 01:03
@patrykoz My suggestion is about how to generate a minimal example from a random one. The hope is that a minimal example is small enough to run through by hand so that you can see where something happens that is wrong. — btilly, Dec 02 '19 at 18:27

score 0 · Accepted Answer · answered Dec 03 '19 at 16:43

0

So - I found 2 serious bugs in code. Both in LR ("standard" node and root). As I suspected - bugs were in pointers. Now tree is working (tested few times for 20k,30k and 100k nodes). Solved.

answered Dec 03 '19 at 16:43

BST with connection to parent - loop

2 Answers2