In tarakc02/rbst: Persistent binary search trees in R

Background

rbst is a purely functional implementation of a balanced search tree. In addition to the normal advantages of a balanced search tree (guaranteed fast retrieval, deletion, and insertion of new key-value pairs, ordered search operations), rbst also has the (natural in R) quality of non-destructive updates.

library(rbst)
example <- bst(keys = letters, values = seq_along(letters))
example

# retrieval:
example["t"]

# ordered search for keys:
keys_between(example, "f", "i")

# non-destructive insertions:
modified_example <- insert(example, "new key", 97)
contains(modified_example, "new key")
contains(example, "new key")

delete functions also allow for priority queue-like behavior:

example <- delete_min(example)
contains(example, "a")
example <- delete_min(example)
contains(example, "a")
contains(example, "b")

---

References

Okasaki, Chris. Purely Functional Data Structures. Cambridge University Press, 1999.

O'Neil, Shawn T. "Implementing Persistent O(1) Stacks and Queues in R." The R Journal Volume 7/1 (June 2015).

Oster, Julien. "An Agda implementation of deletion in Left-leaning Red-Black trees." http://www.reinference.net/llrb-delete-julien-oster.pdf

Sedgewick, Robert and Kevin Wayne. Algorithms, 4th Edition. Addison Wesley Professional, 2011.

tarakc02/rbst documentation built on May 31, 2019, 3:55 a.m.