Trying to understand how to write proof of correctness. Searched over the internet on how to write proof of correctness but can't find a good solution for it.

The following sorting algorithm is proposed using the AVL tree: AVL input of all elements, and printing them in order.

Algorithm - Sort AVL (A[1..n])

T -> Empty AVL Tree.

  • for each 1 <= i <= n

    insert A[i] to T.

    print T elements by using in-order fashion.

Prove the correctness of the algorithm by showing the in-order scan of binary tree is always in ascending order.

  • $\begingroup$ There's nothing special about AVL trees here. The same result would hold for any binary search tree. $\endgroup$ – Yuval Filmus May 21 at 14:49

AVL trees, like all other binary search trees, have the following guarantee:

Suppose that $v$ is a node with left child $l$ and right child $r$. If $x$ is a node in the subtree rooted at $l$ and $y$ is a node in the subtree rooted at $r$ then $key(x) \leq key(v) \leq key(y)$.

Using this, you can easily prove by induction that the inorder traversal of a binary search three produces a list of keys in nondecreasing order.


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.