| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > вывод элементов бинарного дерева не по ключу |
| Автор: Экскалупатор 10.11.2010, 17:10 |
| Всем привет. Есть такая проблема. у меня есть бинарное дерево, каждый узел содержит имя, фамилию, отчество и дату рождения, ключем является дата рождения. вопрос: как оптимально вывести данные из дерева в алфавитном порядке не позднее определенной даты. если выводить в определенном порядке по дате рождения то все просто, читай по ключу и все. но тут надо именно в алфавитном порядке(к примеру по фамилии). у меня созрело решение собрать второе дерево используя как ключ фамилию(или массив, отсортированный по фамилии). но мне кажется это как то коряво. как решить эту проблему не прибегая к помощи массивов/деревьев с временными данными. заранее спасибо. |
| Автор: Pavia 10.11.2010, 21:04 | ||
| Экскалупатор, Берешь дерево отсекаешь дату по ключу. Потом Сортируешь. Второе предложение.
Хорошее решение. Составить второй ключ. Только это ключ должен быть постоянным иначе в нем смысла нет. |
| Автор: Экскалупатор 10.11.2010, 21:17 | ||||
эээ что то не совсем понял мысль. типа сортировать дерево по другому ключу? но это все равно что заново пересоздать все дерево, а мне его менять нельзя, оно должно оставаться отсортированным по дате. и это тоже не совсем понял.
объясни по подробнее плиз. Добавлено через 3 минуты и 39 секунд подумал тут. можно же добавить дополнительные поля, для того что бы можно было создать из одних и тех же узлов два дерева, одно будет отсортировано по дате а второе по фамилии в алфавитном порядке.(или это и имелось ввиду под вторым ключем в предыдущем посте?). |
| Автор: Pavia 10.11.2010, 21:37 | ||
Именно так. Правда выбор структуры я оставил за вами: хочешь дерево или список - это уже как вам угодно. |
| Автор: Экскалупатор 10.11.2010, 22:34 |
| Pavia, спасибо. неплохая идея. лови +. но может есть просто алгоритм с помощью которого можно сделать такой вывод? просто мне не хотелось бы усложнять структуру узлов дерева и создавать лишних массивов. |
| Автор: Pavia 11.11.2010, 23:40 |
| Экскалупатор, Вам шашечки или ехать? Есть золотое правило. Проигрываешь в памяти выигрываешь в скорости. Проигрываешь в скорости выигрываешь в памяти. Можно ходить по дереву вначале искать Фамилии на А потом по Б и тд. Но тогда дерево вам придется перебирать очень много раз. Выводить вам куда надо? Я так думаю в список вот его представить массивом и отсортировать. Можно к примеру вывести в файл и отсортировать в файле. Но это делать лучше когда данных очень много. |
| Автор: baldina 12.11.2010, 09:54 | ||||||
Двоичное дерево поиска хранит значения упорядоченными по ключу Составление такого дерева имеет трудоемкость O(nlogn), как и сортировка, но требует больше памяти и в абсолютных значениях более трудоемко. Поэтому составлять второе дерево имеет смысл, если оно будет использоваться многократно, в т.ч. перестраиваться в случае вставки/удаления данных. Это то, что Pavia назвал постоянным ключом. С точки зрения современных БД оба дерева - индексы, причем первый - кластеризованный. А для однократного решения быстрее и проще выбрать необходимые данные (например, поместить в массив), а затем отсортировать:
"алгоритм с помощью которого можно сделать такой вывод" конечно можно разработать, но он не будет эффективным. нужна соответствующая задаче структура данных, поддерживающая множественные индексы. |
| Автор: Экскалупатор 12.11.2010, 14:47 |
| ясно. спс. |
