  This paper presents the first implementation of a search tree data structure
in an asynchronous shared-memory system that provides a wait-free algorithm for
executing range queries on the tree, in addition to non-blocking algorithms for
Insert, Delete and Find, using single-word Compare-and-Swap (CAS). The
implementation is linearizable and tolerates any number of crash failures.
Insert and Delete operations that operate on different parts of the tree run
fully in parallel (without any interference with one another). We employ a
lightweight helping mechanism, where each Insert, Delete and Find operation
helps only update operations that affect the local neighbourhood of the leaf it
arrives at. Similarly, a Scan helps only those updates taking place on nodes of
the part of the tree it traverses, and therefore Scans operating on different
parts of the tree do not interfere with one another. Our implementation works
in a dynamic system where the number of processes may change over time.
  The implementation builds upon the non-blocking binary search tree
implementation presented by Ellen et al. (in PODC 2010) by applying a simple
mechanism to make the tree persistent.
