sequence to FULLY test AVL tree implementation???

[Nobody]

I recently wrote an AVL tree class, I think its mostly working, but I want
to make sure. Assuming it uses integers, is there an insert/delete sequence
that is known to exercise every possible case of inserting and deleting?

 

[Ben Pfaff]

I recently wrote an AVL tree class, I think its mostly working, but I want
to make sure. Assuming it uses integers, is there an insert/delete sequence
that is known to exercise every possible case of inserting and deleting?

Excellent question. But you could easily find one yourself by
adding a little bit of instrumentation to your insert and delete
routines and then testing random insert and delete sequences.

 

[John]

deleting?

Excellent question. But you could easily find one yourself by
adding a little bit of instrumentation to your insert and delete
routines and then testing random insert and delete sequences.

I don't think there's much hope of exhaustively "find<ing> one
yourself" because a complete test list is just about uncountably large.
Still there are constructive answers to the issue.

Devise a test case for each of the major conditions in the spec. Then
test to see the spec is met. What if there is an even (or prime, or
2**n) inserts before a similar number of deletes? Consider if the
input sequence is sorted, or reversed, or some other pattern that
challenges the specification.

Each such test that the component passes increases your confidence that
it's "correct".

John

 

[Ben Pfaff]

I don't think there's much hope of exhaustively "find<ing> one
yourself" because a complete test list is just about uncountably large.

It's really not that hard. There are only 10! = 3,628,000
possible orders in which 10 integers can be inserted into a tree.
I bet that several of those exercise all the AVL insertion cases,
and that a large fraction of those cases has a corresponding
deletion order that exercises all the deletion cases. If not,
you can probably go up to at least 13! before the problem starts
to become impractical.

There are only 4 rebalancing cases for AVL insertion and 6
rebalancing cases for AVL deletion, and none of them is
particularly rare in practice. I assumed that these were the
cases the OP was interested in. If he has a broader definition
of "case" then I agree that it's quite possibly impractical.