{'fraction_non_alphanumeric': 0.05240174672489083, 'fraction_numerical': 0.00727802037845706, 'mean_word_length': 4.0588235294117645, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
A Simple Balanced Search Tree with O(1) Worst-Case Update Time

In this paper we show how a slight modification of (a, b)-trees allows us to perform member and neighbor queries in O(log n) time and updates in O(1) worst-case time (once the position of the inserted or deleted key is known). Our data structure is quite natural and much simpler than previous worst-case optimal solutions. It is based on two techniques: 1) bucketing, i.e. storing an ordered list of 2log n keys in each leaf of an (a, b) tree, and 2) lazy splitting, i.e. postponing necessary splits of big nodes until we have time to handle them. It can also be used as a finger tree with O(log*n) worst-case update time.