Crit-bit trees [0]. Also known as TRIES, with an interesting use described in "TRASH - A dynamic LC-trie and hash data structure", which combines a trie with a hash function [1].

Also ROPE, a string allowing for prepends, substrings, middle insertions and appends [2]

[0] http://cr.yp.to/critbit.html

[1] https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.96....

[2] https://en.wikipedia.org/wiki/Rope_%28data_structure%29