Всем привет. Есть такая проблема.
у меня есть бинарное дерево, каждый узел содержит имя, фамилию, отчество и дату рождения, ключем является дата рождения. вопрос: как оптимально вывести данные из дерева в алфавитном порядке не позднее определенной даты.
если выводить в определенном порядке по дате рождения то все просто, читай по ключу и все. но тут надо именно в алфавитном порядке(к примеру по фамилии). у меня созрело решение собрать второе дерево используя как ключ фамилию(или массив, отсортированный по фамилии). но мне кажется это как то коряво. как решить эту проблему не прибегая к помощи массивов/деревьев с временными данными.
заранее спасибо.

Экскалупатор, 
Берешь дерево отсекаешь дату по ключу. Потом Сортируешь.
Второе предложение. 

Хорошее решение. Составить второй ключ. Только это ключ должен быть постоянным иначе в нем смысла нет.

эээ что то не совсем понял мысль. типа сортировать дерево по другому ключу? но это все равно что заново пересоздать все дерево, а мне его менять нельзя, оно должно оставаться отсортированным по дате.

и это тоже не совсем понял.



объясни по подробнее плиз.

Добавлено через 3 минуты и 39 секунд
подумал тут. можно же добавить дополнительные поля, для того что бы можно было создать из одних и тех же узлов два дерева, одно будет отсортировано по дате а второе по фамилии в алфавитном порядке.(или это и имелось ввиду под вторым ключем в предыдущем посте?).

Именно так. Правда выбор структуры я оставил за вами: хочешь дерево или список - это уже как вам угодно. 

Это сообщение отредактировал(а) Pavia - 10.11.2010, 21:38

Pavia, спасибо. неплохая идея. лови +. 
но может есть просто алгоритм с помощью которого можно сделать такой вывод? просто мне не хотелось бы усложнять структуру узлов дерева и создавать лишних массивов.

Экскалупатор, Вам шашечки или ехать?
Есть золотое правило. Проигрываешь в памяти выигрываешь в скорости. Проигрываешь в скорости выигрываешь в памяти.
Можно ходить по дереву вначале искать Фамилии на А потом по Б и тд. Но тогда дерево вам придется перебирать очень много раз.

Выводить вам куда надо? Я так думаю в список вот его представить массивом и отсортировать. Можно к примеру вывести в файл и отсортировать в файле. Но это делать лучше когда данных очень много.

Двоичное дерево поиска хранит значения упорядоченными по ключу
Составление такого дерева имеет трудоемкость O(nlogn), как и сортировка, но требует больше памяти и в абсолютных значениях более трудоемко.
Поэтому составлять второе дерево имеет смысл, если оно будет использоваться многократно, в т.ч. перестраиваться в случае вставки/удаления данных. Это то, что Pavia назвал постоянным ключом.
С точки зрения современных БД оба дерева - индексы, причем первый - кластеризованный.

А для однократного решения быстрее и проще выбрать необходимые данные (например, поместить в массив), а затем отсортировать:


"алгоритм с помощью которого можно сделать такой вывод" конечно можно разработать, но он не будет эффективным. нужна соответствующая задаче структура данных, поддерживающая множественные индексы.

ясно. спс.