Двоичное дерево поиска Удалить

Question

Я работаю над деревом двоичного поиска на C++ в настоящий момент, и я достиг стадии, когда мне нужно написать функцию remove/delete (используя рекурсивный подход, x = change(x)). У меня есть два варианта:

• остановить у родителя узла узла, подлежащего удалению;

• , чтобы добраться до узла, чтобы удалить, а затем вызвать функцию, которая будет
  вернуть родительский

Подход 1: дешевле, больше кода

подход 2: меньше кода , более дорогой

Какой подход лучше в соответствии с вами и почему?

Answer 1

Лучшим подходом было бы перейти к родительскому узлу удаляемого узла и затем удалить этот дочерний узел. В конце концов, используя этот подход, вы всегда посещаете дочерний узел, так как вам всегда нужно подтвердить, что дочерний узел - это узел, который вы хотите удалить.

Answer 2

Я считаю, что наиболее эффективной формой для записи функций для древовидных структур в целом является следующий формат псевдокода.

function someActionOnTree() { 
     return someActionOnTree(root) 
    } 

    function someActionOnTree (Node current) { 
     if (current is null) { 
       return null 
     } 
     if (current is not the node I seek) { 
       //logic for picking the next node to move to 
       next node = ... 

       next node = someActionOnTree(next node) 
     } 
     else { 
       // do whatever you need to do with current 
       // i.e. give it a child, delete its memory, etc 
       current = ... 
     } 
     return current; 
    } 

Эта рекурсивная функция рекурсивно пересекает множество вершин структуры данных. Для каждой итерации алгоритма он либо ищет узел для рекурсии функции, либо перезаписывает ссылку структуры данных на этот узел со значением итерации алгоритма на этом узле. В противном случае он перезаписывает значение узла (и, возможно, выполняет другой набор логик). Наконец, функция возвращает ссылку на узел параметра, который необходим для этапа перезаписи.

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

Вот приложение этого стиля для функции удаления двоичного дерева поиска, чтобы украсить мою точку.

function deleteNodeFromTreeWithValue(value) { 
    return deleteNodeFromTree(root, value) 
} 

function deleteNodeFromTree(Node current, value) { 
    if (current is null) return null 
    if (current does not represent value) { 
      if (current is greater than my value) { 
       leftNode = deleteNodeFromTree(leftNode, value) 
      } else { 
       rightNode = deleteNodeFromTree(rightNode, value) 
      } 
     } 
     else { 
      free current's memory 
      current = null 
     } 
     return current 
} 

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

Answer 3

Я не согласен с тем, что это ваши два варианта.

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

// pseudo code. 
deleteNode(Node* node, int value) 
{ 
    if (node == NULL) return node; 

    if (node->value == value) 
    { 
     // This is the node I want to delete. 
     // So delete it and return the value of the node I want to replace it with. 
     // Which may involve some shifting of things around. 
     return doDelete(node); 
    } 
    else if (value < node->value) 
    { 
     // Not node. But try deleting the node on the left. 
     // whatever happens a value will be returned that 
     // is assigned to left and the tree will be correct. 
     node->left = deleteNode(node->left, value); 
    } 
    else 
    { 
     // Not node. But try deleting the node on the right. 
     // whatever happens a value will be returned that 
     // is assigned to right and the tree will be correct. 
     node->right = deleteNode(node->right, value); 
    } 
    // since this node is not being deleted return it. 
    // so it can be assigned back into the correct place. 
    return node; 
}