[Homework] Advanced Tree Structures Part1 - Март 2016 - Софтуерен университет

djc_bg2015 923 Точки

[Homework] Advanced Tree Structures Part1 - Март 2016

Здравейте колеги,

споделям моите решения на двете задачки от домашното.

https://github.com/vdonchev/AdvancedTreeStructures-Homework

Задача 2: Range метода го направих в екстеншън метод, за да пробвам дали работи , и в крайна сметка реших да го оставя така.

Задача 3: Интересното е по задача 3, Не знам до каква степен съм направил индексатора оптимално бърз, и ще се радвам, някой да споедели мнение.

Първо, срещнах сериозно затруднение да следя правлния каунт на нодовете затова при добавяне на нов нод първо ретерейсвам до корена и увеличавам на всеки нод по пътя каунт ++, и чак след това на ново тръгвам от инсертания нод да проверявам баланс факторите...

относно намирането на самия индекс, позлвах алгоритъма описан в стековърлоу (линка от домашното)

1 - Проверявам дали индекса е в рамките на броя елементи в дървото

2 - Започвам от корена и проверявам няколко неща:

2.1 Ако Count на лявото под дърво е равно на търсения индекс, връщам нода като резултат

2.2 Ако Count на лявото под дърво е >= от търсения индекс, повтарям търсенето с лявото под дърво

2.3 Ако Count на лявото под дърво е < индекса, повтарям търсенето с дясното под дърво и намалям индекса с Count на лявото + 1

Тествах няколк оразлични сценария, и изглежда че индексатора работи. Написах и 3 юнит теста с данните от задачата.

Ако някой е готов нека сподели решение, интересно ми е да видя.

Тагове:

15/03/2016 11:40:43 Структури от данни и алгоритми

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

yuletodim 37 Точки

Здравей!

За индексът направих следното, много е просто и засега не ми дава грешка:

I. В метод InserInternal преди retrace викам метод -> SetElementsIndex(newNode);

II. private void SetElementsIndex(Node<T> newNode)
{
if (newNode.IsLeftChild) -> newNode.Index = newNode.Parent.Index;

if (newNode.IsRightChild) -> newNode.Index = newNode.Parent.Index + 1;

this.ModifyIndex(this.root, newNode);
}

III. С един DFS на всички > от newNode увеличавам индексът с 1

if(currentNode.Value.CompareTo(newNode.Value) > 0) -> currentNode.Index += 1;

В крайна сметка никъде не обвързвам retrace с индексирането. не знам дали е по-бързо, но като код е много просто.

Range го направих с вече предоставения ни ForeachDfs(Action<T> action) и ламбда израз -> 1 ред

17/03/2016 16:31:21

djc_bg2015 923 Точки

Ами да, пресмятането на броя деца на нодовете изглежда ок, поне аз не виждам проблем.

Относно ползването на foreach който е в класа, като орежеш резултатите с ламбда израз, спестяваш ли обхожданията в ляво и дясно които са извън търсения рейндж?

Поздрави!

17/03/2016 18:43:58

yuletodim 37 Точки

Не :)

17/03/2016 21:42:55

a_rusenov 1103 Точки

Кратко, точно и ясно, но бавно. :) Вече добавянето ти е O(n) при всички случаи, понеже DFS-ът ти е пълен. Дори да го оптимизираш, worst case пак е O(n). И в крайна сметка нищо не печелиш, търсенето по индекс при всички случаи е O(log n). Докато алгоритъма с Count-a (както е при @djc_bg2015), ти гарантира O(log n) и при търсене, и при добавяне.

PS: Вчера решавахме тази задача и видео е качено.

18/03/2016 16:46:56 18/03/2016 16:53:42

yuletodim 37 Точки

Сега го видях. Благодаря!

18/03/2016 17:09:25

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