9.5 BinarySearchTree

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)

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}