В красно-черных деревьях нисходящее удаление быстрее и больше пространства, эффективного, чем восходящее удаление?
Посмотрите здесь
Текущая реализация сохраняет массив целых объектов для всех целых чисел от -5 до 256, когда вы создаете int в этом диапазоне вы фактически просто возвращаете ссылку на существующий объект.
blockquote>
1 ответ
Из того, что я собираюсь: "нисходящее удаление" старается не пересекать тот же узел в пути несколько раз во время операции. Так, учитывая простой контур от корня до данного узла, если Вы собираетесь сделать некоторую вещь к узлу, это находится в том пути так или иначе, почему не только делают это на пути вниз? Это избегает необходимости пересечение по частям пути несколько раз. Поэтому это экономит время.
А подобный принцип используется для нескольких операций (включая вставку) в 2-3-4 деревьях (специальный подслучай a, B-деревьев)
, нисходящее удаление минимизирует количество изменяющих баланс операций?
Думают, что в среднем случае это делает. Поскольку Вы делаете потенциально легче вставить что-то позже с немногими операциями изменения баланса.
могло быть возможно, что нисходящее удаление заранее делает слишком много переокрасок и изменений баланса на пути вниз?
, Возможно, но это зависит от набора данных. Однако, как упомянуто выше. Это может сократить количество переокрасок и изменений баланса в целом.