Научете за дърветата, полезна и широко използвана структура от данни, използвайки Python

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

Съдържание

1. Introduction
2. Terminology
3. Traversies
4. Implementation
5. Conclusion


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



Въведение

Дървото е нелинейна йерархична структура от данни, която се състои от възли и ръбове като графика. Голямата разлика с графиките е, че дърветата не съдържат кръгове. Дървото се състои от набор от възли, свързани един с друг, създавайки обратно дърво (коренът отгоре и листата отдолу). Дърветата позволяват по-бърз и лесен достъп до данните в сравнение с други линейни структури от данни като масиви, свързани списъци и т.н. Дървото има следната форма:

Като цяло има три типа възли:

  • Коренът: Най-горният възел на дървото (червен възел)
  • Интервални възли: Възли, които имат родителски възел и поне дъщерен възел (сини възли)
  • Листови възли: Възлите, които нямат дете (зелени възли)

Терминология

Имайки основна интуиция за дървовидната структура на данните, нека да разгледаме малко терминология за дърветата.

  • Възел: Възелът (връх) като в графиките е обект, който съдържа данни.
  • Edge: Връзка между два възела.
  • Родителски възел: Всеки възел на дървото (с изключение на корена) има родителски възел, който е предшественик на възела.
  • Дъщерен възел: Възелът, който е непосредствен наследник на възела, се нарича дъщерен възел.
  • Братя и сестри: Възли, които имат един и същ родител.
  • Поддърво: Всяко подмножество на дърво.

  • Степен на възела: Общият брой разклонения (деца) на възел.
  • Степен на дървото: максималната степен сред всички възли на дървото.
  • Дълбочина на възел: Броят на ръбовете от корена до текущия възел.
  • Височина на възел: Най-дългият път (брой ръбове) от текущия възел до лист.
  • Височина на дърво: Височината на основния възел. Най-дългият път от корена до листа.
  • Ниво на възел: Броят на ръбовете от корена до текущия възел. Коренът има ниво 0.
  • Път: Последователността от възли от начален възел до целеви възел.
  • Нулево дърво: Дърво без възли.

  • Пълно двоично дърво: Двоично дърво, в което всеки родителски възел има или нула, или две деца.
  • Пълно двоично дърво: Двоично дърво, в което всички нива (освен евентуално от последното) имат максималния брой възли. За последното ниво всички възли на листа трябва да се наклонят наляво.

Има няколковида дървета, като най-известните от тях са следните:

  • Общо дърво: Дърво, в което всеки възел има от нула до безкраен брой деца.
  • Двоично дърво: Дърво, в което всеки възел има най-много две деца (0, 1 или две)
  • Балансирано дърво: Дървета, при които разликата между лявото и дясното поддърво е най-много 1.
  • Двоично дърво за търсене: Това е двоично дърво със свойството, че във всеки възел i лявото дете на този възел има стойност, по-малка или равна на възел i, а дясното дете има стойност, по-голяма от възел i.
  • Групи: Купчината е пълно двоично дърво, в което всеки родителски възел има по-голяма или равна стойност на своите деца (Макс. куп) или всеки родителски възел има по-малка или равна стойност на своите деца (Минимална купчина ).

В този урок ще говорим за двоични дървета.

Обхождания

Една от най-честите операции в едно дърво е обхождането. С термина обхождане на дърво имаме предвид да посетите всеки възел на дървото с конкретен предварително дефиниран ред. Тъй като дървото е йерархична структура от данни, има няколко начина за преминаване през дърво. По-конкретно, има три вида преминаване:

  • Предварителна поръчка: Последователността на посещението следва модела Корен, ляв възел, десен възел. Да предположим например, че имаме следното двоично дърво:

Преминаването на предварителната поръчкае A — B — D — E — C — F

  • По ред: Последователността на посещението следва модела ляв възел, корен и десен възел. Да предположим например, че имаме следното двоично дърво:

Обхождането вреде D— B — E— A— C — F

  • Поръчка: Последователността на посещението следва модела Ляв възел, Десен възел, Корен. Да предположим например, че имаме следното двоично дърво:

Следпреминаването на поръчкае D — E— B— F— C — A

Внедряване

Имайки интуиция за дърветата и техните свойства, време е да кодирате с помощта на Python. Както беше споменато по-рано, дървото се състои от набор от възли. Така че първата ни работа е да създадем клас с име Node, който представлява всеки възел на дървото. Този клас ще има три атрибута. Атрибутът стойностсъответства на данните на възела, докато другите два атрибута left_childи right_chidсе наричат ​​ляво и дясно дете на възела съответно. Освен това нашият клас ще бъде оборудван с метод за добавяне на деца към възела.

След това създаваме класа MyTreeкойто моделира дървовидната структура на данните. Този клас приема основния възел като параметър. Освен това, той е оборудван с необходимите методи (предварителна поръчка, подредба и последваща поръчка) за преминаване.

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

Забелязваме, че получаваме същите резултати като примерите с писалка и хартия по-горе.

Можете да разгледате и изтеглите целия код тук.

Заключение

В тази статия имахме възможността да говорим за дървета, една от най-фундаменталните структури от данни в компютърните науки. Дърветата се използват в различни области, в които данните имат естествена форма на йерархия. Освен това, няколко алгоритми за търсене като Binary Search Trees и алгоритми за сортиране като Heap Sort използват дървета. Ще разгледаме и двете неща в следващите статии. Благодаря за четенето.

Ако обичате да четете статиите ми, последвайте ме в LinkedIn и Twitter. Освен това можете да се регистрирате, за да станете член на Medium. Като член имате неограничен достъп до хиляди статии. Членството струва 5$ на месец. Можете да използвате следната връзка, за да станете среден член.



Присъединете се към Medium с моята препоръчана връзка - Андреас Суларидис
Като член на Medium, част от вашия членски внос отива на писатели, които четете, и получавате пълен достъп до всяка история… medium.com



Повече съдържание в PlainEnglish.io. Регистрирайте се за нашия безплатен седмичен бюлетин. Следвайте ни в Twitter и LinkedIn. Вижте нашия Community Discord и се присъединете към нашия Talent Collective.