1
$\begingroup$

I've recently implemented RB tree, B-Tree and vEB tree. I was wondering however if there's any rule of thumb for testing if my implementation are actually correct.

Is there any reference that can tell how to develop proper test cases for such data structures?

Besides from mathematical techniques maybe.

What about graph in general?

| cite | improve this question | |
$\endgroup$
2
$\begingroup$

Identify the representation invariants. Add assert statements to check that the representation invariant holds (sometimes called a repOK function). Use random testing to generate millions of test cases, and check that no assert ever fires.

Build a reference implementation of the abstract data type that implements all of the methods, but instead of using your data structure, implements the same semantics using some known-good data structure (e.g., a simple list or something). Use random testing to generate millions of test cases, and check that in every case your implementation produces the same results as the reference implementation.

This isn't perfect but it'll probably be pretty good.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you be more specific for example with the red-black tree and, maybe harder, the vEB tree? $\endgroup$ – user8469759 Aug 27 '18 at 9:42
  • $\begingroup$ @user8469759, No, because this answer isn't specific to red-black trees or vEB trees, so I don't see anything to be more specific about. Was there anything in particular that you found unclear about the suggestions in my answer? $\endgroup$ – D.W.♦ Aug 27 '18 at 14:41
  • $\begingroup$ I just can't see the invariants I should test for the cases in my question. $\endgroup$ – user8469759 Aug 27 '18 at 15:52
  • $\begingroup$ @user8469759, test all of them. If you are asking what are the invariants of a red-black tree, or of a vEB tree, I suggest you ask that separately (one question per data structure, please) -- but make sure to first put some thought into it, do some searching, and list all the invariants you've been able to come up with on your own. You might find that with a combination of searching + thought on your own you can come up with the invariants. For instance, the invariants of a red-black tree are usually listed as part of its definition. $\endgroup$ – D.W.♦ Aug 27 '18 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.