Сам алгоритм довольно прост - в основном вы вставляете все элементы в дерево, а затем пересекаете дерево, чтобы прочитать элементы по порядку.
Для повышения производительности для почти уже отсортированных последовательностей используются следующие модификации:
- Дерево должно быть (a, b) деревом с
b>2a-1, которое имеет O(1) время перебалансировки амортизированной вставки.
- Дерево содержит ссылки на одноуровневые узлы на одном уровне (по всему дереву)
Чтобы использовать время вставки O(1), вам просто нужно быстро найти место, к которому принадлежит следующий элемент, при условии, что последовательность почти отсортирована (поэтому она не будет далеко от того места, где вставлен предыдущий элемент). Это делается примерно следующим образом:
- вы начинаете с предыдущего вставленного элемента
- вы проверяете, не принадлежит ли следующий элемент этому узлу или какому-либо поддереву этого узла; если нет, вы смотрите на братьев и сестер (скажем, новый элемент меньше, так что это будет левый брат)
- если значения родного брата все еще слишком велики, вы поднимаетесь на один уровень и повторяете
- если новый элемент принадлежит поддереву брата, вы выполняете обычный поиск вниз оттуда
- если новый элемент принадлежит между родным братом и этим узлом, вы переходите к самому левому дочернему элементу и повторяете поиск вниз, пока не найдете подходящее поддерево
Таким образом, вы можете пройти a^k элементов дерева за k шагов, поэтому вам потребуется O(log(distance(current, previous)) времени, чтобы найти подходящее место для нового элемента. С учетом амортизированной O(1) перебалансировки вы получаете лучшее время, чем O(n log n), для почти отсортированных последовательностей, сохраняя при этом O(n log n) наихудший случай.