2-3-4 деревья

Модератор: Absurd

Ответить
michael
Сообщения: 116
Зарегистрирован: 15 июл 2004, 12:06
Откуда: ISRAEL (ранее - из Литвы)
Контактная информация:

2-3-4 деревья

Сообщение michael » 02 дек 2004, 00:35

если допустить что даные содержащиеся в узлах это целые числа, каков будет НЕ РЕКУРСИВНЫЙ алгоритм распечатывения оных чисел по порядку возвростания?

Спасибо..

Код: Выделить всё

class Node
{
private static final int ORDER = 4;
private int numItems;
private Node parent;
private Node childArray[] = new Node[ORDER];
private DataItem itemArray[] = new DataItem[ORDER-1];
}

Absurd
Сообщения: 1213
Зарегистрирован: 26 фев 2004, 13:24
Откуда: Pietari, Venäjä
Контактная информация:

Сообщение Absurd » 06 дек 2004, 16:06

Почитай Кнута (том 1)...
Там был изящный алгоритм прошитых деревьев, который сводится к тому, что через все узлы по возрастанию тянется нить. Соответственно, чтобы пройти дерево, надо сделать один цикл вдоль всей нити.
Но нить надо поддерживать, и поэтому процедуры вставки и удаления узлов там несколько сложнее.
2B OR NOT(2B) = FF

michael
Сообщения: 116
Зарегистрирован: 15 июл 2004, 12:06
Откуда: ISRAEL (ранее - из Литвы)
Контактная информация:

Сообщение michael » 06 дек 2004, 21:46

а как книга то называется полностью?

Absurd
Сообщения: 1213
Зарегистрирован: 26 фев 2004, 13:24
Откуда: Pietari, Venäjä
Контактная информация:

Сообщение Absurd » 07 дек 2004, 13:04

2B OR NOT(2B) = FF

Absurd
Сообщения: 1213
Зарегистрирован: 26 фев 2004, 13:24
Откуда: Pietari, Venäjä
Контактная информация:

Сообщение Absurd » 07 дек 2004, 13:32

Сорри, не заметил, что ты из Израиля и ссылки на озон тебе не нужны. Но как назвывается книжка, там в принципе ясно.
2B OR NOT(2B) = FF

michael
Сообщения: 116
Зарегистрирован: 15 июл 2004, 12:06
Откуда: ISRAEL (ранее - из Литвы)
Контактная информация:

Сообщение michael » 07 дек 2004, 16:00

Cпасибо. Но вот теоретический вопрос - возможно ли ВООБЩЕ пройтись по дереву не рекурсивно, не используя вспомагательную структуру?

Absurd
Сообщения: 1213
Зарегистрирован: 26 фев 2004, 13:24
Откуда: Pietari, Venäjä
Контактная информация:

Сообщение Absurd » 07 дек 2004, 19:59

Можно эмулировать стек =)
2B OR NOT(2B) = FF

michael
Сообщения: 116
Зарегистрирован: 15 июл 2004, 12:06
Откуда: ISRAEL (ранее - из Литвы)
Контактная информация:

Сообщение michael » 08 дек 2004, 19:22

НЕ подкинет ли кто код как выбрать корень из 2-3-4 дерево и при этом сохранить структуру 2-3-4

Ответить