Loading...
djc_bg2015 avatar 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 юнит теста с данните от задачата.

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

yuletodim avatar 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 ред

 

 

1
djc_bg2015 avatar djc_bg2015 923 Точки

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

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

Поздрави! 

1
yuletodim avatar yuletodim 37 Точки

Не :)

0
a_rusenov avatar a_rusenov 1103 Точки

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

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

3
18/03/2016 16:53:42
yuletodim avatar yuletodim 37 Точки

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

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