В красно-черных деревьях удаление сверху вниз быстрее и эффективнее, чем удаление снизу вверх?

Question

На эту страницу http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx «Удаление сверху вниз» представляет собой реализацию удаления узла из красно-черного дерева, который проактивно уравновешивает дерево, проталкивая красный узел вниз по дереву, так что удаляемый листовой узел гарантированно будет красным. Поскольку листовой узел гарантированно будет красным, вам не нужно беспокоиться о перебалансировке дерева, потому что удаление красного листового узла не нарушает никаких правил, и вам не нужно выполнять никаких дополнительных операций для восстановления баланса. сбалансировать и восстановить красно-черное.

«Удаление снизу вверх» включает в себя выполнение обычного двоичного поиска по дереву для поиска удаляемого узла, перестановку в листовом узле (если найденный узел не является листовым узлом), а затем восстановление красного свойства черного дерева, взбираясь на дерево и исправляя нарушения красно-черных правил.

Минимизирует ли удаление сверху вниз количество операций перебалансировки? Возможно ли, что удаление сверху вниз проактивно делает слишком много перекрашиваний и перебалансировок на пути вниз?

Как насчет этого сценария: (x) обозначает красный узел

               8
         _____/ \____
        /            \
       4              12
     /   \          /    \
   2       6      10      14
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

Если я захочу удалить 16, удаление снизу вверх не произведет никакой перебалансировки, но удаление сверху вниз перекрасит узлы до конца, прежде чем обнаружит, что операции перекраски не нужны:

итерация 1:

              (8)
         _____/ \____
        /            \
       4              12
     /   \          /    \
   2       6      10      14
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

итерация 2:

               8
         _____/ \____
        /            \
      (4)            (12)
     /   \          /    \
   2       6      10      14
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

итерация 3:

               8
         _____/ \____
        /            \
      (4)             12
     /   \          /    \
   2       6     (10)    (14)
  / \     / \    /  \    /  \
 1   3   5   7   9  11  13  15
                             \
                            (16)

Затем в итерации 4 вы обнаружите, что вам не нужно нажимать вниз, потому что 16 уже красный. Таким образом, удаление сверху вниз более эффективно по времени и пространству?

Answer 1

Из того, что я понял: «удаление сверху вниз» позволяет избежать пересечения одного и того же узла в пути более одного раза во время операции. Итак, учитывая простой путь от корня к данному узлу, если вы все равно собираетесь что-то делать с узлом, который находится на этом пути, почему бы просто не сделать это по пути вниз? Это позволяет избежать необходимости пересекать участки пути более одного раза. Следовательно, это экономит время.

Аналогичный принцип применяется для нескольких операций (включая вставку) в 2-3-4 деревьях (особый случай a, b-деревьев)

Минимизирует ли удаление сверху вниз количество операций перебалансировки?

Думаю, что в среднем случае это так. Потому что вы потенциально облегчаете вставку чего-либо после нескольких операций перебалансировки.

Возможно ли, что удаление сверху вниз проактивно делает слишком много перекрашиваний и перебалансировок на пути вниз?

Может быть, но это зависит от набора данных. Однако, как уже упоминалось выше. Это может уменьшить количество перекрасок и повторных балансировок в целом.

Answer 2

Эффективнее ли сверху вниз пробел эффективнее, чем снизу вверх?

Одним словом, да. Нисходящий алгоритм, представленный в вечно сбитом с толку , не нуждается в родительских указателях на узлах. Восходящие алгоритмы представлены с компромиссом между временем и пространством: родительские указатели допускают некоторое короткое замыкание при повторной балансировке после вставки и удаления.

Например, Реализация OpenJdk-7 Красно-черных деревьев имеет родительские указатели, что позволяет ему выбирать, требуется ли повторный баланс после удаления (например, в вашем сценарии).

Эффективнее ли время сверху вниз время , чем снизу вверх?

В общем, да: подход сверху вниз должен проходить только один раз за операцию, а подход снизу должен проходить дерево дважды за операцию. Как я упоминал ранее, подходы снизу вверх могут сбрить время с помощью указателей родителя. Но определенно не каждый раз обход дерева.

Обе реализации могут также выбрать использование threading для улучшения времени или пространства, необходимого для итерации по всему дереву. Это требует накладных расходов одного или двух флагов на узел. Это также может быть достигнуто с помощью родительских указателей, но не так эффективно. NB: ссылка на потоки говорит, что потоки не так эффективны, как родительские указатели, но это относится только к деревьям снизу вверх (которые рассматриваются в книге).

Неофициальные данные

Вернувшись в колледж, мы внедрили красно-черное дерево с вечным смещением в C ++ и провели сравнение с нашей STL (снизу вверх) реализацией std :: map. Наш нисходящий подход был определенно быстрее & mdash; я хочу сказать, что он был легко в 2 раза быстрее для всех операций мутирования. Поиск также был быстрее, но я не могу сказать, было ли это из-за более сбалансированного дерева или менее сложного кода.

К сожалению, у меня больше нет ни кода, ни записи.