41.3.2 Operations on unbalanced binary nodes

The following syntactic bindings are exported by the library (vicare containers binary-search-trees). The bindings whose name is prefixed with $ are unsafe operations: they do not validate their arguments before accessing them.

Function: unbalanced-tree-insert! root key< unode

Function: $unbalanced-tree-insert! root key< unode

Insert a new node into an unbalanced binary tree.

The argument root must be #f or an instance of <unbalanced-binary-node> representing the root of the tree.

The argument key< must be a procedure accepting two arguments of type <binary-node> and returning: true if the first argument has sort key less than the second argument; #f otherwise. Example for the trees of fixnums defined in the introduction (see bst intro):

(define (key< one two)
  (fx<? (<fixnum-node>-sort-key one)
        (<fixnum-node>-sort-key two)))

The argument unode must be an instance of <unbalanced-binary-node> representing the new node to insert. This node is meant to have left and right fields set to #f.

The return value is the root node after the insertion operation. If the argument root is #f: the return value is unode. If the argument root is a node: the return value is root itself.

Function: unbalanced-tree-remove! unode root

Function: $unbalanced-tree-remove! unode root

Remove a node from an unbalanced binary tree. unode must be the instance of <unbalanced-binary-node> to remove. root must be an instance of <unbalanced-binary-node> representing the root of the binary tree; it can be that unode equals root.

Return an instance of <unbalanced-binary-node> representing the new tree root after unode removal. If, after the removal, the tree is left empty: the return value is #f.