Как кэш LRU будет работать для структуры данных trie?

Говоря о кеше, следует помнить, что это избыточная структура данных, единственной целью которой является ускорение выборки данных.
Таким образом, когда фрагмент данных удаляется из кеша, это не имеет никаких последствий. (кроме скорости выполнения) в программе, которая использует эти данные, потому что тогда они будут извлечены из основной памяти. Так что в любом случае ваш trie будет вести себя точно так же, вне зависимости от того, какой его кусок находится в кеше или нет.

Это очень важно, потому что позволяет нам кодировать на языках высокого уровня, таких как java, не заботясь о политике замены кеша, реализуемой процессором. Если бы это было не так, это был бы кошмар, потому что пришлось бы учитывать всю существующую (и будущую?) политику замены, реализованную в процессорах. Не говоря уже о том, что эти политики не так просты, как LRU (существуют наборы кэшей, которые делят кэш на «строки», и их поведение в значительной степени также связано с их физической структурой), и что место, где часть данных будет находится в кэше, зависит от его адреса в основной памяти, который не обязательно будет одинаковым для каждого выполнения кода.

Короче говоря, две упомянутые вами вещи (узлы trie в java и политики кэширования LRU) слишком далеки друг от друга (одна — программирование очень, очень низкого уровня, другая — высокого уровня). Вот почему мы редко, если вообще когда-либо, рассматриваем их взаимодействие.
Если вы реализуете Trie в Java, ваша задача состоит в том, чтобы убедиться, что он хорошо работает во всех ситуациях, что он хорошо спроектирован, чтобы обслуживание было проще (возможно, ), что он удобочитаем, чтобы другие программисты могли когда-нибудь над ним поработать. В конце концов, если он по-прежнему работает слишком медленно, вы можете попытаться оптимизировать его (после определения узких мест, но никогда раньше).
Но если вы хотите связать свою попытку с совпадением кэша и политиками замены, придется прочитать перевод вашей реализации в байт-код (сделанный JVM).

PS: в своем посте вы говорите об имитации превышения памяти. Для программы такого нет. Когда кеш заполнен, мы заполняем основную память. Когда основная память заполнена, операционные системы обычно резервируют часть жесткого диска для выполнения роли основной памяти (мы называем это подкачкой, и когда это происходит, компьютер практически зависает). Когда своп заполнен, программы вылетают. Все.
В «разуме» программы операционная система выделяет ей совершенно гигантские объемы памяти (виртуальной, но для программы все равно, что реальной), которые никогда не заполнятся. Сама программа не «осознает» способ управления памятью и объем оставшейся памяти по многим веским причинам (безопасность, гарантия того, что все программы будут иметь справедливую долю ресурсов...)