RedBlackTree Mark Allen Weis Удалить (x) Верхний нижний подход

Из оригинальной реализации Марка Аллена Вейса RedBlackTree из Структуры данных и решение проблем Использование Java найдено здесь.

Кажется, я не могу понять, как удалить узел из дерева. Прочитав ресурс википедии, я заметил функцию "is_leaf()". , проблема с этой реализацией и реализацией Марка Вайса заключается в том, что невозможно определить, какой узел является листом, а какой нет.

void delete_one_child(struct node *n)
{
    /*
     * Precondition: n has at most one non-null child.
     */
    struct node *child = is_leaf(n->right) ? n->left : n->right;

    replace_node(n, child);
    if (n->color == BLACK) {
            if (child->color == RED)
                    child->color = BLACK;
            else
                    delete_case1(child);
    }
    free(n);
}

Java-реализация Is_Leaf

public boolean isLeaf(){
if(left == null && right == null){
return false;
}
return true;
}

Консольный вывод

value=1 color=1 leaf=true left=null right=14
value=2 color=1 leaf=true left=null right=5
value=5 color=0 leaf=true left=null right=null
value=7 color=0 leaf=true left=2 right=11
value=8 color=0 leaf=true left=null right=null
value=11 color=1 leaf=true left=8 right=null
value=14 color=1 leaf=true left=7 right=15
value=15 color=1 leaf=true left=null right=null

Формат дерева (из консоли)

└── (1) 1
    └── (1) 14
        ├── (0) 7
        │   ├── (1) 2
        │   │   └── (0) 5
        │   └── (1) 11
        │       └── (0) 8
        └── (1) 15

Правила:

  1. Корень черный
  2. У каждого красного узла есть черный родитель
  3. Любые дочерние элементы красного узла являются черными. У красного узла не может быть красных дочерних элементов.
  4. Каждый путь от корня к листу содержит одинаковое количество черных узлов.

Итак, мой вопрос: как мне реализовать удаление из этой реализации Red и Back Trees?


java red-black-tree
person Killrawr    schedule 30.05.2012    source источник

Ответы (3)


arrow_upward
0
arrow_downward

Вы спрашиваете, как реализовать isLeaf()? Если это так, вы должны передать isLeaf узел, который хотите проверить.

public boolean isLeaf(RedBlackNode<AnyType> t ){
if(t.left == null && t.right == null){
return false;
}
return true;
}

В противном случае сам алгоритм выглядит правильно, единственная реальная работа — это перевод C в Java, что несложно.

person matchdav    schedule 30.05.2012
comment
Также я заметил это в вашей вставке: if(current!= nullNode) throw new DuplicateItemException(item.toString()); текущий = новый RedBlackNode‹AnyType›( item, nullNode, nullNode ); Я думаю, вы, вероятно, захотите проверить, что current.element != nullNode.element, так как значение nullNode установлено, и я думаю, что это может быть причиной того, что вы, кажется, вставляете повторяющиеся элементы. - person matchdav; 30.05.2012

arrow_upward
1
arrow_downward

Я думаю, что это правильный код isLeaf():

public boolean isLeaf(RedBlackNode<AnyType> t ){
    if(t.left.element == null && t.right.element == null){
        return true;
    }
    return false;
}
person Justin    schedule 31.05.2012
comment
Нет. Критерием листа является то, что его левый и правый узлы указатели равны нулю, т. е. они не ссылаются на другие узлы под ними. Если значение left или right равно null, ваш код выдаст исключение, потому что он пытается получить доступ к свойствам нулевых элементов. - person matchdav; 01.06.2012
comment
@matthewdavidson Это выглядит неправильно, если посмотреть на код вставки (). В коде вставки при создании нового конечного узла используется следующая строка: current = new RedBlackNode‹AnyType›( item, nullNode, nullNode ); который создает новый узел с ненулевыми указателями для левого и правого. Вот почему вы должны проверять поля элементов этих указателей. - person Justin; 01.06.2012
comment
Я понимаю, о чем вы говорите, но лист — это не узел. Вот что я хочу сказать. «текущий» — это узел, а не лист. «лево» и «право» — это листья. Узел находится между головой и листьями, а его левый и правый указатели относятся либо к узлу, либо к листу, либо ни к чему. Лист находится на конце с указателями, ведущими в никуда. Посмотрите, как ведет себя код в приведенных выше тестах. Левый и правый указатели листьев всегда указывают на ноль, и их элементы НЕ являются нулевыми. - person matchdav; 05.06.2012
comment
@Justin, не могли бы вы взглянуть на мой метод удаления для RedBlackTree? stackoverflow.com/questions/28705454 / - person committedandroider; 25.02.2015

arrow_upward
0
arrow_downward

Вы должны проверить nullnode вместо null:

public boolean isLeaf() {
    if(left == nullnode && right == nullnode) {
        return false;
    }
    return true;
}
person Hari Menon    schedule 30.05.2012
comment
Я недавно изменил свой вопрос, не могли бы вы обновить свой вопрос соответствующим образом? спасибо! - person Killrawr; 30.05.2012
comment
Можете ли вы взглянуть на мой метод удаления красного черного дерева? Он похож на этот. stackoverflow.com/questions/28705454 / - person committedandroider; 25.02.2015