Функция для удаления узла с заданным значением из двоичного дерева поиска

Question

У меня есть структура, называемая TreeNode с ключом int, а слева и с родителем. Я пытаюсь удалить узел из дерева с помощью функции DeleteNode, и он не работает. Я должен заменить удаленный узел в моей функции DeleteNode с максимальным значением из левого поддерева. Мои функции трансплантации и макс - вспомогательные функции для DeleteNode. Моя проблема в том, что я не уверен, где в моей функции DeleteNode я должен сравнивать значение узла, на котором я нахожусь, значение, которое я передаю через функцию. У меня есть комментарий в моем коде со звездочками, где я смущен, что делать. Любая помощь будет принята с благодарностью!

void transplant(TreeNode* u, TreeNode* v) //swaps u with v 
{ 

if (u->parent == NULL) //if u was root, make v new root 
    u->parent = v; 
else if (u == u->parent->left) //if u is smaller than it's parent 
    u->parent->left = v;  //set v to the left child of parent of u. Swap them at left, really 
else 
    u->parent->right = v;  //otherwise swap them at right 

if (v != NULL)    //reassign parents to double link 
    v->parent = u->parent; 
} 

TreeNode* maximum(TreeNode* n) 
{ 

while (n->left != NULL) 
    n = n->left; 
return n; 
} 

    void deleteNode(TreeNode *node, int key) 
{ 

if (node->left == NULL)     //if there is no left child 
    transplant(node, node->right);  //swap 
else if (node->right == NULL)   //if there is no right child 
    transplant(node, node->left);  //swap 
else 
{ 
    if(node->key == key){ //****This if comparison must be wrong*** 
    TreeNode* temp = maximum(node->right); //make temp the max on right 
    if (temp->parent != node)    //if it is more than one chain down 
    { 
     transplant(temp, temp->right);   //swap temp and it's right branch 
     temp->right = node->right;   //set right branch to nodes right 
     temp->parent->right = temp;    //set temp to the right child 
    } 
    transplant(node, temp);     // transplant 
    temp->left = node->left;    //get nodes left branch 
    temp->left->parent = temp;    //replace 
    } 
} 
} 

Answer 1

Во-первых, у вас есть три случая обращаться: (. Прямо из википедии был большой для меня, когда я взял структуры данных)

Существуют три возможных случая:

Удаление узла без детей (лист): просто удалите узел из дерева.

Удаление узла одним дочерним: удалите узел и замените его своим потомком.

Удаление узла двумя детьми: вызовите удаляемый узел N. Не удаляйте N. Вместо этого выберите либо его узел преемника в порядке, либо его узел-предшественник в порядке, R. Скопируйте значение R в N, а затем рекурсивно вызывать delete на R до достижения одного из первых двух случаев.

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

Возможно, вы пытаетесь реализовать вариант преемника in-order из-за максимума (node-> right).

Теперь, когда мы установили ваши возможные случаи, единственным случаем, который действительно требует пересадки, является третий случай с двумя детьми, на мой взгляд.

case 1: просто вызвать delete на листовом узле.

случай 2:

Здесь дель является узел должен быть удален (дель имеет один правильный ребенок в данном случае). Я просто написал это быстро. Первый оператор if проверяет, является ли del левым дочерним элементом его родительского узла, затем «удаляет» себя из уравнения указателя, указывая его родительский элемент на его дочерний элемент и наоборот. Второй, если делает то же самое, но вместо этого проверяет, является ли del правильным дочерним элементом его родительского узла. Наконец, удалите узел.

del->right->parent = del->parent; 
if (del == del->parent->left) 
    del->parent->left = del->right; 
else if (del == del->parent->right) 
    del->parent->right = del->right; 
delete del; 

случай 3:

TreeNode *inOrderSuccessor = maximum(del->right); 
del->val = inOrderSuccessor->val; //you could use transplant/swap here 
deleteNode(inOrderSuccessor, inOrderSuccessor->val); 

Вот об этом.