Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.77/13: Рейтинг темы: голосов - 13, средняя оценка - 4.77
67 / 40 / 14
Регистрация: 24.02.2013
Сообщений: 250
1

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

22.04.2014, 02:05. Просмотров 2330. Ответов 2
Метки нет (Все метки)

Здравствуйте!
Подскажите пожалуйста, как удалить элемент из двоичного бинарного дерева поиска, если имеются как левое, так и правое ответвление(очень желательно, что бы была теория и сам алгоритм)?
Я уже читал теорию в другой похожей теме, но не понял её(именно ту часть, где говорится о том, что делать, если есть два ответвления). Смотрел пример на 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.
Обходить мне моё дерево по заданию надо через рекурсию. Ну, я и обхожу... Вызываю этот метод удаления лишь в процессе поиска нужного элемента.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
22.04.2014, 02:05
Ответы с готовыми решениями:

Удаление поддеревьев из двоичного дерева поиска
Дано некоторое двоичное дерево поиска. Также даны запросы на удаление из него вершин, имеющих...

Некорректное удаление элемента бинарного дерева поиска
Задача состоит в том, чтобы удалить максимальный в левом поддереве элемент и все его порожденные...

Удаление элемента из бинарного дерева поиска (bst)
Есть структура данных bst с методом delete (и некоторыми другими, не имеющими отношения к данной...

Удаление элемента из двоичного дерева
Хочу окончательно завершить тему двоичное дерево и перейти к более сложным деревьям. Однако, не...

2
67 / 40 / 14
Регистрация: 24.02.2013
Сообщений: 250
19.05.2016, 05:14  [ТС] 2
Мда... Теме уже больше 2х лет и ни один человек так и до сих пор не дал ответа на вопрос...
Большое спасибо!

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

В общем, всё оказалось куда проще, чем казалось(осмелюсь предположить, что это я как то не так понял теорию). Нужно было удалять, вызывая этот же метод из самого левого элемента. Тогда будут исключены случаи удаления части дерева.

В общем, вот код(правда, это Java, но в данном случае, "не суть"):
Кликните здесь для просмотра всего текста

Java
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
44
45
46
    public void delete(int key)
    {
        if (this._key == key)//Если текущий элемент является удаляемым элементом
        {
            //Сперва, рассмотрим сценарий, где у нас нету ответвлений(удаляем лист, а не ветвь)
            if (this._left == null && this._right == null)
            {
                if (this._up != null)
                {
                    binaryTree<T> up = this._up;
                    if (up._key > key) up._left = null;
                    else up._right = null;
                }
                else System.out.println("Невозможно удалить единственный элемент дерева. Воспользуйтесь функцией замены элемента");
            }
            //После этого, рассмотрим сценарий, где у нас есть хотя бы одно ответвление
            else if ((this._left != null && this._right == null) || (this._right != null && this._left == null))
            {
                binaryTree<T> _backup = (this._left != null ? this._left : this._right);
                binaryTree<T> _backup_up = this._up;
                if (_backup_up._key > key)
                {
                    _backup_up._left = _backup;
                    _backup._up = _backup_up;
                }
                else if (_backup_up._key < key)
                {
                    _backup_up._right = _backup;
                    _backup._up = _backup_up;
                }
            }
            //И в конце, рассмотрим сценарий, где у нас оба ответвления присутствуют/не пустые
            else if (this._left != null && this._right != null)
            {
                binaryTree<T> _backup = this._right;
                while (_backup._left != null) _backup = _backup._left;
                int _backup_key = _backup._key;
                T _backup_value = _backup._value;
                this.delete(_backup_key);
                this._key = _backup_key;
                this._value = _backup_value;
            }
        }
        else if (this._key > key && this._left != null) this._left.delete(key);
        else if (this._key < key && this._right != null) this._right.delete(key);
    }
Проверил при удалении элемента с ключом 75.
Последовательность добавления элементов такая:
50(корень); 75; 25; 15; 24; 60; 65; 55; 80; 85; 90; 54; 56; 64; 66; 63
У удаляемого элемента(75) должно быть 2 ответвления: [L] - 60; [R] - 80. У элемента 80 левых ответвлений нету, там только правые.
0
Эксперт .NET
14489 / 10931 / 2886
Регистрация: 17.09.2011
Сообщений: 18,458
19.05.2016, 10:18 3
Цитата Сообщение от Jack Wade Посмотреть сообщение
Теме уже больше 2х лет и ни один человек так и до сих пор не дал ответа на вопрос
На момент создания этой темы уже более двух лет висела как минимум одна тема с полной реализацией двоичного дерева.
Можно было бы и глянуть

Не стесняйтесь поднимать тему, если на нее никто не отвечает: кому-то может быть неинтересно, а те, кому интересно могут быть в запое отпуске и просто ее не заметить.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.05.2016, 10:18

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Удаление элементов из бинарного дерева (не дерево поиска)
Задание заключается в создании бинарного дерева, из букв введенной строки, обходе дерева и удалении...

Удаление нечетных чисел из дерева бинарного поиска
Задача: Удалить нечетные числа из дерева бинарного поиска. Вообщем, ошибка в функции удаления...

Удаление элемента из бинарного дерева
в программе выполняется пару ф-й, не работает удаление элемента (в меню пункт 1), должен удалить...

Удаление элемента из бинарного дерева
Ругается компилятор в Visual Studio при выполнении кода удаления элемента, а именно в том месте,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.