[Homework] Advanced Tree Structures

Във форума е въведено ограничение, което позволява на потребителите единствено да разглеждат публикуваните въпроси.

nakov SoftUni Team Trainer 5294 Точки

[Homework] Advanced Tree Structures

Колеги, качих ви домашнто за темата Advanced Tree Structures.

Дал съм ви 3 задачи:

Имплементация на AA дърво - има псевдокод в Уикипедия + демо показвано в клас
Имплементация на интервално дърво - помислете дали не може да ползвате вътрешно други балансирани дървета, например подредени по старт на интервал или край на интерал, или комбинация от няколко такива.
Имплементация на Фибоначиева пирамида - има псевдокод в книгата Introduction to Algorithms (глава 20) + подробни обяснения с картинки как точно работи тази структура.

Успехи!

Наков

Тагове:

21/08/2015 19:45:03 Структури от данни и алгоритми

Виж всички отговори

MartinDachev 30 Точки

Ето тази страница може да помогне за имплементацията на АА дърво - ~~http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_andersson.aspx~~

На C++ е, но мисля че ще си го преведете. Най-вече го давам за изтриването на елемент, защото е същото като изтриването на елемент в нормално Binary Search Tree, само че има и проверка за ребалансиране - според мен този начин е много по-лесен от дадения в Уикипедия :). Аз го използвам, като давам всички node-ове по референции - тоест с ref.

Вече не го използвам, оказа се грешен кода...

Наистина ще се радвам, ако някой ми даде визуализация на АА дърво или някакви тестове, че е трудно да тествам моето. [Блягодаря на mihayloff14, с неговите тестове си поправих дървото]

П.С. Ето го моето АА дърво - ~~http://pastebin.com/kdiAUQE6~~ [старата имплементация с бъгове при триене, на долния ред е новата]

http://pastebin.com/bHEpb2Jk - Досега всички тестове, които съм му хвърлил, ги е минало :). Ако някой открие грешка казвайте...

29/08/2015 17:13:29 30/08/2015 14:45:03

mihayloff14 824 Точки

http://goose.ycp.edu/~dhovemey/fall2013/cs350/lectures/AATrees.pdf

ето тук към края има примери с insertion и deletion стъпка по стъпка. Може да ти е полезно за тестване.

29/08/2015 20:29:28

MartinDachev 30 Точки

Благодаря, с тези тестове си поправих грешките в дървото :))))))

30/08/2015 14:45:32

Виж всички отговори