私の削除がツリーを順番に (左から右へ) バランスを取り直そうとすると仮定します。
私は現在 BinarySearchTree クラスを書いていますが、ほとんどの場合、私の削除機能は現在機能しています (私は <3 を願っています)。私は対処すべきいくつかのフリンジケースを持っています:
- 親ノードがないため、ルート ノードを削除しても機能しません。
- next に 2 つの子がある最後のケースでは、その左端の一番右の子孫が右の子自体である場合、newCurr は next を指します。これは、newCurr (別名 next) が New と交換されるため、問題を引き起こします。
ルート削除の提案された解決策:
私の解決策は、ルートを削除し、BST クラスのメンバー関数を使用して Root を New に設定し (そのノードをルートにする)、New があった場所を 0/NULL に設定することです。
A: これは機能しますが、ケースワークをあちこちに配置する必要があります。
BST クラスにダミーの親ノードを用意します。このノードは単にルート ノードを右側のオブジェクトとして持ちます (billyswong による提案)。
A: これでうまくいくかもしれませんが、それに対処するには特別なケースの作業が必要だと思います。
2 人の子供を削除するための提案された解決策:
私の解決策は、New の場所を一時的に保存し、親の New の場所を New の右の子に設定してから、一時ポインタを削除することです。
A: これは機能しますが、私が思っているほどエレガントではありません。
- 「ノードを回転させます」（Agorが提案した方法がわからない）。
これが私のコードです：
if (root()->value() == val)
{
delete root();
this->setRoot(New);
newCurr->setLeft(0);
}
else if (newCurr == next)
{
Node *temp = New;
newCurr->setRight(New->right());
delete temp;
}
ポスターは、このコードが 1) 機能するかどうか、2) 最適かどうか教えてください。
編集:関数の終わり近くで一貫性のないキャメルキャップの使用について申し訳ありません。変数名のより良い説明は思いつきませんでしたがnew、C++ で定義されたキーワードです。
Edit2: リファクタリングされたコードを投稿しましたが、エラーは解決しません。
void BinarySearchTree::del(int val)
{
//curr refers to the parent of next
//next is the node we will want to delete
Node* curr = 0;
Node* next = root();
//these will only be used if you get into
//the last case, where you have two children
//on next
Node* newCurr = curr;
Node* New = next;
//boolean value to check if you found the value
//in the binary search tree
bool found;
//set curr and next; will be false if val not found
found = setCurrAndNext(val, curr, next);
//get next to the node needing deletion
//and set curr to its parent
//pass by ref function
//return value is that you found it
if (found)
{
setNewCurrAndNew (newCurr, New);
}
else
{
return;
}
/* next is a leaf */
if (nextIsLeaf(next))
{
handleLeafCase(curr, next);
return;
}
/* next has a single child */
else if (nextHasSingleChild(next))
{
if(leftIsChild(next))
{
handleLeftCase(curr, next);
}
else
{
handleRightCase(curr, next);
}
}
/* next has two children */
else
{
if (newCurr == next)
{
Node *temp = New;
newCurr->setRight(New->right());
delete temp;
}
else if (next == curr->left())
{
if (New == newCurr->left())
{
curr->setLeft(New);
newCurr->setLeft(next);
}
else
{
curr->setLeft(New);
newCurr->setRight(next);
}
}
else
{
if (New == newCurr->left())
{
curr->setRight(New);
newCurr->setLeft(next);
}
else
{
curr->setRight(New);
newCurr->setRight(next);
}
}
if (next->left() == 0 && next->right() == 0)
{
newCurr->setRight(0);
newCurr->setLeft(0);
delete next;
}
else
{
if (next->left() == 0)
{
newCurr->setRight(next->left());
}
else
{
newCurr->setLeft(next->right());
}
delete next;
}
}
}
}