Дълбочина-първа срещу широчина-първо търсене

Ако сте отделили време да изучавате код под каквато и да е форма или форма, вероятно ще попаднете на структури от данни. Структурите на данните се състоят от множество възможности за съхраняване, организиране и манипулиране на данни. Някои от по-популярните включват масиви, свързани списъци, стекове, опашки и двоични дървета за търсене. За целта на тази статия ще се съсредоточим върху два различни начина да се приближим до обиколка на дървото: Дълбоко първо търсене и търсене на пръст.

Какво е дърво?

Дърво е структура от данни, състояща се от възли, които съдържат указатели към други възли. За разлика от дърветата в реалния живот (или може би те съществуват някъде), дървото с данни е с главата надолу. По същество коренът е в горната част, а листата са отдолу.

Нека разбием диаграмата.

Всяко дърво има един корен възел, който е на най-горното ниво (в този случай ниво 0). Тогава виждаме, че на следващото ниво коренният възел А има указатели към възли В и С. По същия начин възлите В и С имат указатели към възел А. В тази ситуация възел А е родителският възел, а възлите В и С са децата му. Освен това възлите В и С се считат за братя и сестри.

Може би се чудите дали е възможно възел да има повече от 2 деца. Отговорът е да! Това конкретно изобразяване е на двоично дърво, което може да се определи от максимум два възли за всеки родител.

Код на дървото

Отказ от отговорност: Ще използвам Javascript за създаване на обикновено дърво!

Първо, трябва да създадем клас възли:

Когато създаваме клас на възел, ние го предаваме стойност или данни, които се превръщат в свойство на данни на възела. Засега имаме и свойства родител и деца, които съответно са нула и празен масив. В крайна сметка свойството родител ще сочи към родителя на конкретния възел, а свойството деца ще насочи към децата на възела.

След това създаваме класа дърво:

Дървесният клас съдържа едно свойство, root, което първоначално е нулево. Дърветата включват методи на прототип, като съдържа (), вмъкване () и премахване (), но ние ще ги спасим за дъждовен ден!

Издирване!

Както дълбочинното търсене, така и първото търсене в ширина са методи на прототип от класа Tree, които се използват за определяне дали определен възел, съдържащ специфични данни, съществува в дърво. Изображението по-долу показва двете различни процедури за търсене.

Дълбоко-първи подход

Първият метод на дълбочина започва от коренния възел и се придвижва към най-левия възел. След като удари най-левия възел, той преминава нагоре към дървото обратно към корена и след това до най-дясния възел. Ако удари възел с деца, той ще премине през децата от този възел отляво надясно и след това ще продължи надясно.

Поръчка за търсене: [10, 4, 1, 9, 17, 12, 18]

код

Дълбокото търсене приема стойност като аргумент, която е стойността, която търсим в дървото. Тъй като искаме да прекосим възлите отляво надясно, ние задаваме корен като стек, защото искаме да вземем последен първи подход. След това извършваме цикъл, който продължава, докато стека съдържа елементи. В рамките на цикъл while премахваме първия елемент в стека или извикваме метода на масива shift () и го задаваме равно на възел. Сравняваме данните на този възел със стойността на аргумента и ако те съвпадат, функцията връща true. Ако това не е така, той добавя децата на възела в предната част на стека или извиква метода на мащабиране () и продължава да търси чрез новите данни. Ако конкретната стойност не съществува в дървото, функцията връща false.

Първи подход на ширина

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

Поръчка за търсене: [10, 4, 17, 1, 9, 12, 18]

код

Търсенето с първа ширина е подобно по код на първото на дълбочина търсене. Тя изисква стойност, за да бъде намерена като аргумент. Разликата тук е, че вместо да използваме стек, ние искаме да използваме опашка, за да можем да предприемем първи подход при първото излизане. В цикъл while, подобно на първо търсене по дълбочина, искаме да използваме метода на масива shift (), за да премахнем първия елемент от опашката като възел. Ако обаче данните на възела не са същите като желаната стойност, вместо да изместим децата на възела, ще използваме метода на масива push (), за да добавим децата в края на опашката. Това ни позволява да проверим всеки възел на ниво, преди да преминем през възлите на следващото ниво. И накрая, точно като първо търсене в дълбочина, ако стойността не бъде намерена, функцията ще върне невярно.

Кое да използвам?

Въпреки че както търсенето с дълбочина първо (DFS), така и с широта на първо място (BFS) са законни подходи и могат да стигнат до едни и същи изводи, всеки от тях е предпочитан при определени обстоятелства. Не често обаче е очевидно кой от тях е по-ефективен.

Отказ от отговорност: Това са общи насоки! Определено не винаги са най-оптималните подходи.

DFS: Като цяло се предпочита, когато дървото е много дълбоко и желаните стойности или данни се срещат рядко.

BFS: Като цяло предпочитан в плитки дървета, които не са твърде широки. Използва се също, ако е известно, че желаният възел е по-близо до нивото на корена.

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

Например, да кажем, че използвате дървото по-горе и търсите възела, съдържащ 8. Дървото не е толкова дълбоко, за да може да мислите, че би било по-добре да използвате BFS. Всъщност би било по-ефективно да използвате DFS.

Да сравним двата метода и кои възли са преминали:

DFS: 1, 2, 4, 8

BFS: 1, 2, 3, 4, 5, 6, 7, 8

Вече можем да видим, че първо търсене в ширина преминава през повече възли и следователно се нуждае от достъп до повече памет.

Освен това, след като намерим възел 8, стека DFS ще бъде [8, 9, 5, 3], докато опашката за BFS ще бъде [8, 9, 10, 11, 13, 14]. Опашката за BFS съдържа още 2 възли, които в този пример изглежда не се равняват на много, но по отношение на паметта, тя все още използва по-голямо количество. Следователно, в тази конкретна ситуация, DFS би бил по-ефективен от BFS.

Въпреки че този пример е прост и лесен, в ситуации, когато дърветата са по-дълбоки и широки, определено е много по-трудно да се определи кое е по-оптимално. Най-добрият начин да диктувате по-добрия метод е да опитате и двете.

Сложност

Времето и пространството са сложни както за DFS, така и за BFS. Тъй като говорим за обиколка на дървото, за да определим дали стойност или данни съществуват вътре в дървото, трябва да посетим всеки възел. Посещаването на всеки възел еднократно означава, че времевата сложност както за DFS, така и за BFS е O (n) или линейна. Ако мислим за дърветата като подредени масиви, ще трябва само да прегледаме един път, за да определим дали дадена стойност съответства на стойността, която търсим или не. По същия начин, по отношение на сложността на пространството, DFS е O (h), а BFS е O (w). За DFS „h“ означава височина, тъй като колко място ще заеме функцията зависи от това колко възли са дълбоки в дървото. По същия начин при BFS 'w' означава ширина, тъй като пространството зависи от това колко е широко дървото. Разбира се, тези големи O обозначения се променят в зависимост от структурата на данните, но за дърветата, сложността на времето и пространството ще бъде същата.

Благодарим ви, че отделихте време да прочетете тази статия! Ако имате отзиви или въпроси, уведомете ме! Надявам се, че имате страхотен ден!