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(Node *cur, string s);の責任であるべきノードを削除、ノードを探していることはvoid delete_node_helper(string s);の責任であることを言うだろう、と子供をマージすることは、新しく作成された者の責任でなければなりません関数。

最初の2つの部分のアルゴリズムが非常に厳密であることを考えると、3番目の部分だけを詳細に説明します。

BST（どちらが残っていてどちらが正しいか）をマージするには、誰がその子になるかを決定し、必要に応じて再帰的マージを実行する必要があります。コードは次のようになります。

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; 
} 

マークされた行では、実際にどのノードがその親であるかを決定します。この特定の例では、結果はランダムであるが、他の戦略を実装することもできる。たとえば、ツリーのすべてのノードに高さ（またはサイズ）を格納し、大きなツリールートの小さいツリールートの子ノードにすることができます。