Небольшой трюк для алгособеседований (не нужно так делать в любях других ситуациях)
Ситуация - на кодинг-собеседовании задали задачу, которую Вы умеете сводить к сбалансированным деревьям, но не к стандартным контейнерам (классический вариант - мультимножество с удалением, добавлением и ответом на запрос "сколько элементов лежит в заданном интервале"), но писать сбалансированное дерево без гуглежа, ошибок и за разумное время Вы не умеете (ничего страшного, я тоже не умею).
Возможное решение: выделить нужную Вам функциональность сбалансированного дерева в отдельный интерфейс, написать код, использующий этот интерфейс, после чего на словах сказать примерно следующее: "Данная функциональность оптимально реализуется сбалансированным деревом, я знаю о существовании AVL-tree и RB-tree (в идеале - еще и помнить, какие инварианты поддерживаются при каждой из реализаций), но прямо сейчас восстановить в памяти разбор всех частных случаев я не смогу, поэтому давайте сейчас реализую более упрощённый вариант с худшей асимптотической сложностью - в среднем O(sqrt(n)) вместо O(log(n))" - прокатывает примерно везде.
Идея реализации проста и красива как кувалда: мы используем обычное двоичное дерево поиска, зафиксировав высоту, при которой дерево нужно полность отбалансировать, числом, эквивалентным корню из максимально возможного числа элементов в дереве. (предполагается, что эту оценку мы знаем заранее и максимальное число элементов достаточно большое). Понятно, что при операциях поиска и удаления высота не изменится, так что эти операции стоят в худшем случае O(sqrt(n)). На операции вставки мы легко получаем высоту до добавленного элемента и, если она превысила порог (понятно, что на 1), перебалансируем всё дерево оптимальным образом. Полная перебалансировка дерева стоит O(n), после неё высота дерева будет равна двоичному логарифму n => до следующей перебалансировки случится не менее O(sqrt(n)) вставок - следовательно, каждая операция вставки в среднем O(sqrt(n)) - один раз за вставку и один раз за последующую перебалансировку.
Чуть более сложный случай - когда оценка на максимум элементов в дереве заранее неизвестна - по умолчанию считаем её, например, 1024, при достижении максимума элементов удваиваем оценку и пересчитываем максимально допустимую высоту. При этом, если число элементов в дереве упало ниже max/4, и при этом max не минимально возможный - можно уполовинить max, пересчитать максимальную высоту дерева и выполнить перебалансировку. Перед такой перебалансировкой должно пройти O(n) удалений, таким образом, к средней сложности добавится O(1)
Реализацию и несколько легко сдаваемых с её помощью задач с литкода можно посмотреть тут