Подскажите пожалуйста ссылки на литературу по 2-3 деревьям? (интересует литература, а не исходники)
пока понял, что 2-3 деревья обычно реализуются на основе B-деревьев, также то что АА-деревья являются изоморфными для 2-3 деревьев, означает ли это что АА-деревья можно использовать для построения 2-3? какой из методов реализации 2-3 деревьев проще?
p.s. в гугл ходил, гугл молчит
23 февраля 2010 в 15:00
А зачем её сносить? ИМХО, тема интересна и полезна.
23 февраля 2010 в 15:00
ну во многих группах принято сносить темы чтобы не мусорить…
оставлю…
23 февраля 2010 в 14:05
спасибо большое за помощь, еще уточню у преподавателя возможные реализации…
нашел получше визуализатор многих типов деревьев если кому нужно: //people.ksp.sk/~kuko/bak/index.html
p.s. тему снесу через полчаса, если никто ничего не добавит)
23 февраля 2010 в 14:02
Для лабораторной, я бы сказал, что нет – не поймут. От Вас ожидают две различных реализации узла, а не надстройку над бинарным деревом.
Хотя картинка занятная, но это, в первую очередь, все-таки бинарное дерево.
23 февраля 2010 в 14:00
спасибо большое, стало сразу понятнее, но отсюда возник еще вопрос:
"Искусство программирования. 3 том" Кнут:
>>Р. Байер (R. Bayer) [Proc. ACM-SIGFIDET Workshop (1971), 219-235] предложил интересное представление 2-3-деревьев в виде бинарных деревьев. Взгляните на рис. 28, на котором показано такое представление дерева, изображенного на рис. 26. Один бит каждого узла используется для того, чтобы отличать "горизонтальные" правые ссылки RLINK от "вертикальных" Заметьте, что ключи в таком дереве расположены, как и в бинарном дереве поиска, в симметричном порядке слева направо. Оказывается, что при вставке нового ключа в деревья такого типа необ¬ходимо выполнить те же преобразования, что и при вставке в бинарное дерево, а именно — однократные и двукратные повороты (хотя в этом случае требуется только одна версия каждого поворота без отражений относительно вертикальной оси, необходимых для алгоритмов А и С).
вот картинка:
//s004.radikal.ru/i207/1002/89/1eadba321258.bmp
а теперь вопрос: допустима ли реализация 2-3 дерева в таком виде?
23 февраля 2010 в 13:05
является ли АА-дерево 2-3 деревом?
Нет.
Литература: //www.cs.ucr.edu/cs14/cs14_06win/slides/2-3_tre...
23 февраля 2010 в 13:05
Пример: //www.cosc.canterbury.ac.nz/mukundan/dsal/TwoTh...
Тыкать в кнопочки поочередно.
23 февраля 2010 в 13:03
Нам просто лабу задали, формулировка звучит так:
Цель работы: изучение построения 2-3 деревьев. Оценка их быстродействия по сравнению с двоичными и AVL-деревьями.
…
и далее не сказано каким образом строить это дерево…
Почитал Кнута и Вирта у них указано, что иногда удобнее представлять 2-3 дерево в виде двоичного с доп флагом указания лежит ли узел по вертикали или горизонтали. И тогда балансировка в дереве сводится к поворотам.
У Арне Андерсона описано, что АА деревья проигрывают по скорости немного B-деревьям, однако тесты в интернете показывают, что B-деревья медленнее немного, чем АА.
я хочу получить ответ на вопрос является ли АА-дерево 2-3 деревом? вика говорит только, что они изоморфны…
p.s. подкиньте еще пожалуйста литературы по построению настоящих 2-3 деревьев (B-деревьев степени 3) ибо гугл codesearch показал наличие многих различных вариантов и представлений…
23 февраля 2010 в 13:02
мужчина в своей жизни долженвыратить сына, построить дом и посадить дерево.
23 февраля 2010 в 12:04
Для начала лучше ответить себе на вопрос, для чего ты собираешься использовать 2-3 деревья. Если они не самоцель, я бы просто использовал AA-дерево.
23 февраля 2010 в 12:01
о_О