"John" <jp********@irisinternet.net> writes:
Ben Pfaff wrote: "Nobody" <no****@cox.net> writes:
> 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.
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.
--
"A computer is a state machine.
Threads are for people who cant [sic] program state machines."
--Alan Cox