Witam mam za zadanie dopisać metodę usuwającą wybrany element z drzewa :) znalazłem w internecie coś takiego:
public void Delete(IComparable data)
{
// odszukujemy węzeł do usunięcia (n)
// przeszukujemy drzewo aż do odnalezienia węzła n
Node current = root, parent = null;
int result = **current.Value.CompareTo(data);**
while (result != 0 && current != null)
{
if (result > 0)
{
// current.Value > n.Value
// a więc węzeł n może znajdować się
// w lewym poddrzewie węzła current
parent = current;
current = current.Left;
}
else if (result < 0)
{
// current.Value < n.Value
// a więc węzeł n może znajdować się
// w prawym poddrzewie węzła current
parent = current;
current = current.Right;
}
result = **current.Value.CompareTo(data);**
}
// jeśli current == null, to nie ma co usuwać
if (current == null)
throw new Exception("Element do usunięcia nie został znaleziony w drzewie BST.");
// zmienna current wskazuje teraz węzeł, który ma zostać
// usunięty, a zmienna parent wskazuje jego rodzica
count--;
// PRZYPADEK 1: jeśli węzeł current nie posiada prawego dziecka,
// to węzłem wskazywanym przez rodzica zostaje lewe dziecko
// węzła current
if (current.Right == null)
{
if (parent == null)
root = current.Left;
else
{
result = **parent.Value.CompareTo(current.Value);**
if (result > 0)
// parent.Value > current
// a więc lewe poddrzewo węzła current zostaje
// lewym poddrzewem węzła parent
parent.Left = current.Left;
else if (result < 0)
// parent.Value < current.Value
// a więc lewe poddrzewo węzła current zostaje
// prawym poddrzewem węzła parent
parent.Right = current.Left;
}
}
// PRZYPADEK 2: jeśli prawe dziecko węzła current nie posiada lewego
// dziecka, to prawe dziecko węzła current zastępuje węzeł current
else if (current.Right.Left == null)
{
if (parent == null)
root = current.Right;
else
{
result = **parent.Value.CompareTo(current.Value);**
if (result > 0)
// parent.Value > current
// a więc prawe poddrzewo węzła current zostaje
// lewym poddrzewem węzła parent
parent.Left = current.Right;
else if (result < 0)
// parent.Value < current.Value
// a więc prawe poddrzewo węzła current zostaje
// prawym poddrzewem węzła parent
parent.Right = current.Right;
}
}
// PRZYPADEK 3: Jeśli prawe dziecko węzła current posiada lewe
// dziecko, węzeł current zostaje zastąpiony skrajnym lewym węzłem
// swojego prawego poddrzewa
else
{
// odszukujemy skrajny lewy węzeł prawego poddrzewa
Node leftmost = current.Right.Left, lmParent = current.Right;
while (leftmost.Left != null)
{
lmParent = leftmost;
leftmost = leftmost.Left;
}
// prawe poddrzewo skrajnego lewego węzła zostaje
// lewym poddrzewem węzła parent
lmParent.Left = leftmost.Right;
// lewe i prawe dziecko węzła current zostaje lewym i prawym
// dzieckiem węzła skrajnie lewego
leftmost.Left = current.Left;
leftmost.Right = current.Right;
if (parent == null)
root = leftmost;
else
{
result = **parent.Value.CompareTo(current.Value);**
if (result > 0)
// parent.Value > current
// a więc węzeł skrajnie lewy zostaje lewym dzieckiem
// węzła parent
parent.Left = leftmost;
else if (result < 0)
// parent.Value < current.Value
// a więc węzeł skrajnie lewy staje się prawym dzieckiem
// węzła parent
parent.Right = leftmost;
}
}
}
Mam pytanie do tego kodu. Jakie wartości powinienem umieścić w miejscach z grubą czcionką ??
Mógłby ktoś mi to troszkę objaśnić ?? Nie chcę gotowca!!
- < code> - msm