# RBST

##### The RBST reference class

The RBST reference class implements the data structure binary search tree (BST).

- Keywords
- RBST

##### Usage

`RBST`

##### Details

A BST is a particular type of container storing items or elements (nodes) by following a binary tree structure. The BST has one root on top, which is the first node of the tree, and each node in the BST has at most two sub-nodes (left sub-node and right sub-node) which can be the roots of their sub-trees.

The BST should be equipped with the "<" and "=" operators such that any two nodes in the tree can be compared. And therefore, the ">" is defined. The BST structure follows strictly the rules that, for a certain node in the tree, any nodes in its left sub-tree must be strictly smaller than it, any nodes in its right sub-tree must be strictly larger than it, and any two nodes in the tree must not be equal.

Therefore, the BST is a special set or dictionary equipped with "<", ">" operators.

When you create a new RBST instance, you have to input two functions which defines
the bodies of the two private methods `lessthan`

and `equal`

.
The RBST instance then will use them to make comparison and decide where to put new nodes (build the BST).

Each time a new node is inserted, the BST algorithm finds its location on the tree. Then you can imagine, the BST is efficient in maintaining (inserting and deleting), searching and traversing the tree. An average O(log n) time complexity can be achieved by applying the BST algorithm.

A very important fact is that, the RBST only compares the nodes by using
the function `equal`

.
So it will regard any two nodes identical if `equal`

returns `TRUE`

,
even though they are different.

We see that the BST can also be regarded as a dictionary,
as the key of the dictionary is actually the value input into `insert`

, `delete`

and `search_for`

.

The traversals of the BST (in-order, pre-order, and post-order) are implemented as well.
A `callback`

function can be input into the `traverse`

function
to specify how to treat the traversed nodes.
By default (if you do not input anything here) the `traverse`

function
prints the traversed nodes.
But of course you can, for example, store them by changing the `callback`

function,
see the examples below.

The elements in the BST are not necessarily to be of the same type, and they can even contain functions.

##### Format

An object of class `R6ClassGenerator`

of length 24.

##### Class Method

The class method belongs to the class.

`new(lessthan, equal, ..., collapse=NULL)`

The

`new`

method creates a new instance of the RBST class containing the values in`...`

and`collapse`

as its nodes.The argument

`lessthan`

takes a function defining the "<" operation, and the argument`equal`

takes a function defining the "=" operation. Both of the functions takes two values of the nodes in the tree and return a boolean.`lessthan`

can take, for example, the form`lessthan <- function(x, y) return(x$num < y$num)`

where

`x`

and`y`

are values of two nodes in the tree with the attribute`num`

.`equal`

can take, for example, the form`equal <- function(x, y) return(x$num == y$num)`

where

`x`

and`y`

are values of two nodes in the tree with the attribute`num`

.

##### Immutable Methods

The immutable methods do not change the nodes of the instance.

`traverse(mode="in", callback=function(item){print(item)}, ...)`

The

`traverse`

method takes at least two arguments which are`mode`

and`callback`

.The

`mode`

takes a value in one of the three strings`"in"`

,`"pre"`

, and`"post"`

which indicate*traverse-in-order*,*traverse-pre-order*, and*traverse-post-order*, respectively.The

`callback`

takes a function input specifying how to handle the value of each node in the tree. By default,`callback`

prints the nodes by using the`print`

function.The method also takes

`...`

as the additional arguments for the`callback`

function if any.`search_for(val)`

The method

`search_for`

uses the`equal`

function to compare`val`

with the nodes in BST. It returns the value of the node if the node is`equal`

to the given value, and`NULL`

otherwise.As the tree has been structured strictly by following the rules introduced above, there is no need to search the whole tree in most cases, and the maintaining and searching are efficient.

`min`

The active method

`min`

returns the smallest node in the tree, and`NULL`

if the tree is empty.`max`

The active method

`min`

returns the largest node in the tree, and`NULL`

if the tree is empty.

##### Mutable Methods

The mutable methods changes the nodes of the instance.

`insert(val)`

The method

`insert`

inserts a new node and returns`TRUE`

showing that the inserting is successful, but if there is one node in BST that is`equal`

to the node, the`insert`

will do nothing and return a`FALSE`

showing that the inserting fails.`delete(val)`

The method

`delete`

removes the node which is`equal`

to`val`

. If the node is found, then it will be removed and the function returns a`TRUE`

, and if the node is not found, then it will do nothing and returns a`FALSE`

,

##### References

For the details about the BST data structure, see BST at Wikipedia.

##### See Also

R6DS for the introduction of the reference class and some common methods

##### Examples

```
# NOT RUN {
### create a new instance
# you have to define two functions for "<" and "="
lessthan <- function(x, y) return(x$key < y$key)
equal <- function(x, y) return(x$key == y$key)
# remember that the nodes in the BST have the "key" variable
# and it is numeric
# to create a new instance of the class
bst <- RBST$new(lessthan=lessthan, equal=equal)
# of course you can start to push elements when creating the instance
# the previous BST instance will be removed by doing so
# and the memory allocated for that one will be cleared,
# as now bst has been pointed to another instance of the class.
bst <- RBST$new(lessthan=lessthan, equal=equal,
list(key=5, val="5"), collapse=list(list(key=3,val="3"), list(key=9,val="9")))
# the following sentence is equivalent to the above
bst <- RBST$new(lessthan=lessthan, equal=equal,
list(key=5, val="5"), list(key=3,val="3"), list(key=9,val="9"))
# where the three lists are inserted into the BST
### maintaining
bst$insert(list(key=5, val="6"))
# FALSE though their val are different
bst$insert(list(key=6, val="5"))
# TRUE
bst$delete(list(key=7, val="7"))
# FALSE
bst$delete(list(key=6, val="7"))
# TRUE and delete list(key=6, val="5")
# though val are different
### searching
bst$search_for(list(key=0, val="0"))
# NULL
bst$search_for(list(key=5, val="0"))
# the BST has a node whose key is 5
### min and max
# min and max are two active functions
# so the parenthesis is not needed
bst$min
bst$max
### traversing
# by default, the callback function prints the nodes
# but you can re-define the callback function
queue <- RQueue$new()
callback <- function(item)queue$enqueue(item)
# remember that RQueue is a reference class
# so the new callback will store the traversed nodes
bst$traverse(callback=callback)
tmp = queue$dequeue(); print(tmp)
while(!is.null(tmp)) {tmp = queue$dequeue(); print(tmp)}
bst$traverse(mode = "in", callback=callback)
tmp = queue$dequeue(); print(tmp)
while(!is.null(tmp)) {tmp = queue$dequeue(); print(tmp)}
# pre-order traversing
bst$traverse(mode = "pre", callback=callback)
tmp = queue$dequeue(); print(tmp)
while(!is.null(tmp)) {tmp = queue$dequeue(); print(tmp)}
# post-order traversing
bst$traverse(mode = "post", callback=callback)
tmp = queue$dequeue(); print(tmp)
while(!is.null(tmp)) {tmp = queue$dequeue(); print(tmp)}
# }
```

*Documentation reproduced from package R6DS, version 1.1.0, License: GPL-3*