We saw earlier how we can represent collections of elements such that we can efficiently iterate through them and efficiently merge two such collections. In this chapter, we turn “bags” into “sets” by considering data structures that allow us to efficiently insert, delete, and check for membership of elements:
insert <- function(x, elm) UseMethod("insert")remove <- function(x, elm) UseMethod("remove")member <- function(x, elm) UseMethod("member")
We do this through so-called search trees—trees with the property that all elements in the left subtree of a node will have values ...
