A binary trie is a sequential data structure that maintains a dynamic set from the universe$\{0,\ \ldots,\ u-1\}$, supporting Search with$O(1)$worst-case step complexity, and Insert, Delete, and Predecessor with$O(\log u)$worst-case step complexity. We give a wait-free implementation of a relaxed binary trie, using read, write, CAS, and AND operations. It supports all oper-ations with the same worst-case step complexity as the sequential binary trie. However, predecessor operations may not return a key when there are concurrent update operations. We use this as a component of a lock-free, linearizable implementation of a binary trie. It supports Search with$O(1)$worst-case step complexity and Insert, Deleteand Predecessorwith$O(c^{2}+\log\ u)$amortized step complexity, where$c$is a measure of the contention. A lock-free binary trie is challenging to implement as compared to many other lock-free data structures because Insertand Deleteoperations perform a non-constant number of modifications to the binary trie in the worst-case to ensure the correctness of Predecessoroperations.

A non-blocking chromatic tree is a type of balanced binary search tree where multiple processes can concurrently perform search and update operations. We prove that a certain implementation has amortized cost O(c˙+log⁡n) for each operation, where c˙ is the maximum number of concurrent operations during the execution and n is the maximum number of keys in the tree during the operation. This amortized analysis presents new challenges compared to existing analyses of other non-blocking data structures.