The Amortized Analysis of a Non-blocking Chromatic Tree

Jeremy Ko

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 imple…