Alvin Seville
335 / 267 / 132
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 9
1

Удаление из AVL-дерева

18.11.2018, 16:55. Показов 1104. Ответов 1
Метки нет (Все метки)

Узел дерева:
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
44
namespace AVL_Tree
{
    /// <summary>
    /// Узел дерева.
    /// </summary>
    /// <typeparam name="T">Тип элемента.</typeparam>
    public class TreeNode<T>
    {
        /// <summary>
        /// Значение.
        /// </summary>
        public T value;
 
        /// <summary>
        /// Левый потомок.
        /// </summary>
        public TreeNode<T> left;
 
        /// <summary>
        /// Правый потомок.
        /// </summary>
        public TreeNode<T> right;
 
        /// <summary>
        /// Родитель.
        /// </summary>
        public TreeNode<T> parent;
 
        /// <summary>
        /// Показатель баланса.
        /// </summary>
        public int balance;
 
        public TreeNode(T value = default(T), TreeNode<T> left = null, TreeNode<T> right = null, TreeNode<T> parent = null)
        {
            this.value = value;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
 
        public override string ToString() => value.ToString();
    }
}
Само дерево:
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
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
using System;
using System.Collections.Generic;
 
namespace AVL_Tree
{
    class AVLTree<T>
    {
        private TreeNode<T> root;
 
        private void ThrowIfEmpty()
        {
            if (Count == 0)
                throw new InvalidOperationException("Недопустимо малое количество элементов для произведения требуемой операции.");
        }
 
        private TreeNode<T> Find(TreeNode<T> root, T x)
        {
            if (root == null)
                return null;
 
            if (Comparer.Compare(root.value, x) > 0)
                return Find(root.left, x);
            else if (Comparer.Compare(root.value, x) < 0)
                return Find(root.right, x);
 
            return root;
        }
 
        private TreeNode<T> Insert(ref TreeNode<T> root, TreeNode<T> parent, T x)
        {
            if (root == null)
            {
                root = new TreeNode<T>(value: x, parent: parent);
                return root;
            }
            else
            {
                if (Comparer.Compare(root.value, x) > 0)
                    return Insert(ref root.left, root, x);
                else if (Comparer.Compare(root.value, x) < 0)
                    return Insert(ref root.right, root, x);
                else
                    throw new ArgumentException($"Узел со значением {x} уже включён в бинарное дерево поиска.");
            }
        }
 
        private void TryChangeRoot(TreeNode<T> pivot)
        {
            if (pivot == root)
                root = pivot.parent;
        }
 
        private void RotateRight(TreeNode<T> pivot)
        {
            TreeNode<T> left = pivot.left;
            pivot.left = left.right;
            if (left.right != null)
                left.right.parent = pivot;
 
            TreeNode<T> parent = pivot.parent;
            left.right = pivot;
            pivot.parent = left;
 
            left.parent = parent;
            if (parent != null)
                if (parent.right == left.right)
                    parent.right = left;
                else
                    parent.left = left;
 
            TryChangeRoot(pivot);
 
            left.right.balance = Math.Max(left.balance, 0) + 1;
            left.balance = Math.Min(0, left.right.balance) - 1;
        }
 
        private void RotateLeft(TreeNode<T> pivot)
        {
            TreeNode<T> right = pivot.right;
            pivot.right = right.left;
            if (right.left != null)
                right.left.parent = pivot;
 
            TreeNode<T> parent = pivot.parent;
            right.left = pivot;
            pivot.parent = right;
 
            right.parent = parent;
            if (parent != null)
                if (parent.left == right.left)
                    parent.left = right;
                else
                    parent.right = right;
 
            TryChangeRoot(pivot);
 
            right.left.balance = Math.Min(0, right.balance) - 1;
            right.balance = Math.Max(right.left.balance, 0) + 1;
        }
 
        private void RotateLeftRight(TreeNode<T> pivot)
        {
            RotateLeft(pivot.left);
            RotateRight(pivot);
        }
 
        private void RotateRightLeft(TreeNode<T> pivot)
        {
            RotateRight(pivot.right);
            RotateLeft(pivot);
        }
 
        private void InsertAndRebalance(T x)
        {
            TreeNode<T> current = Insert(ref root, null, x);
 
            while (current.parent != null)
            {
                if (current == current.parent.left)
                    current.parent.balance++;
                else
                    current.parent.balance--;
 
                if (current.parent.balance == 2)
                {
                    if (current.balance == -1)
                    {
                        RotateLeftRight(current.parent);
                        current = current.parent;
                    }
                    else if (current.balance == 1)
                        RotateRight(current.parent);
                    break;
                }
                else if (current.parent.balance == -2)
                {
                    if (current.balance == 1)
                    {
                        RotateRightLeft(current.parent);
                        current = current.parent;
                    }
                    else if (current.balance == -1)
                        RotateLeft(current.parent);
                    break;
                }
                else
                    current = current.parent;
            }
            Count++;
        }
 
        private T RemoveMin(ref TreeNode<T> root)
        {
            if (root.left != null)
                return RemoveMin(ref root.left);
            else
            {
                T result = root.value;
                root = root.right;
                return result;
            }
        }
 
        private void Remove(ref TreeNode<T> root, in T x)
        {
            if (root == null)
                throw new ArgumentException($"Узел со значением {x} не найден.");
 
            if (Comparer.Compare(root.value, x) == 0)
            {
                if ((root.left == null) && (root.right == null))
                    root = null;
                else if (root.left == null)
                    root = root.right;
                else if (root.right == null)
                    root = root.left;
                else
                    root.value = RemoveMin(ref root.right);
                Count--;
            }
            else if (Comparer.Compare(root.value, x) > 0)
                Remove(ref root.left, in x);
            else
                Remove(ref root.right, in x);
        }
 
        private void RemoveAndRebalance(in T x) // x - удаляемое значение
        {
 
        }
 
        private IEnumerable<T> ByAscending(TreeNode<T> root)
        {
            if (root != null)
            {
                foreach (var item in ByAscending(root.left))
                    yield return item;
 
                yield return root.value;
 
                foreach (var item in ByAscending(root.right))
                    yield return item;
            }
        }
 
        private IEnumerable<T> ByDescending(TreeNode<T> root)
        {
            if (root != null)
            {
                foreach (var item in ByDescending(root.right))
                    yield return item;
 
                yield return root.value;
 
                foreach (var item in ByDescending(root.left))
                    yield return item;
            }
        }
 
 
        /// <summary>
        /// Количество элементов.
        /// </summary>
        public int Count { get; private set; }
 
        /// <summary>
        /// Корень.
        /// </summary>
        public TreeNode<T> Root => root;
 
        /// <summary>
        /// Компаратор, используемый при сравнении элементов.
        /// </summary>
        public IComparer<T> Comparer { get; private set; }
 
        public AVLTree(IComparer<T> comparer) => Comparer = comparer;
 
        public AVLTree() : this(Comparer<T>.Default)
        {
        }
 
        /// <summary>
        /// Выполняет поиск элемента со значением x.
        /// </summary>
        /// <param name="x">Искомое значение.</param>
        /// <returns>Узел с искомым значением.</returns>
        public TreeNode<T> Find(T x) => Find(root, x);
 
        /// <summary>
        /// Вставляет элемент со значением x.
        /// </summary>
        /// <param name="x">Вставляемое значение.</param>
        public void Insert(T x) => InsertAndRebalance(x);
 
        /// <summary>
        /// Возвращает последовательность элементов дерева по возрастанию.
        /// </summary>
        /// <returns>Последовательность элементов.</returns>
        public IEnumerable<T> ByAscending() => ByAscending(root);
 
        /// <summary>
        /// Возвращает последовательность элементов дерева по убыванию.
        /// </summary>
        /// <returns>Последовательность элементов.</returns>
        public IEnumerable<T> ByDescending() => ByDescending(root);
    }
}
Метод RemoveAndRebalance - занимается удалением узла из дерева и перебалансировкой дерева. В нём я собираюсь в цикле подниматься по дереву после удаления и балансировать при надобности узлы. Вопрос такой: как лучше мне подправить RemoveMin и Remove, чтобы реализовать так как хочу RemoveAndRebalance?

Сам алгоритм я запоминал по книге Сенюковой - Сбалансированные деревья поиска.

Добавлено через 58 минут
Вопрос актуален.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
18.11.2018, 16:55
Ответы с готовыми решениями:

Ошибка компилятора "Рекурсивное определение структур" при реализации AVL-дерева
Здравствуйте форумчане!! Реализовываю AVL-дерево, практически написал, но появилась ошибка ...

Удаление узла из AVL-дерева
Почему можно так (стр 28) сделать ? Добавлено через 2 минуты Как вообще может найтись такой...

Физическое удаление из AVL-дерева
Можно ли при удалении сначала провести балансировку и пересчитать балансы, а потом произвести...

Балансировка AVL дерева
Здравствуйте. У меня возникла такая проблема, не могу сбалансировать AVL дерево, верней даже не...

1
Alvin Seville
335 / 267 / 132
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 9
19.11.2018, 16:35  [ТС] 2
Переформулирую вопрос. Вот при добавлении всё просто - по ссылкам смотришь откуда поднялся и меняешь баланс соответственно. А как сделать то же самое в случае удаления, если узел удалён уже?

Добавлено через 1 минуту
Критерий оптимальности для данной структуры данных - скорость. Она должна работать максимально быстро.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
19.11.2018, 16:35
Помогаю со студенческими работами здесь

Сделать вывод AVL дерева
Не получается сделать наглядный вывод дерева. В traverse_debug ошибка не могу ее исправить. Вот...

Графическое представление AVL дерева
Пытаюсь реализовать графическое представление AVL дерева. Swing знаю более 3-х дней. Понимаю...

Проверить на эквивалентность два AVL-дерева
Такое вот задание: проверить на эквивалентность два АВЛ-дерева. Если они не являются информационно...

Операции над бинарными деревьями: построение дерева, обход дерева, вставка и удаление элемента дерева
Пожалуйста кто сможет, помогите составить программу: Организация по трудоустройству населения...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru