Удаление узла из бинарного дерева

@Disaczar · Регистрация: 24.02.2017

Студворк — интернет-сервис помощи студентам

всем доброго времени суток.

помогите пожалуйста с удалением элемента из дерево, а именно с методом my_node* erase(my_node* _ptr, const _key_type _key);
можно сделать удаление без балансировки дерева, так как по заданию этого делать не нужно

вот код всего класса

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
#pragma once
#include <vector>
 
template <class _key_type, class _data_type>
struct pair {
    _key_type _key;
    _data_type _data;
};
 
template <class _key_type, class _data_type>
struct node {
    pair<_key_type, _data_type> _value;
    node<_key_type, _data_type>* _left;
    node<_key_type, _data_type>* _right;
};
 
template <class _key_type, class _data_type>
class binary_tree {
private:
    using my_node = typename node<_key_type, _data_type>;
 
    my_node* _tree;
    unsigned int _size;
 
    _data_type value(my_node* _ptr, const _key_type _key) const;
    void value(my_node* _ptr, const _key_type _key, const _data_type _data);
    void insert(my_node* _ptr, const _key_type _key, const _data_type _data);
    my_node* erase(my_node* _ptr, const _key_type _key);
    void keys(my_node* _ptr, std::vector<_key_type>& _src) const;
    void show(my_node* _ptr) const;
    void show_balance_value(my_node* _ptr) const;
    void copy(my_node* _ptr);
    void create_element(my_node* _new, const _key_type _key, const _data_type _data);
    my_node* receiver(my_node* _ptr);
public:
    binary_tree();
    binary_tree(const binary_tree& _T);
    ~binary_tree();
    unsigned int size() const;
    void clear();
    bool empty() const;
    _data_type value(const _key_type _key) const;
    void value(const _key_type _key, const _data_type _data);
    void insert(const _key_type _key, const _data_type _data);
    void erase(const _key_type _key);
    std::vector<_key_type> keys() const;
    void show() const;
    void show_balance_value() const;
};
 
template<class _key_type, class _data_type>
inline binary_tree<_key_type, _data_type>::binary_tree() {
    _tree = NULL;
    _size = 0;
}
 
template<class _key_type, class _data_type>
inline binary_tree<_key_type, _data_type>::binary_tree(const binary_tree& _T) {
    copy(T._tree);
}
 
template<class _key_type, class _data_type>
inline binary_tree<_key_type, _data_type>::~binary_tree() {
    clear();
}
 
template<class _key_type, class _data_type>
inline unsigned int binary_tree<_key_type, _data_type>::size() const {
    return _size;
}
 
template<class _key_type, class _data_type>
inline void binary_tree<_key_type, _data_type>::clear() {
    while (_tree != NULL) {
        _key_type _key = _tree->_value._key;
        erase(_key);
    }
}
 
template<class _key_type, class _data_type>
inline bool binary_tree<_key_type, _data_type>::empty() const {
    return !_size;
}
 
template<class _key_type, class _data_type>
inline _data_type binary_tree<_key_type, _data_type>::value(const _key_type _key) const {
    my_node* ptr = _tree;
    return value(ptr, _key);
}
 
template<class _key_type, class _data_type>
inline void binary_tree<_key_type, _data_type>::value(const _key_type _key, const _data_type _data) {
    my_node* ptr = _tree;
    value(ptr, _key, _data);
}
 
template<class _key_type, class _data_type>
inline void binary_tree<_key_type, _data_type>::insert(const _key_type _key, const _data_type _data) {
    if (_tree == NULL) {
        create_element(_tree, _key, _data);
    }
    else {
        my_node* ptr = _tree;
        insert(ptr, _key, _data);
    }
    ++_size;
}
 
template<class _key_type, class _data_type>
inline void binary_tree<_key_type, _data_type>::erase(const _key_type _key) {
    my_node* ptr = _tree;
    erase(ptr, _key);
    --_size;
}
 
template<class _key_type, class _data_type>
inline std::vector<_key_type> binary_tree<_key_type, _data_type>::keys() const {
    my_node* ptr = _tree;
    std::vector<_key_type> source;
    keys(ptr, source);
    return source;
}
 
template<class _key_type, class _data_type>
inline void binary_tree<_key_type, _data_type>::show() const {
    my_node* ptr = _tree;
    show(ptr);
}
 
template<class _key_type, class _data_type>
inline void binary_tree<_key_type, _data_type>::show_balance_value() const {
    my_node* ptr = _tree;
    show_balance_value(ptr);
}
 
template<class _key_type, class _data_type>
inline _data_type binary_tree<_key_type, _data_type>::value(my_node* _ptr, const _key_type _key) const {
    if (_key < _ptr->_value._key) {
        return value(_ptr->_left, _key);
    }
    else if (_key > _ptr->_value._key) {
        return value(_ptr->_right, _key);
    }
    else if (_key == _ptr->_value._key) {
        return _ptr->_value._data;
    }
    else throw std::exception("sample text");
}
 
template<class _key_type, class _data_type>
inline void binary_tree<_key_type, _data_type>::value(my_node* _ptr, const _key_type _key, const _data_type _data) {
    if (_key < _ptr->_value._key) {
        value(_ptr->_left, _key, _data);
    }
    else if (_key > _ptr->_value._key) {
        value(_ptr->_right, _key, _data);
    }
    else if (_key == _ptr->_value._key) {
        _ptr->_value._data = _data;
    }
    else throw std::exception("sample text");
}
 
template<class _key_type, class _data_type>
inline void binary_tree<_key_type, _data_type>::insert(my_node* _ptr, const _key_type _key, const _data_type _data) {
    if (_key < _ptr->_value._key) {
        if (_ptr->_left != NULL) {
            insert(_ptr->_left, _data);
        }
        else {
            create_element(_ptr->_left, _key, _data);
        }
    }
    else if (_key > _ptr->_value._key) {
        if (_ptr->_right != NULL) {
            insert(_ptr->_right, _data);
        }
        else {
            create_element(_ptr->_right, _key, _data);
        }
    }
    else {
        _ptr->_value._data = _data;
    }
}
 
template<class _key_type, class _data_type>
inline node<_key_type, _data_type>* binary_tree<_key_type, _data_type>::erase(my_node* _ptr, const _key_type _key) {
    if (_ptr == NULL) {
        return _ptr;
    }
    if (_key < _ptr->_value._key) {
        _ptr->_left = erase(_ptr->_left, _key)
    }
    else if (_key > _ptr->_value._key) {
        _ptr->_right = erase(_ptr->_right, _key)
    }
    else if (_ptr->_left != NULL && _ptr->_right != NULL) {
        _ptr->_value = receiver(_ptr->_right)->_value;
        _ptr->_right = erase(_ptr->_right, _ptr->_value._key);
    }
    else {
        if (_ptr->_left != NULL) _ptr = _ptr->_left;
        else _ptr = _ptr->_right;
    }
    return _ptr;
}
 
template<class _key_type, class _data_type>
inline void binary_tree<_key_type, _data_type>::keys(my_node* _ptr, std::vector<_key_type>& _src) const {
    if (_ptr->_left != NULL) {
        keys(_ptr->_left, _src);
    }
    if (_ptr->_right != NULL) {
        keys(_ptr->_right, _src);
    }
    _src.push_back(_ptr->_value._key);
}
 
template<class _key_type, class _data_type>
inline void binary_tree<_key_type, _data_type>::show(my_node* _ptr) const {
    if (_ptr->_left != NULL) {
        show(_ptr->_left);
    }
    if (_ptr->_right != NULL) {
        show(_ptr->_right);
    }
    std::cout << _ptr->_value._data;
}
 
template<class _key_type, class _data_type>
inline void binary_tree<_key_type, _data_type>::show_balance_value(my_node* _ptr) const {
 
}
 
template<class _key_type, class _data_type>
inline void binary_tree<_key_type, _data_type>::copy(my_node* _ptr) {
 
}
 
template<class _key_type, class _data_type>
inline void binary_tree<_key_type, _data_type>::create_element(my_node* _new, const _key_type _key, const _data_type _data) {
    _new = new my_node;
    _new->_left = NULL;
    _new->_right = NULL;
    _new->_value._key = _key;
    _new->_value._data = _data;
}
 
template<class _key_type, class _data_type>
inline node<_key_type, _data_type>* binary_tree<_key_type, _data_type>::receiver(my_node* _ptr) {
    if (_ptr->_left == NULL) {
        return _ptr->_left;
    }
    return receiver(_ptr->_left);
}

@БедолагаЖека · 17.11.2019, 08:41

А зачем они inline все? Что бы реверсер повесился?

Не увидел ни одного delete

my_node* erase(my_node* _ptr, const _key_type _key);

Что она должна вернуть и зачем?
Что такое my_node* и const _key_type и зачем они вместе?

@БедолагаЖека · 17.11.2019, 08:44

Почему-то дубль сообщения запостился.

@Disaczar · 17.11.2019, 09:06 **[ТС]**

Сообщение от БедолагаЖека

А зачем они inline все? Что бы реверсер повесился?

все методы шаблонные же

Сообщение от БедолагаЖека

Не увидел ни одного delete

ну, если бы они были - я бы не писал сюда. именно с ними-то у меня и проблемы.

Сообщение от БедолагаЖека

Что она должна вернуть и зачем?

указатель на корень дерева (забыл присвоить в публичном erase)

Сообщение от БедолагаЖека

Что такое my_node* и const _key_type и зачем они вместе?

my_node - псевдоним node<_key_type, _data_type)
а const _key_type - передаю ключ как константу (хотя на самом деле надо бы передать ссылку...)

@БедолагаЖека · 17.11.2019, 09:42

Сообщение от Disaczar

все методы шаблонные же

Шаблоны классов в С++

Сообщение от Disaczar

псевдоним node

указатель на удаляемый узел?

Сообщение от Disaczar

передаю ключ как константу

уникальный идентификатор?

@Disaczar · 17.11.2019, 10:33 **[ТС]**

Сообщение от БедолагаЖека

Шаблоны классов в С++

а зачем тогда ещё и vs инлайнит эти функции?

Сообщение от БедолагаЖека

указатель на удаляемый узел?

нет, это, скажем так, сокращение, чтобы не писать node<_key_type, _data_type>, а просто my_node

Сообщение от БедолагаЖека

уникальный идентификатор?

да, ибо по ключу(уникальному идентификатору) происходит удаление

Добавлено через 2 минуты
вообще, я могу нормально удалить элемент с информацией о родителе, но лучше же без неё

@БедолагаЖека · 17.11.2019, 10:52

Сообщение от Disaczar

да, ибо по ключу(уникальному идентификатору) происходит удаление

отлично.

Сообщение от Disaczar

нет, это, скажем так, сокращение, чтобы не писать node<_key_type, _data_type>, а просто my_node

ЗАЧЕМ ЭТО ТУДА ПЕРЕДАВАТЬ??? Что это по факту такое? Какой в этом смысОл?

Добавлено через 12 минут
Ты так долго свои реплики постишь - тебе кто-то подсказывает как конкретно протупить надо?

@Disaczar · 17.11.2019, 11:39 **[ТС]**

Сообщение от БедолагаЖека

Ты так долго свои реплики постишь

помимо сидения на форумах у меня есть свои дела ирл, поэтому и отвечаю долго

Сообщение от БедолагаЖека

как конкретно протупить надо

вам так вообще не объяснили, что ключ и уникальный идентификатор - одно и то же

Сообщение от БедолагаЖека

ЗАЧЕМ ЭТО ТУДА ПЕРЕДАВАТЬ

это удобнее...

@БедолагаЖека · 17.11.2019, 13:35

Disaczar, удачи вам.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .	Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»	SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .

@БедолагаЖека 43 / 39 / 5 Регистрация: 16.09.2019 Сообщений: 285
	17.11.2019, 08:44
	Почему-то дубль сообщения запостился. 0

@БедолагаЖека 43 / 39 / 5 Регистрация: 16.09.2019 Сообщений: 285
	17.11.2019, 13:35
	Disaczar, удачи вам. 0