Удаление целого поддерева красно-черного дерева сохранит его свойства? - PullRequest
Новая
       71

Удаление целого поддерева красно-черного дерева сохранит его свойства?

6 голосов
/ 14 апреля 2011

В настоящее время я реализую красно-черную структуру данных для выполнения некоторых оптимизаций для приложения.

В моем приложении в данный момент мне нужно удалить все элементы, которые меньше или равны данномуЗначение (вы можете предположить, что элементы являются целыми числами) из дерева.

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

Ответы [ 3 ]

8 голосов
/ 14 апреля 2011

Когда вы удаляете один элемент из красно-черного дерева, это занимает O (log n) времени, где n - количество элементов в данный момент в дереве.

Если вы удаляете только несколько элементов, то лучше просто удалить их один за другим, заканчивая O (k log n) операциями (k = удаленные элементы, n = элементы в дереве перед удалением).

Но если вы знаете, что собираетесь удалить большое количество узлов (например, 50% или более дерева), то лучше перебрать элементы, которые вы хотите сохранить (O (k '), операция, где k '= элементы, которые будут сохранены), затем очистите дерево (O (1) или O (n) в зависимости от вашей схемы управления памятью) и восстановите операцию дерева (O (k' log k ')). Общая сложность O (k ') + O (k' log k ') = O (k' log k '), что, очевидно, меньше, чем O (k log n), когда k'

Ну, в любом случае, суть в том, что когда вы собираетесь удалить MOST элементов, на практике лучше перечислить те, которые вы хотите сохранить, а затем перестроить дерево.

6 голосов
/ 14 апреля 2011

РЕДАКТИРОВАТЬ: ниже для общего удаления поддерева. Вам нужна только одна Split операция (в зависимости от фактического содержания вопроса).

Можно удалить целое поддерево красно-черного дерева в худшем случае O(log n) время.

Известно, что операции Split и Join на красно-черном дереве могут быть выполнены за O(log n) время.

Разделить : учитывая значение k и красно-черное дерево T, разделить T на два красно-черных дерева T1 и T2, чтобы все значения в T1 = k .

Присоединиться : объединить два красно-чёрных дерева T1 и T2 в одно красно-чёрное дерево T. T1 и T2 удовлетворяют max в T1 <= min в T2 (или T1 <= T2 вкратце) . </p>

Вам нужно два Splits и один Join.

В вашем случае удаляемое поддерево будет соответствовать диапазону значений L <= v <= U.

Итак, вы сначала Split на L, чтобы получить T1 и T2 с T1 <= T2. <code>Split T2 на U, чтобы получить T3 и T4 с T3 <= T4. Теперь <code>Join деревья T1 и T4.

В псевдокоде ваш код будет выглядеть примерно так: 

Tree DeleteSubTree( Tree tree, Tree subTree) {

    Key L = subTree.Min();
    Key U = subTree.Max();

    Pair <Tree> splitOnL = tree.Split(L);
    Pair <Tree> splitOnU = splitOnL.Right.Split(U);

    Tree newTree = splitOnL.Left.Join(splitOnU.Right);

    return newTree;
}

См. Это для получения дополнительной информации: https://cstheory.stackexchange.com/questions/1045/subrange-of-a-red-and-black-tree

2 голосов
/ 14 апреля 2011

Массовое удаление из красно-черного дерева затруднено, потому что инвариант высоты черного цвета испорчен довольно сильно. Предполагая, что вы не выполняете (мягкое) в реальном времени, я бы либо удалил один за другим (так как вам пришлось вставлять их один за другим, мы говорим здесь о меньшем постоянном множителе), либо переключился на дерево отображения .

...