CODEWITHSUNDEEP
haskellbinary-search-tree
Mo Beigi
Mo Beigi

Reputation: 1765

What do these properties mean for an insert function for a Binary Search Tree

So my task is to write some properties to check the correctness of an insert function for a BST.

Here is the stub code.

My issue is determining what it is I actually need to do. I've deduced the correct way to insert into the BST is to insert at the proper place (to preserve BST property) and to allow duplicates to be inserted.

Can you help me determine what each property means? Here are my current thoughts:

prop_insert_preserves_bst insertFunction integer
This means check that the structure of the BST is correct. That is, each element is in the proper place and all elements in the left branch have lower values and all elements in the right branch have higher values.

prop_insert_adds_element insertFunction integer
I am confused about this one. Originally I just checked that the new tree (after insertion) container integer. Now I actually check that the new tree is 1 length longer and has 1 new element which is integer.

prop_insert_does_not_change_other_elements insertFunction integer newInteger
For this one I checked that every element in new tree is same as original tree. However I have no idea what newInteger is, I didn't use it in my implementation.

prop_insert_duplicate_check insertFunction integer
This was is even more confusing. Right now I have implemented it in the same way as prop_insert_duplicate_check insertFunction integer. Does it mean that duplicates are accepted and inserted into the tree? (Remember that insertBST function is correct and so must pass all of these properties).

Upvotes: 1

Views: 135

Answers (1)

JP Moresmau
JP Moresmau

Reputation: 7403

You should check with whoever gave you the exercise!

But anyway, I think you're right for the first two. First one, you check that if isBST is true on a Leaf, it's still true after inserting the given integer. Second one, you check has you said the length and the presence of the inserted integer.

For the third one, you insert the first integer, then newInteger and check integer is still present.

For the fourth one, you need to insert the integer twice and check the results are expected. It does look like the current code does not check for duplicates, are you sure you shouldn't fix the insertBST function? If that's right, you need to check the side arguments, if not you need to check inserting twice produced the same tree as inserting once.

Hope this helps.

Upvotes: 3

Related Questions