BSTのノードを削除します

Question

私はBSTの削除を実装しようとしています。私が使用しています アルゴリズムは次のとおりです。

1. 検索が一つのノード

1.1に一致する場合。左の子ノードがある場合は、このノードとその左の子ノードの値を入れ替えます。もう一度左ノードの機能を呼び出します。

1.2。そうでなければ、左ノードはないが右ノードがある場合は、ノードと右ノードの値を入れ替えます。右のノードの関数を呼び出します。

1.3。左ノードも右ノードもない場合は、このノードを削除します。

以下は、クラス定義です。私は...、私の左の子は...、私の右の子である...

void node::print(){ 
    if(this == 0) return; 
    cout<<"i am "<<value<<endl; 
    if(left !=0){ 
    cout<<"i have left, left is "<<left -> value<<endl; 
    } 
    if(right !=0){ 
    cout<<"i have right, right is "<<right -> value <<endl; 
    } 
} 

のprintAll（）関数をプリントアウトする

class node{ 
    public: 
    int value; 
    node *left; 
    node *right; 
    node(){value=0; left=0; right =0;} 
    node(int value){this -> value = value; left=0;right=0;} 
    void print(); 
}; 

class tree{ 
    public: 
    node *root; 
    tree(){ 
    root = 0; 
    } 
    ~tree(){} 
    void remove(node *, int); 
    //tree(int value){root = &node(value);} 
    void insert(int); 
    void printSorted(node *); 
    void printAll(node *); 
}; 

印刷（）関数からのトラバースrootとprintを順番に実行します。

void tree::printAll(node *nodeP){ 
    if(nodeP == 0) return; 
    else{ 
    node *iter = nodeP; 
    if(iter -> left !=0){ 
     printAll(iter->left); 
    } 
    iter->print(); 
    cout<<endl; 
    if(iter -> right !=0){ 
     printAll(iter -> right); 
    } 
    } 
} 

これは削除機能です。削除呼び出し後7 4 10 1 6 5

void tree::remove(node* origin, int toDel){ 
    if(origin == 0) return; 
    node *orig_origin = origin; 
    int tmp; 
    if(origin -> value == toDel){ 
    if((origin -> left == 0) && (origin -> right == 0)){ 
     delete origin; 
     origin =0; 
    } 
    else if((origin -> left != 0) && (origin -> right == 0)){ 
     tmp = origin -> value; 
     origin -> value = origin -> left -> value; 
     origin -> left -> value = tmp; 
     remove(origin -> left, toDel); 
    } 
    else if((origin -> left == 0) && (origin -> right != 0)){ 
     tmp = origin -> value; 
     origin -> value = origin -> right -> value; 
     origin -> right -> value = tmp; 
     remove(origin -> right, toDel); 
    } 
    else{ 
     tmp = origin -> value; 
     origin -> value = origin -> left -> value; 
     origin -> left -> value = tmp; 
     remove(origin -> left, toDel); 
    } 
    } 
    else{ 
    if(origin -> value > toDel) remove(origin -> left, toDel); 
    else remove(origin -> right, toDel); 
    } 
    origin = orig_origin; 
} 

I入力、1は、元の4の位置にあります。しかし、0の左の子があります。だから何とか私は元の1ノードを削除することに失敗しました。

sc-xterm-24:~/scratch/code/cpp_primer> ./a.out 
7 4 10 1 6 5 
i am 0 

i am 1 
i have left, left is 0 
i have right, right is 6 

i am 5 

i am 6 
i have left, left is 5 

i am 7 
i have left, left is 1 
i have right, right is 10 

i am 10 

Answer 1

ツリーの値を見つけたら、最後のケース（左右の枝がある）の処理が間違っています。 origin->valueとorigin->left->valueを交換することはできません。これは、ツリーに必要な順序付けを破るためです。元のorigin->valueが左のサブツリーに格納されているすべての値よりも大きいため、新しいorigin->left->valueは、origin->left->rightサブツリーに格納されているすべての値よりも大きくなります。ノード内の値は、正しいツリーに格納されているすべての値より小さくなければならないので、そのブランチに沿った将来の検索は失敗したり、間違ったノードを見つけることができます。