Изменения

Операции поиска минимума и максимума дорогие, выполним их за О(1). Теперь становится понятно, что необязательно спускаться до минимума или максимума в дереве. Если у вершину нет левого сына (отметим одним битом) вместо ссылки на левого сына сделаем ссылку на минимум в правом поддереве, что удобно для нашей реализации succOrPred. Если нет правого сына, то храним ссылку на максимум в левом поддереве. [[File:TrieMinMin amp amp max.jpg|thumb|right|200px500px|Ссылка Ссылки на минимум]] [[File:Trie_max.jpg|thumb|right|200px|Ссылка на и максимум]]