====================================================================
BinarySearchTree examples
====================================================================

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.

  lv := [8,3,5,4,6,2,1,5,7]
   [8, 3, 5, 4, 6, 2, 1, 5, 7]
                      Type: List PositiveInteger

A convenient way to create a binary search tree is to apply the
operation binarySearchTree to a list of elements.

  t := binarySearchTree lv
   [[[1, 2, .], 3, [4, 5, [5, 6, 7]]], 8, .]
                      Type: BinarySearchTree PositiveInteger

Another approach is to first create an empty binary search tree of integers.

  emptybst := empty()$BSTREE(INT)
   [] 
                      Type: BinarySearchTree Integer

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.

  t1 := insert!(8,emptybst)
   8 
                      Type: BinarySearchTree Integer

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.

  insert!(3,t1)
   [3, 8, .]
                      Type: BinarySearchTree Integer

We go back to the original tree t.  The leaves of the binary search
tree are those which have empty left and right subtrees.

  leaves t
   [1, 4, 5, 7]
                      Type: List PositiveInteger

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.

  split(3,t)
   [less=[1, 2, .], greater=[[., 3, [4, 5, [5, 6, 7]]], 8, .]]
              Type: Record(less: BinarySearchTree PositiveInteger,greater: 
                           BinarySearchTree PositiveInteger)

Define insertRoot to insert new elements by creating a new node.

  insertRoot: (INT,BSTREE INT) -> BSTREE INT
                      Type: Void

The new node puts the inserted value between its "less" tree and
"greater" tree.


  insertRoot(x, t) ==
    a := split(x, t)
    node(a.less, x, a.greater)
                      Type: Void


Function buildFromRoot builds a binary search tree from a list
of elements ls and the empty tree emptybst.

  buildFromRoot ls == reduce(insertRoot,ls,emptybst)
                      Type: Void

Apply this to the reverse of the list lv.

  rt := buildFromRoot reverse lv
   [[[1, 2, . ], 3, [4, 5, [5, 6, 7]]], 8, .]
                      Type: BinarySearchTree Integer

Have FriCAS check that these are equal.

  (t = rt)@Boolean
   true
                      Type: Boolean

See Also:
o )show BinarySearchTree

