Удаление элемента из двоичного бинарного дерева поиска

Здравствуйте!

Подскажите пожалуйста, как удалить элемент из двоичного бинарного дерева поиска, если имеются как левое, так и правое ответвление(очень желательно, что бы была теория и сам алгоритм)?

Я уже читал теорию в другой похожей теме, но не понял её(именно ту часть, где говорится о том, что делать, если есть два ответвления). Смотрел пример на C, переписал под C#-в итоге, нужный элемент не удалился, а при последующей попытке удалить элемент с одним ответвлением получал Exception("Ссылка не ссылается на экземпляр объекта")...

Вот кот, который у меня есть на данный момент(проверял-вроде бы то, что готово-то работает правильно(во всяком случае-согласно той теории, которую я читал)):

Кликните здесь для просмотра всего текста

C#Выделить код

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

public BinaryTree<TYPE> DeleteData(TYPE ValueKey)
            {
                BinaryTree<TYPE> ThisData = this;
                if (ThisData.Value == null) throw new Exception("Невозможно удалить элемент из пустого дерева");
                else
                {
                    Int32 CompareToResult = ThisData.Value.CompareTo(ValueKey);
                    if (CompareToResult == 0)
                    {
                        if (ThisData.Right == null && ThisData.Left == null)
                        {
                            ThisData = ThisData.Parrent;
                            {
                                if (ThisData.Value.CompareTo(ValueKey) > 0) ThisData.Left = null;
                                else if (ThisData.Value.CompareTo(ValueKey) < 0) ThisData.Right = null;
                            }
                        }
                        else if (ThisData.Right == null && ThisData.Left != null)
                        {
                            ThisData = ThisData.Parrent;
                            {
                                if (ThisData.Value.CompareTo(ValueKey) > 0) ThisData.Left = ThisData.Left.Left;
                                else if (ThisData.Value.CompareTo(ValueKey) < 0) ThisData.Right = ThisData.Right.Left;
                            }
                        }
                        else if (ThisData.Right != null && ThisData.Left == null)
                        {
                            ThisData = ThisData.Parrent;
                            {
                                if (ThisData.Value.CompareTo(ValueKey) > 0) ThisData.Left = ThisData.Left.Right;
                                else if (ThisData.Value.CompareTo(ValueKey) < 0) ThisData.Right = ThisData.Right.Right;
                            }
                        }
                        else if (ThisData.Right != null && ThisData.Left != null)
                        {
                        }
                    }
                    else if (CompareToResult > 0) ThisData.Left.DeleteData(ValueKey);
                    else if (CompareToResult < 0) ThisData.Right.DeleteData(ValueKey);
                }
                while (ThisData.Parrent != null) ThisData = ThisData.Parrent;
                return ThisData;
            }

Я читал здесь, что нужно двигаться в первой ветви до дна в левую часть, и присвоить parent левой части удаляемого элемента ссылке на левое дно Right... Пытался реализовать этот алгоритм-ничего хорошего не вышло...

Вот, "не рабочий алгоритм":

Кликните здесь для просмотра всего текста

C#Выделить код

1
2
3
4
5
6

BinaryTree<TYPE> NRight = ThisData.Right;
                            while (NRight.Left != null) NRight = NRight.Left;
                            BinaryTree<TYPE> NLeft = ThisData.Left;
                            NLeft.Parrent = NRight;
                            while (NLeft.Parrent != null) NLeft = NLeft.Parrent;
                            ThisData = NLeft;

P.S. Сразу пишу в Windows Application варианте. Таблицу DataGridView после удаления элемента всю обновляю(т.е. сразу получаю список всех элементов, после чего именно из списка получаю всё обратно в DataGridView). Все Exception перехватываю блоком Try/Catch.

Обходить мне моё дерево по заданию надо через рекурсию. Ну, я и обхожу... Вызываю этот метод удаления лишь в процессе поиска нужного элемента.