| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > АВЛ сбалансированное бинарное дерево поиска |
| Автор: MaXL 20.10.2008, 09:32 |
| Всем привет. Задали реализовать АВЛ-сбалансированное бинарное дерево поиска. и К нему несколько функций, для работы с ним. Препод дал *.h файл в котором описаны прототипы функция, а мне нужно написать *.c файл, где их реализация. Так вот вроде бы всё понятно и просто, но возникла проблема, при реализации итератора. Есть функция InsertBeforeIterator, которая вставляет элемент в дерево, перед итератором. Итератор может указывать на любой элемент дерево(для создания итератора, и его двигания есть спец. функции). Так вот, что же делать в этом случае, куда и как вставлять. Я вот думаю просто забивать на позицию итератора и вставлять куда мне хочется(на какой-нибудь лист -> балансировка). |
| Автор: Lazin 20.10.2008, 11:26 |
| в принципе, любой нод можно рассматривать как вершину дерева |
| Автор: Earnest 20.10.2008, 16:57 |
| Посмотри на std::map и сделай аналогично. Там тоже есть функция вставки с итератором. Хотя сам map упорядочен и позиция вставки определяется ключом. Итератор в этом случае является подсказкой=хинтом, которая позволяет ускорить поиск места вставки (если, конечно, итератор правильно указан). Иначе, надо полагать, производится поиск от корня... |
| Автор: MaXL 21.10.2008, 08:39 |
| Lazin, и что это даёт, как разница куда вставлять в вершину или в узел какой-то. там ведь всё дело в ключах. Earnest, я с STL не работал, так только по наслышке знаю, что там при вставке нужно указывать ключ. А фишка в том, что в этой библиотеке, которую нам дали, вообще ключи мы делаем сами. И как тут быть я хз, это вообще не дерево а не понять что получается... |
| Автор: MaXL 22.10.2008, 08:26 |
| Всем спасибо. Вапрос снят. Препод подправил *.h файл. Как и оказалось, функции с подобными параметрами не имеют смысла. |