I am attempting to validate that my threaded binary tree’s insertion and deletion works as intended.

Would it be safe to assume that the following procedure would have tested all corner cases at least once?

I have an array of integer S = {1, 2, …, n-1, n} for n = 1’000’000. I then randomize the order of S to obtain S’ and S*. S’ is then used to insert its elements sequentially, into the tree. After all elements are inserted, I create an in order list of the tree, say A, and confirm that A = S. This concludes the insert test.

For deletion, I pass elements of S* sequentially as argument to be removed from the tree, testing that each call was successful. After all elements was removed I confirm that the tree is empty.

  • $\begingroup$ Do you have standard Binary Search Tree (not self-balancing) with double threads (left and right)? $\endgroup$ – Evil Feb 25 '16 at 16:22
  • $\begingroup$ @EvilJS Not self-balancing, with only right as thread. $\endgroup$ – MSR Feb 25 '16 at 16:47
  • $\begingroup$ That's what correctness proofs were invented for. $\endgroup$ – Raphael Feb 25 '16 at 17:26

Shortly - no, it is not safe.
Huge random test does not guarantee success (but of course, when there is a bug, it finds it in the most cases).
To test threaded tree with deletion and insertion you need to have saturated all nodes (with thread links), make them change thread, the same for deletion.
To make sure it works all corner cases must be covered both for insertion and deletion. With huge input there is huge probability it works, but this is not conclusive. Also making more passes (more test) it increases probability of success, but nothing more.

To test it manually - case by case - you do not need very big tree (I did tests on double threaded AVL, tree height was maximally 5).

| cite | improve this answer | |
  • $\begingroup$ So this method is good to roughly test if the program is bug free, but it is not conclusive. $\endgroup$ – MSR Feb 25 '16 at 16:47
  • $\begingroup$ Yes, this is really good at finding errors, early testing, with very high probability. If code / algorithm has some bugs it finds them quickly, but it is too weak to say that for sure algorithm is bug free. In case of trees this is better test because there are only several cases. But if random generator has bug, and test cases are generated to pass? Increasing test size will not help, and there is still hidden bug. $\endgroup$ – Evil Feb 25 '16 at 16:56
  • $\begingroup$ Let me give extreeme example: some algorithm to be tested gets one double (floating point value, let it be 80bits). And the error occurs only for one value (not 0, as this is often tested). Picking numbers randomly does not guarantee that this value occurs, even for days... So maybe checking not randomly but all values? Exhausting double values is not the best idea, and test is conclusive, but only for given size of double - if it changes (64bit, 128bit) - we still do not know if it works. $\endgroup$ – Evil Feb 25 '16 at 17:08

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.