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

[Homework] Advanced Tree Structures

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

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

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

Успехи!

Наков

pafkuneca avatar pafkuneca 14 Точки

Искам да попитам имате ли добър източник за интервални дървета, не можах да намеря добра статия?Благодаря!

0
pafkuneca avatar pafkuneca 14 Точки

Мерси

0
mihayloff14 avatar mihayloff14 824 Точки

От тази статия не ми става ясно как точно става insert-ването в интервално дърво.

0
pafkuneca avatar pafkuneca 14 Точки

Здравейте, открих грешка в имплементацията на АА дърво в презентацията.Грешка е, че функцията за триене, поне при мен не работи.При мен го fixnah с една проверка ако ключа е по - голям пускам същата функция за Node.Left, ако е по - малък пускам същата функция за Node.Right и ако е ключа е == Node.Key чак тогава присвоявам node на deleted и т.н.Ако и други са срещнали този проблем, fix е този :))

0
27/08/2015 13:56:29
martin_n_marinov avatar martin_n_marinov 26 Точки

До колкото разбирам, идеята на интервалното дърво е да подържа някаква колекция от интервали и да може да намира всички интервали които пресичат даден интервал. Примерно някакъв такъв интерфейс :

public void Add(Interval interval)

public void Remove(Interval interval)

public bool IntersectsTheIntervalSet(Interval interval, IntersectType option = IntersectType.Inclusive)

public IEnumerable<Interval> GetIntersects(Interval interval, IntersectType option = IntersectType.Inclusive)

IntersectType е енумерация за това дали интервала е [x , y] или (x, y).

Ако ползваме директно някоя от структорите на .NET нещата стават прекалено лесни и не съм сигурен дали това се има предвид :

Tree Code.

Interval code.

Колкото статии прочетох по въпроса толкова различни мнения за това как трябва да се имплементира, някои друг да има проблем със задачата ?

0
pafkuneca avatar pafkuneca 14 Точки

Как става с друга структура?Моята идея е да ползваме АА дървото от предната задача, иначе не ми хрумва как ще се пазят нодовете ако ги бутаме в речник, понеже имат свойство, че нодеа валуе е MAX(node.left.value, node.right.value), ако нямат max от интервалните пропъртита.

0
MartinDachev avatar MartinDachev 30 Точки

Прекалено лесно изглежда, но всъщност ти обикаляш абсолютно всички интервали, а идеята е да ги изкараш без да обикаляш всичко.

0
martin_n_marinov avatar martin_n_marinov 26 Точки

Не ги обикалям всичките ( само така изглежда ). Обикалям ги до момента в които (item.Low > interval.High) всички останали ги прескачам и поняже са в сортирано по Low дърво обикалям само под-дървото в което има шанс да се намира интервала. Само в най-лошия случай минавам през всички, но няма алгоритъм който да не ги обикаля всички ако всички влизат. Другата функция обаче IntersectsTheIntervalSet работи по-бавно ако търся висок интервал, а в дървото има много малки или изобщо не съществува.

Иначе съм съгласен, че с АА дървото може да се направи и вероятно така ще го пренапиша, но нали Наков казва да ползваме SortedDictionary<K,V>(red-black tree) и се чудя как да стане.

0
ttitto avatar ttitto 1153 Точки

Аз съм още на AA дървото. Гледам примерната имплементация и не мога да схвана какъв е този node сентинел?

0
dim4o avatar dim4o 288 Точки

Според мен sentinel е да пази за случаите, когато имаме връзка на нода към null. Иначе node.right.right.level например още на първия опит щеше да изгърми с NullReferenceException. Като цяло тази имплементация на AA дърво хич не ме кефи, въпреки че изглежда сравнително проста и изчистена. Смятам да преправя имплементацията на OrderedSet от предните домашни като добавя балансиране.

2
MartinDachev avatar MartinDachev 30 Точки

Sentinel node - това е node за референции към празни ляв или десен node. Още някъде може да си го виждал като NIL. Аз мисля, че не е нужен да се използва в АА дървото, аз не го използвам - където няма референция си е NULL. Този node се използва като traversal path terminator. Знаеш, че стигнеш ли до него, трябва да спреш, защото този node е празен. В конкретната имплементация не виждам смисъл да се използва, но сигурно има. За да имплементираш дървото може да гледаш псевдокода в Уикипедия, и там където проверяват дали node е NIL, ти да си проверяваш дали е NULL. Пиши ако нещо още е неясно, щото наистина тоя sentinel node е объркващ :D.

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