Skip to main content

Binary Search Trees

A binary search tree keeps a set of values ordered for lookup, insertion, and minimum and maximum queries [Sedgewick and Wayne]. Here a HeyVL domain specifies the trees, and recursive procedures implement these operations. Do the membership, minimum, and maximum procedures return the right answers, and does insertion keep the tree ordered?

Caesar verifies partial correctness under the tree axioms, using the specifications of recursive calls. The @uwlp annotation selects unbounded greatest fixed point semantics for the Boolean specifications written with ?(...).

Representing Trees​

The Tree domain declares an empty tree nil(), a node constructor node, and selectors for each node's integer value and children:

Tree Constructors and Selectors
domain Tree {
// Constructors for the empty tree and a node with two children.
func nil(): Tree
func node(left: Tree, value: Int, right: Tree): Tree

// Selectors recover the corresponding argument of a constructed node.
func left_child(tree: Tree): Tree
axiom left_child_node forall left: Tree, value: Int, right: Tree.
left_child(node(left, value, right)) == left

func root_value(tree: Tree): Int
axiom root_value_node forall left: Tree, value: Int, right: Tree.
root_value(node(left, value, right)) == value

func right_child(tree: Tree): Tree
axiom right_child_node forall left: Tree, value: Int, right: Tree.
right_child(node(left, value, right)) == right

// A tree is empty precisely when it equals nil().
func is_nil(tree: Tree): Bool
axiom is_nil_def forall tree: Tree.
is_nil(tree) == (tree == nil())

// A constructed node is never empty.
axiom node_not_nil forall left: Tree, value: Int, right: Tree.
node(left, value, right) != nil()

These axioms do not say that every tree is built from finitely many nodes. The proofs therefore do not establish that recursion terminates for every value of type Tree.

Checking Membership​

The recursive function contains specifies whether a value occurs at the root or in either subtree:

Membership Predicate
// Membership holds at the root or in either subtree.
func contains(tree: Tree, value: Int): Bool =
ite(
is_nil(tree),
false,
(value == root_value(tree)) ||
contains(left_child(tree), value) ||
contains(right_child(tree), value)
)

The procedure contains_value checks the root, then searches the subtrees until it finds the value. It needs no ordering assumption on its input:

Membership specification
Expected: Verified
@uwlp
proc contains_value(tree: Tree, value: Int) -> (present: Bool)
post ?(present == contains(tree, value))
{
if is_nil(tree) {
present = false
} else {
var root: Int = root_value(tree)
if value == root {
present = true
} else {
var in_left: Bool = contains_value(left_child(tree), value)
if in_left {
present = true
} else {
present = contains_value(right_child(tree), value)
}
}
}
}

Each recursive call gives the membership result for its subtree. Combining those results with the comparison at the root proves the caller's postcondition.

Finding the Minimum and Maximum​

Both queries require a nonempty tree satisfying is_bst:

Search-tree ordering
// Both subtrees are ordered, with left values below and right values above the root.
func is_bst(tree: Tree): Bool =
ite(
is_nil(tree),
true,
is_bst(left_child(tree)) &&
is_bst(right_child(tree)) &&
(forall value: Int. contains(left_child(tree), value) ==> (value < root_value(tree))) &&
(forall value: Int. contains(right_child(tree), value) ==> (root_value(tree) < value))
)

The predicate requires both subtrees to be ordered, with all left values below the root and all right values above it.

Minimum​

The function min_value follows left children:

Minimum function
func min_value(tree: Tree): Int =
ite(is_nil(left_child(tree)), root_value(tree), min_value(left_child(tree)))

The procedure get_min finds this minimum:

Minimum specification
Expected: Verified
@uwlp
proc get_min(tree: Tree) -> (result: Int)
pre ?(is_bst(tree) && !is_nil(tree))
post ?(
(result == min_value(tree)) &&
contains(tree, result) &&
(forall value: Int.
(contains(tree, value) && (value != result)) ==> (result < value))
)
{
var left: Tree = left_child(tree)
var root: Int = root_value(tree)
if is_nil(left) {
result = root
} else {
result = get_min(left)
}
}

If the left child is empty, the root is the minimum. Otherwise, the recursive call gives the minimum of the nonempty left child. By is_bst, that value is also smaller than the root and every member of the right subtree.

Maximum​

The function max_value follows right children:

Maximum function
func max_value(tree: Tree): Int =
ite(is_nil(right_child(tree)), root_value(tree), max_value(right_child(tree)))

The procedure get_max verifies that this value is the largest member:

Maximum specification
Expected: Verified
@uwlp
proc get_max(tree: Tree) -> (result: Int)
pre ?(is_bst(tree) && !is_nil(tree))
post ?(
(result == max_value(tree)) &&
contains(tree, result) &&
(forall value: Int.
(contains(tree, value) && (value != result)) ==> (value < result))
)
{
var right: Tree = right_child(tree)
var root: Int = root_value(tree)
if is_nil(right) {
result = root
} else {
result = get_max(right)
}
}

The proof mirrors the minimum query, using the right child's specification and the ordering of the left subtree.

Inserting a Value​

The procedure insert_value adds the supplied value to a tree satisfying is_bst. Its two post clauses require the result to remain ordered and describe exactly which values it contains:

Insertion specification
Expected: Verified
@uwlp
proc insert_value(tree: Tree, value: Int) -> (result: Tree)
pre ?(is_bst(tree))
post ?(is_bst(result))
post ?(forall witness: Int.
contains(result, witness) == (contains(tree, witness) || (witness == value)))
{
if is_nil(tree) {
result = node(nil(), value, nil())
} else {
var left: Tree = left_child(tree)
var root: Int = root_value(tree)
var right: Tree = right_child(tree)

if value < root {
var new_left: Tree = insert_value(left, value)
result = node(new_left, root, right)
} else {
if root < value {
var new_right: Tree = insert_value(right, value)
result = node(left, root, new_right)
} else {
result = tree
}
}
}
}

The recursive call tells us which values are in the modified child and that they are ordered. The comparison with the root ensures that rebuilding the parent preserves is_bst. The result contains exactly the old members together with the inserted value.

The complete source also includes insert_example, which inserts 4, 2, 8, and 6, then uses these specifications to check membership, minimum 2, and maximum 8.

See Also​

References​