BinarySearchTree(R) is the domain of binary trees with elements of type R, ordered across the nodes of the tree. A non-empty binary search tree has a value of type R, and right and left binary search subtrees. If a subtree is empty, it is displayed as a period (``.'').
Define a list of values to be placed across the tree. The resulting tree has 8 at the root; all other elements are in the left subtree.
A convenient way to create a binary search tree is to apply the operation binarySearchTree to a list of elements.
Another approach is to first create an empty binary search tree of integers.
Insert the value 8. This establishes 8 as the root of the binary search tree. Values inserted later that are less than 8 get stored in the left subtree, others in the right subtree.
Insert the value 3. This number becomes the root of the left subtree of t1. For optimal retrieval, it is thus important to insert the middle elements first.
We go back to the original tree t. The leaves of the binary search tree are those which have empty left and right subtrees.
The operation split(k,t) returns a record containing the two subtrees: one with all elements ``less'' than k, another with elements ``greater'' than k.
Define insertRoot to insert new elements by creating a new node.
The new node puts the inserted value between its ``less'' tree and ``greater'' tree.
Function buildFromRoot builds a binary search tree from a list of elements ls and the empty tree emptybst.
Apply this to the reverse of the list lv.
Have Axiom check that these are equal.