(Mathematical expressions are simplified in this html-dokument. They should be readable enough to get the flavour.)
A new data structure for the dictionary problem is presented. Updates are performed in Theta(log n) time in the worst case and the number of comparisons per operation is ceiling(log n + 1 + epsilon), where epsilon is an arbitrary positive constant.