failing 'test__AVLTree_insert_list(xs): ' test case

[emmacgodfrey]

Hi @mikeizbicki and classmates,

I have been trying to de-bug my code for a couple days now, and I am officially stuck.

When I run the test cases, I keep failing the following case:

_________________________________________________________ test__AVLTree_insert_list __________________________________________________________

    @given(xs=ints)
>   def test__AVLTree_insert_list(xs):

tests/test_AVLTree.py:231: 
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 

xs = [0, 1, 2, 3, -2, -1]

    @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([-2, -1, 0, 1, 2, 3])>()
E        +    where <bound method AVLTree.is_avl_satisfied of AVLTree([-2, -1, 0, 1, 2, 3])> = AVLTree([-2, -1, 0, 1, 2, 3]).is_avl_satisfied

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

However, when I try to debug in python interactive mode, it seems as though my code is working. For example,

>>> avl=AVLTree()
>>> avl.insert_list([0,1,-1,2,-2,3])
>>> str(avl)
'(0 - (-1 - (-2 - - ) - ) - (2 - (1 - - ) - (3 - - ) ) )'
>>> avl.is_avl_satisfied()
True

The only thing that I can think of is that my _right_rotate and _left_rotate functions do not run in logarithmic time due to the deep copy. Could this be causing the failing test case? If so, any suggestions for fixing these functions?

My _left_rotate function is as follows:

 75     @staticmethod
 76     def _left_rotate(node):
 77         '''
 78         FIXME:
 79         Implement this function.
 80 
 81         The lecture videos provide a high-level overview of tree rotations,
 82         and the textbook provides full python code.
 83         The textbook's class hierarchy for their AVL tree code is fairly different from our class h    ierarchy,
 84         however, so you will have to adapt their code.
 85         '''
 86         nodecopy = copy.deepcopy(node)
 87         newroot = nodecopy.right
 88         transfer = newroot.left
 89         newroot.left = nodecopy
 90         nodecopy.right = transfer
 91         return newroot

Thanks in advance,

Emma Godfrey

[mikeizbicki]

The reason that your code is passing when run with interactive python and not when run directly through the test case is that you are actually running on a different list in both scenarios. The key is the line

        xs = list(set(xs))

in the test case, which will change the order of the xs list. On my python, I get

>>> list(set([0, 1, -1, 2, -2, 3]))
[0, 1, 2, 3, -2, -1]

but the order of an iterator of a set is not guaranteed to be the same across python versions, and in particular may be different for you.

To debug this issue, you should be inserting the transformed list in interactive python, rather than the original list.