[Homework] Advanced Tree Structures

nakov SoftUni Team Trainer 5295 Точки

[Homework] Advanced Tree Structures

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

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

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

Успехи!

Наков

Тагове:

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

pafkuneca 14 Точки

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

26/08/2015 14:15:38

nakov SoftUni Team Trainer 5295 Точки

Тук са описани доста читаво интервалните дървета: http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-11-augmenting-data-structures-dynamic-order-statistics-interval-trees/lec11.pdf

Може да ползваш отдолу SortedDictionary<K,V> (red-black tree).

26/08/2015 14:49:29 26/08/2015 14:51:17

pafkuneca 14 Точки

Мерси

26/08/2015 15:44:49

mihayloff14 824 Точки

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

26/08/2015 16:35:17

Покажи всички коментари

pafkuneca 14 Точки

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

27/08/2015 13:54:13 27/08/2015 13:56:29

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.

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

27/08/2015 23:53:08

pafkuneca 14 Точки

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

28/08/2015 13:51:42

MartinDachev 30 Точки

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

28/08/2015 16:37:21

martin_n_marinov 26 Точки

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

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

28/08/2015 17:10:07

ttitto 1153 Точки

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

28/08/2015 09:44:20

krach 65 Точки

http://web.eecs.umich.edu/~sugih/courses/eecs281/f11/lectures/12-AAtrees+Treaps.pdf

28/08/2015 10:15:12

dim4o 288 Точки

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

28/08/2015 11:27:57

MartinDachev 30 Точки

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

28/08/2015 13:49:04

Покажи всички коментари

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