Глыбіня-першая ў параўнанні з шырынёй першага

Калі вы знайшлі час для вывучэння кода ў любой форме або форме, вы, верагодна, сутыкнуліся з структурамі дадзеных. Структуры дадзеных складаюцца з мноства магчымасцей для захоўвання, арганізацыі і кіравання дадзенымі. Некаторыя з найбольш папулярных - масівы, звязаныя спісы, стэкі, чэргі і бінарныя дрэвы пошуку. Дзеля гэтага артыкула мы спынімся на двух розных спосабах набліжэння да пераходу дрэва: глыбіня першага пошуку і пошук у шырыню.

Што такое дрэва?

Дрэва - гэта структура дадзеных, якая складаецца з вузлоў, якія ўтрымліваюць паказальнікі на іншыя вузлы. У адрозненне ад дрэў у рэальным жыцці (ці, магчыма, яны дзесьці існуюць), дрэва дадзеных перавернута. Па сутнасці, корань знаходзіцца ўверсе, а лісце - унізе.

Давайце разаб'ем схему.

Кожнае дрэва мае адзіны каранёвы вузел, які знаходзіцца на верхнім узроўні (у гэтым выпадку ўзровень 0). Затым мы бачым, што на наступным узроўні каранёвы вузел A мае паказальнікі на вузлы B і C. Акрамя таго, вузлы B і C маюць паказальнікі на вузел A. У гэтай сітуацыі вузел A з'яўляецца бацькоўскім вузлом, а вузлы B і C - яе дзеці. Акрамя таго, вузлы В і С лічацца роднымі братамі.

Вам можа быць цікава, ці магчыма ў вузле больш за 2 дзяцей. Адказ - так! Гэта канкрэтнае малюнак - двайковае дрэва, якое можа быць вызначана максімум двума даччынымі вузламі для кожнага з бацькоў.

Код дрэва

Адмова ад адказнасці: Я буду выкарыстоўваць Javascript для стварэння простага дрэва!

Па-першае, нам трэба стварыць клас вузла:

Калі мы ствараем клас вузла, мы перадаем яму значэнне альбо дадзеныя, якія становяцца ўласцівасцю дадзеных вузла. У нас таксама ёсць уласцівасці бацькоў і дзяцей, якія з'яўляюцца нулявым і пустым масівам адпаведна. У рэшце рэшт, уласцівасць бацькоўскага ўказання будзе ўказваць на бацькоў канкрэтнага вузла, а ўласцівасць дзяцей будзе ўказваць на дзяцей гэтага вузла.

Затым мы ствараем клас дрэва:

Клас дрэва змяшчае адно ўласцівасць, корань, які першапачаткова з'яўляецца нулявым. Дрэвы ўключаюць метады прататыпаў, такія як змяшчае (), устаўляць () і выдаляць (), але мы захаваем іх для дажджлівага дня!

Пошук!

І пошук у глыбіні і ў шырыню - гэта метады прататыпа класа дрэва, якія выкарыстоўваюцца для вызначэння таго, ці існуе ў дрэве пэўны вузел, які змяшчае пэўныя дадзеныя. На малюнку ніжэй паказаны дзве розныя працэдуры пошуку.

Глыбіня-першы падыход

Першы метад паглыблення пачынаецца з каранёвага вузла і рухаецца да самога левага вузла. Як толькі ён трапляе ў самы левы вузел, ён перамяшчаецца па дрэве да кораня, а потым да самага правага вузла. Калі ён трапляе ў вузел з дзецьмі, ён будзе праходзіць праз дзеці гэтага вузла злева направа і працягваць направа.

Парадак пошуку: [10, 4, 1, 9, 17, 12, 18]

Кодэкс

Для першага паглыблення значэнне ў якасці аргумента прымае значэнне, якое мы шукаем на дрэве. Паколькі мы хочам перайсці вузлы злева направа, мы ўсталёўваем корань як стэк, таму што мы хочам скарыстацца апошнім першым падыходам. Затым мы робім цыкл, які працягваецца да таго часу, пакуль стэк не ўтрымлівае элементаў. У рамках цыклу while мы выдаляем першы элемент у стэку альбо выклікаем метад масіва shift () і ўсталёўваем яго роўным вузлу. Мы параўноўваем дадзеныя вузла са значэннем аргумента, і калі яны супадаюць, функцыя вяртае ісціну. Калі гэта не так, ён дадае дзяцей вузла на пярэдняй частцы стэка альбо выклікае метад масіва unshift () і працягвае пошук новых дадзеных. Калі пэўнага значэння ў дрэве не існуе, функцыя вяртае false.

Першы падыход

Першы ў шырыню падыход пачынаецца з каранёвага вузла і праходзіць кожны наступны ўзровень для пошуку патрэбнага вузла. Аналагічна падыходу да першага паглыблення, вузлы счытваюцца злева направа на кожным узроўні.

Парадак пошуку: [10, 4, 17, 1, 9, 12, 18]

Кодэкс

Пошук па шырыні ў кодзе падобны на пошук па глыбіні. У якасці аргументу патрабуецца значэнне, якое можна знайсці. Розніца тут у тым, што замест таго, каб выкарыстоўваць стэк, мы хочам выкарыстаць чаргу, каб мець магчымасць зрабіць першы ў падыходзе. У той час як цыкл, падобна да першага пошуку па глыбіні, мы хочам выкарыстаць метад масіва shift () для выдалення першага элемента чаргі ў якасці вузла. Аднак, калі дадзеныя вузла не супадаюць з патрэбным значэннем, замест таго, каб адмяняць дзеці вузла, мы будзем выкарыстоўваць метад масіва push (), каб дадаць дзяцей у канец чаргі. Гэта дазваляе нам праверыць кожны ўзровень на ўзроўні, перш чым прайсці праз вузлы на наступным узроўні. У рэшце рэшт, як і пошук па глыбіні, калі значэнне не знойдзена, функцыя верне ілжывую.

Якія я выкарыстоўваю?

Хоць пошук і па глыбіні першага (DFS), і ў першы па шырыні (BFS) з'яўляецца законным падыходам і можа прыйсці да аднолькавых высноў, кожны з іх аддае перавагу пры пэўных абставінах. Аднак не заўсёды відавочна, які з іх больш эфектыўны.

Адмова ад адказнасці: Гэта агульныя рэкамендацыі! Вызначана не заўсёды самыя аптымальныя падыходы.

DFS: Звычайна пераважней, калі дрэва вельмі глыбокае і жаданыя значэнні або дадзеныя сустракаюцца нячаста.

BFS: звычайна пераважней на дробных дрэвах, якія не занадта шырокія. Таксама выкарыстоўваецца, калі вядома, што патрэбны вузел бліжэй да каранёвага ўзроўню.

Хоць пры выбары спосабу выкарыстоўваць агульныя перавагі, калі вы не ўпэўнены, лепш паспрабаваць абодва спосабу і паглядзець, які з іх больш эфектыўны.

Напрыклад, скажам, што вы карыстаецеся дрэва вышэй і шукаеце вузел, які змяшчае 8. Дрэва не такое глыбокае, каб вы маглі падумаць, што лепш выкарыстоўваць BFS. Аднак на самай справе было б больш эфектыўна выкарыстоўваць 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 змяняюцца ў залежнасці ад структуры дадзеных, але дзеля дрэў складанасць часу і прасторы будзе аднолькавай.

Дзякуем, што знайшлі час прачытаць гэты артыкул! Калі ў вас ёсць водгукі ці пытанні, дайце мне ведаць! Спадзяюся, у вас цудоўны дзень!