Функция удаления в бинарном дереве поиска - PullRequest
Новая
       14

Функция удаления в бинарном дереве поиска

0 голосов
/ 27 июня 2011

Может кто-нибудь сказать мне, что делают следующие строки 

else if ( obj < retrieve() ) 
{
    return ( left() == 0 ) ? 0 : left()->erase( obj, left_tree );
} 
else 
{
    return ( right() == 0 ) ? 0 : right()->erase( obj, right_tree );
}

в блоке кода ниже: 

    template <typename Comp>
    int Binary_search_node<Comp>::erase( Comp const &obj, Binary_search_node<Comp> *&ptr_to_this) 
{
    if ( obj == retrieve() ) {
        if ( leaf() ) { // leaf node
            ptr_to_this= 0;
            delete this;
        } 
        else if ( left() != 0 && right() != 0 ) { // full node
            element= right()->front();
            right()->erase( retrieve(), right_tree );
        } 
        else { // only one child
            ptr_to_this= ( left() != 0 ) ? left() : right();
            delete this;
        }
        return 1;
    } 
    else if ( obj < retrieve() ) {
        return ( left() == 0 ) ? 0 : left()->erase( obj, left_tree );} 
    else {
        return ( right() == 0 ) ? 0 : right()->erase( obj, right_tree );}
}

Дополнительная информация:

1) 

front() -- finds the minimum objects

Реализация: 

template <typename Comp>
Comp Binary_search_node<Comp>::front() const 
{
    return( left() == 0 ) ?retrieve() :left()->front();
}

2) 

left()  -- returns pointer to left subtree

3) 

right() -- returns pointer to right subtree

4) 

*ptr_to_this points to current object (same location as what *this points to)

У меня есть представление о том, что делают строки, но я не уверен на 100%, поэтому я хотел подтвердить. Обратите внимание, что эта функция erase() предназначена для двоичного дерева поиска. Спасибо!

Ответы [ 3 ]

3 голосов
/ 27 июня 2011

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

  • Если удаляемое значение меньше текущего значения, попробуйте перейти влево.
  • Если значение для удаления больше текущего значения, то попытаться идти прямо.
  • Если узел, на который вы пытаетесь перейти, не существует, вернуть 0.
0 голосов
/ 27 июня 2011

erase представляется рекурсивным. На каждом этапе мы проверяем, равен ли удаляемый объект текущему объекту или нам нужно перейти в левый или правый дочерний элемент.

Если дочерний элемент, в который мы хотим войти, не существует (left() == 0 или right() == 0), то мы не можем стереть объект (потому что его нет в дереве), поэтому мы возвращаем 0. В противном случае мы возвращаемся в дочернюю функцию и возвращаем все, что она возвращает.

0 голосов
/ 27 июня 2011

Ваш код ищет двоичное дерево (и предполагает, что его элементы отсортированы) для поиска obj, и если он рекурсивно находит его, удаляет его и возвращает 1.Если он не найдет его, он вернет 0.

...