Sort each statement about a binary search tree by whether it is an invariant of the structure.
Groups: An invariant · Not an invariant
- An in-order traversal yields the values in sorted order
- Every node except the root has exactly one parent
- Every value in a node's left subtree is less than the node's value
- The root currently holds the value 50
- The tree currently holds 12 values
Hints
- An invariant must hold before and after EVERY operation, not merely right now.
- Ask of each statement whether an insertion could make it false without the structure being broken.
Show the answer
An invariant: Every value in a node's left subtree is less than the node's value, Every node except the root has exactly one parent, An in-order traversal yields the values in sorted order
Not an invariant: The tree currently holds 12 values, The root currently holds the value 50
The ordering property, the single-parent rule and the sorted traversal survive every legal operation, so they are invariants. The current size and the current root value change with a single insertion, so they describe this moment rather than a rule, and a checker that asserted them would fire constantly on a perfectly healthy tree.
Practise Debugging Structural Invariants
The app has 6 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.
More questions on Debugging Structural Invariants
- Order the steps of debugging a data structure with an invariant checker.
- An invariant checker is written, run during development, and deleted before release. What was gained, and…
- Select every benefit the lesson attributes to writing an invariant checker.
- An invariant checker is code that verifies a structure's rules and is never called in production. Why is…