AVL tree balanced in interactive mode but failing test cases

[amyyu116]

One of my test cases failed while I was running them, so I tried it in interactive mode to see what the issue was. However, when I ran the same commands in interactive mode, it seemed to pass:

python3 -i containers/AVLTree.py
>>> avl = AVLTree()
>>> avl.insert_list([0,1,-1,2,3,-33,-34,-35])
>>> avl.is_avl_satisfied()
True

On the other hand, when I run pytest commands, I receive this message:

xs = [0, 1, 2, 3, -34, -35, ...]

    @given(xs=ints)
    def test__AVLTree_insert_list(xs):
        xs = list(set(xs))
        avl = AVLTree()
        avl.insert_list(xs)
        assert avl.is_bst_satisfied()
>       assert avl.is_avl_satisfied()
E       assert False
E        +  where False = <bound method AVLTree.is_avl_satisfied of AVLTree([-35, -34, -33, -1, 0, 1, 2, 3])>()
E        +    where <bound method AVLTree.is_avl_satisfied of AVLTree([-35, -34, -33, -1, 0, 1, 2, 3])> = AVLTree([-35, -34, -33, -1, 0, 1, 2, 3]).is_avl_satisfied

tests/test_AVLTree.py:228: AssertionError
---------------------------------- Hypothesis ----------------------------------
Falsifying example: test__AVLTree_insert_list(
    xs=[0, 1, -1, 2, 3, -33, -34, -35],
)

I am not sure how to approach fixing this, since my code seems to be working properly when I enter the commands into interactive mode.

[mikeizbicki]

The problem is that the list you are inserting in interactive mode is different than the list the test cases are inserting because you are skipping the calls to the list and set functions. In particular, these lines will reorder the values in the list:

>>> xs=[0, 1, -1, 2, 3, -33, -34, -35]
>>> list(set(xs))
[0, 1, 2, 3, -34, -35, -1, -33]

Calling your insert_list function on this reordered list will likely allow you to reproduce the error.

[amyyu116]

Hi Mike, I took your suggestion and reproduced the test line by line, and this is what came out of interactive mode.

$ python3 -i containers/AVLTree.py
>>> xs=[0, 1, -1, 2, 3, -33, -34, -35]
>>> list(set(xs))
[0, 1, 2, 3, -34, -35, -1, -33]
>>> avl = AVLTree()
>>> avl.insert_list(xs)
>>> avl.is_avl_satisfied()
True

It doesn't seem like calling list or set is reproducing the error.

[irajmoradi]

Hello,

I think you need to on the second line of the interactive python actually assign xs to the new list(set(xs)) because otherwise you don’t change xs at all. See the line below for what you should replace the second line of interactive python with.

xs = list(set(xs))

[amyyu116]

I've found the issue. Looks like I had to run check for the rebalance function over the whole tree instead of just the ancestors of the inserted value? Either way, thank you so much for your help!