We improve upon an existing non-blocking implementation of a binary search tree from single-word compare-and-swap instructions. We show that the worst-case amortized step complexity of performing a Find, Insert or Delete operation op on the tree is O(h(op)+c(op)) where h(op) is the height of the tree at the beginning of op and c(op) is the maximum number of operations accessing the tree at any one time during op. This is the first bound on the complexity of a non-blocking implementation of a search tree.

We present what we believe is the most efficient and quickest four-key text entry method available. H4-Writer uses Huffman coding to assign minimized key sequences to letters, with full access to error correction, punctuation, digits, modes, etc. The key sequences are learned quickly, and support eyes-free entry. With KSPC = 2.321, the effort to enter text is comparable to multitap on a mobile phone keypad; yet multitap requires nine keys. In a longitudinal study with six participants, an average text entry speed of 20.4 wpm was observed in the 10th session. Error rates were under 1%. To improve external validity, an extended session was included that required input of punctuation and other symbols. Entry speed dropped only by about 3 wpm, suggesting participants quickly leveraged their acquired skill with H4-Writer to access advanced features.