Прежде всего, я предполагаю, что упустил что-то серьезное, когда думал об этом, но я все еще хотел опубликовать об этом, чтобы посмотреть, действительно ли я ничего не пропустил, в связи с этим ...
У меня довольно тяжелое двоичное дерево записи (около 50/50 между записью и чтением), и сегодня по дороге домой я думал о способах оптимизации этого, особенно об ускорении записи - это то, что я придумал .
Учитывая, что операция add (T, x) для добавления x в дерево T сначала состоит из find (T, x), чтобы увидеть, существует ли x, и в этом случае она не возвращает родителя, поэтому мы можем добавить это вместо одного из родителей пустые листья.
Что если мы добавим хеш-таблицу в качестве промежуточного кеша к операции добавления, поэтому, когда мы вызываем add (T, x), в действительности происходит то, что x хешируется и вставляется в хэш-карту M. И это все. Оптимизация происходит, когда мы где-то еще просим найти (T, x), теперь, когда мы ищем дерево, мы придем к листовому узлу, так как x еще не вставил дерево (оно существует только в хэш-карте M) , мы хэшируем x и сравниваем его с ключами в M, чтобы увидеть, должно ли оно быть в дереве. Если он найден в M, мы добавляем его в дерево и удаляем из M.
Это исключило бы операцию поиска (T, x) для add (T, x) и уменьшило бы ее до сложения (M, x), которое равно O (1). И затем (ab) - используйте операцию поиска (T, x), которая выполняется, когда мы ищем узел в первый раз, чтобы вставить его.