The amortized analysis of a non-blocking chromatic tree
Jeremy Ko · Theoretical Computer Science · 2020
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˙+logn) 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.