41.2.2 Accessors and mutators for 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: binary-node-parent bnode

Function: $binary-node-parent bnode

Accessor for the parent node of bnode. Return #f or an instance of <binary-node>.

Function: binary-node-left bnode

Function: $binary-node-left bnode

Accessor for the left subtree of bnode. Return #f or an instance of <binary-node>.

Function: binary-node-left-set! bnode left

Function: $binary-node-left-set! bnode left

Mutator for the left subtree of a <binary-node> instance. The argument left must be #f or an instance of <binary-node> representing the root of the left subtree. When left is a node: it is mutated to reference bnode as parent.

Function: binary-node-right bnode

Function: $binary-node-right bnode

Accessor for the right subtree of bnode. Return #f or an instance of <binary-node>.

Function: binary-node-right-set! bnode right

Function: $binary-node-right-set! bnode right

Mutator for the right subtree of a <binary-node> instance. The argument right must be #f or an instance of <binary-node> representing the root of the right subtree. When right is a node: it is mutated to reference bnode as parent.

Function: binary-node-replace-in-parent! old-child new-child

Function: $binary-node-replace-in-parent! old-child new-child

Replace one child node with another child node.

The argument old-child must be an instance of <binary-node>; the argument new-child must be #f or an instance of <binary-node>.

Let’s name dad the parent of old-child, dad can be #f or an instance of <binary-node>; this function performs the following operations:

• If dad is a node and old-child is the left child of dad: set new-child as left child of dad.
• If dad is a node and old-child is the right child of dad: set new-child as right child of dad.
• The parent of old-child is set to #f.
• If new-child is a node: the parent of new-child is set to dad.

As example, let’s consider this simple tree:

2--3  0
|
1

applying this function to old-child having key ‘1’ and new-child having key ‘0’, results in the following tree:

2--3  1
|
0