Удаление в дереве bst

Question

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

class Node { 
    friend class Tree; 
private: 
    long long rep; 
    Node *left, *right; 
    string data; 
public: 
    Node(string d) 
     : data(d), left(NULL), right(NULL), rep(1) {} 
}; 

class Tree { 
private: 
    Node *root; 
public: 
    void delete_node(Node *cur , string s); 
    void delete_node_helper(string s); 
}; 

Answer 1

Delete a special node from a BST tree

Я просто попытался код удаления в ссылке выше, и она работала хорошо.

Answer 2

Там вы 3 части в удалении узла из бинарного дерева поиска:

1. найти узел для удаления.
2. Удалить узел (свободная память и т. Д.).
3. Объединить детей удаленного узла.

В вашем конкретном примере кода, я бы сказал, что ищет узел должен нести ответственность void delete_node_helper(string s);, удаление узла должна быть ответственность void delete_node(Node *cur, string s);, и объединение детей должны нести ответственность за вновь созданной функция.

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

Чтобы слить два BST s (из которых мы знаем, какой из них оставлен, а какой правильный), мы должны решить, кто будет дочерним и, если необходимо, выполнить рекурсивное слияние. Код выглядит так:

Node* merge(Node* left, Node* right) { 
    if (left == nullptr) { 
     return right; 
    } 
    if (right == nullptr) { 
     return left; 
    } 
    if (rand() & 1) {        // <- chose parent 
     left->right = merge(left->right, right); 
     return left; 
    } 
    right->left = merge(left, right->left); 
    return right; 
} 

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