平衡型バイナリ検索ツリーからの削除

Question

ノードをバランス型BSTから削除したいとします。私は次のコードを書いて、子を削除する際に働きますが、2つの子を持つノードを削除したい場合、リンクは復元されますが、他のノードは失われます。私はキー4を持つノードを削除したい場合は

  9 
    4   15 
1  7 10  18 

は、結果ツリーは次のようになります：

 9 
7   15 
      10  18 

Nod* minValue(Nod *p) 
{ 
    Nod *q = p; 

    while (q->stg != NULL) 
     q = q->stg; 

    return q; 
} 

Nod* os_delete(Nod *p, int k) 
{ 
    if (p == NULL) 
     return p; 

    if (k < p->ch) 
    { 
    p->stg = os_delete(p->stg, k); 
    } 

    else if (k > p->ch) 
    { 
    p->dr = os_delete(p->dr, k); 
    } 

    else 
    { 
     p->size--; 
     if (p->stg = NULL) 
     { 
      Nod* aux = p->dr; 
      free(p); 
      return aux; 
     } 
     else if (p->dr == NULL) 
     { 
      Nod* aux = p->stg; 
      free(p); 
      return aux; 
     } 

     Nod* aux = minValue(p->dr); 
     p->ch = aux->ch; 
     p->dr = os_delete(p->dr, aux->ch); 
    } 
    return p; 

}たとえば

：これは私のコードです

編集：

typedef struct nod 
{ 
    int ch, size; // ch - key of the node; size - size of node's subtree 
    struct nod *stg, *dr; // stg - left; dr - right 
}Nod; 

Answer 1

バランスのとれたバイナリツリーから削除する1つの方法は、関数balance（）を作成することです。これは、ツリーのバランスをとるために使用されます。バイナリツリーの要素の参照ポインタをInorderのリストにコピーします。次に、リストの中央の要素を見つけます（2つの半分にリストを分割します）。新しいルートノードになります。ルートノードの左の子はリストの左半分の中央になり、ルートノードの右の子はリストの右半分の中央になります。バランスの取れたツリーを作成するためにこれを再帰的に実行します。 削除処理でこの関数を使用します。削除するノードを見つけている間、そのノードを親のままにしておきます。今度は、BSTの場合と同じように削除ロジックを構築しますが、このbalance（）関数を使用して、必要なときにいつでもツリーを再調整します。 ソース：http://www.codeproject.com/Articles/68500/Balanced-Binary-Search-Tree-BST-Search-Delete-InOr

ツリーのバランスを保つ方法はわかりませんが、別の簡単な方法は、AVLまたはR-Bツリーなどの自己分散バイナリ検索ツリーを実装することです。