функция Erase в бинарное дерево поиска

Question

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

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() предназначена для двоичного дерева поиска. Благодаря!

Answer 1

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

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

Answer 2

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

Answer 3

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

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