Loading...
nakov avatar nakov SoftUni Team Trainer 5295 Точки

[Homework] Advanced Tree Structures

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

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

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

Успехи!

Наков

MartinDachev avatar 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​ - Досега всички тестове, които съм му хвърлил, ги е минало :). Ако някой открие грешка казвайте...

0
30/08/2015 14:45:03
mihayloff14 avatar mihayloff14 824 Точки

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

 

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

1
MartinDachev avatar MartinDachev 30 Точки

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

0
Можем ли да използваме бисквитки?
Ние използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Можете да се съгласите с всички или част от тях.
Назад
Функционални
Използваме бисквитки и подобни технологии, за да предоставим нашите услуги. Използваме „сесийни“ бисквитки, за да Ви идентифицираме временно. Те се пазят само по време на активната употреба на услугите ни. След излизане от приложението, затваряне на браузъра или мобилното устройство, данните се трият. Използваме бисквитки, за да предоставим опцията „Запомни Ме“, която Ви позволява да използвате нашите услуги без да предоставяте потребителско име и парола. Допълнително е възможно да използваме бисквитки за да съхраняваме различни малки настройки, като избор на езика, позиции на менюта и персонализирано съдържание. Използваме бисквитки и за измерване на маркетинговите ни усилия.
Рекламни
Използваме бисквитки, за да измерваме маркетинг ефективността ни, броене на посещения, както и за проследяването дали дадено електронно писмо е било отворено.