Всичко, което трябва да знаете за структурите на данните за дърветата

Дърветата са толкова красиви. Рисунка, която направих, когато бях малко момче.

Когато за първи път се научите да кодирате, обикновено е да научите масиви като „основна структура на данни“.

В крайна сметка ще научите и за хеш таблиците. Ако преследвате образователна степен по компютърни науки, трябва да вземете клас по структура на данните. Ще научите и за свързани списъци, опашки и стекове. Тези структури от данни се наричат ​​"линейни" структури от данни, защото всички те имат логическо начало и логичен край.

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

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

В тази статия ще научим:

  • Какво е дърво
  • Примери за дървета
  • Неговата терминология и как работи
  • Как да внедрите дървесни структури в код.

Нека започнем с това учебно пътуване. :)

дефиниция

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

Дърветата са добре известни като нелинейна структура на данни. Те не съхраняват данни по линеен начин. Те организират данни йерархично.

Нека се потопим в примери от реалния живот!

Какво имам предвид, когато казвам по йерархичен начин?

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

Моето родословно дърво

Горната рисунка е моето родословно дърво. Тосико, Акикадзу, Хитоми и Такеми са мои баби и дядовци.

Тошиаки и Джулиана са мои родители.

TK, Yuji, Bruno и Kaio са деца на моите родители (аз и моите братя).

Структурата на организацията е друг пример за йерархия.

Структурата на компанията е пример за йерархия

В HTML модела на обект на документ (DOM) работи като дърво.

Модел на обект на документ (DOM)

HTML маркерът съдържа други тагове. Имаме таг за глава и етикет за тяло. Тези тагове съдържат специфични елементи. Главният маркер има мета и заглавни маркери. Тегът на тялото има елементи, които се показват в потребителския интерфейс, например, h1, a, li и т.н.

Техническо определение

Дърво е съвкупност от образувания, наречени възли. Възлите са свързани чрез ръбове. Всеки възел съдържа стойност или данни и може да има или не може да има дъщерен възел.

Първият възел на дървото се нарича корен. Ако този корен възел е свързан с друг възел, тогава коренът е родителски възел и свързаният възел е дете.

Всички възли на дърво са свързани чрез връзки, наречени ръбове. Това е важна част от дърветата, защото управлява връзката между възлите.

Листата са последните възли на дърво. Те са възли без деца. Подобно на истинските дървета, имаме корен, клони и накрая листата.

Други важни понятия за разбиране са височината и дълбочината.

Височината на едно дърво е дължината на най-дългия път до листо.

Дълбочината на възел е дължината на пътя до неговия корен.

Обобщение на терминологията

  • Коренът е най-горният възел на дървото
  • Edge е връзката между два възла
  • Child е възел, който има родителски възел
  • Родител е възел, който има ръб на дочерния възел
  • Листът е възел, който няма дъщерен възел в дървото
  • Височината е дължината на най-дългия път до листо
  • Дълбочината е дължината на пътя до корена му

Двоични дървета

Сега ще обсъдим конкретен тип дърво. Ние го наричаме бинарно дърво.

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

Затова нека разгледаме пример за двоично дърво.

Нека кодираме двоично дърво

Първото нещо, което трябва да имаме предвид, когато внедряваме бинарно дърво, е, че то е съвкупност от възли. Всеки възел има три атрибута: стойност, left_child и right_child.

Как да реализираме обикновено бинарно дърво, което се инициализира с тези три свойства?

Нека да разгледаме

Ето го. Нашият клас на бинарни дървета.

Когато инстанцираме обект, ние предаваме стойността (данните на възела) като параметър. Погледнете левия и десния. И двете са настроени на None.

Защо?

Защото когато създаваме нашия възел, той няма деца. Просто имаме данни за възлите.

Нека го тестваме:

Това е.

Можем да предадем низа „a“ като стойност към нашия възел Binary Tree. Ако отпечатаме стойността, left_child и right_child, можем да видим стойностите.

Нека да преминем към частта за вмъкване. Какво трябва да направим тук?

Ще приложим метод за вмъкване на нов възел отдясно и отляво.

Ето правилата:

  • Ако текущият възел няма ляво дете, просто създаваме нов възел и го задаваме на лявото дете на текущия възел.
  • Ако има лявото дете, създаваме нов възел и го поставяме на мястото на текущото ляво дете. Разпределете този лев детев възел на лявото дете на новия възел.

Нека го извадим :)

Ето кода:

Отново, ако текущият възел няма ляво дете, просто създаваме нов възел и го задаваме на лявото дете на текущия възел. Или иначе създаваме нов възел и го поставяме на мястото на текущото ляво дете. Разпределете този лев детев възел на лявото дете на новия възел.

И правим същото, за да вмъкнем правилен детски възел.

Свършен. :)

Но не изцяло. Все още трябва да го тестваме.

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

За да обобщим илюстрацията на това дърво:

  • възел ще бъде коренът на нашето двоично дърво
  • лявото дете е b възел
  • дясното дете е c възел
  • b дясното дете е d node (b node няма ляво дете)
  • c лявото дете е e възел
  • c правилното дете е f възел
  • и e, и f възлите нямат деца

И така, ето кода за дървото:

Прави се вмъкване.

Сега трябва да помислим за обиколка на дърветата.

Тук имаме две опции: Дълбоко-първо търсене (DFS) и Търсене на първа ширина (BFS).

  • DFS “е алгоритъм за преминаване или търсене в структурата на данните на дървото. Човек започва в основата и проучва, доколкото е възможно, по протежение на всеки клон, преди да отстъпи назад. “- Уикипедия
  • BFS “е алгоритъм за преминаване или търсене в структурата на данните на дърветата. Той започва от корена на дървото и първо изследва съседните възли, преди да премине към съседите от следващото ниво. “- Wikipedia

Така че нека се потопим във всеки тип дървесен траверс.

Дълбоко първо търсене (DFS)

DFS изследва пътека чак до листо, преди да изтегли и проучи друг път. Нека да разгледаме пример с този тип преминаване.

Резултатът за този алгоритъм ще бъде 1–2–3–4–5–6–7.

Защо?

Нека го разградим

  1. Започнете от корен (1). Отпечатайте го.

2. Отидете до лявото дете (2). Отпечатайте го.

3. След това отидете на лявото дете (3). Отпечатайте го. (Този възел няма деца)

4. Обратно и отидете на правилното дете (4). Отпечатайте го. (Този възел няма деца)

5. Изтеглете обратно към коренния възел и отидете на правилното дете (5). Отпечатайте го.

6. Отидете до лявото дете (6). Отпечатайте го. (Този възел няма деца)

7. Обратно и отидете на правилното дете (7). Отпечатайте го. (Този възел няма деца)

8. Готово.

Когато отидем дълбоко в листата и назад, това се нарича DFS алгоритъм.

Сега, когато сме запознати с този алгоритъм за преминаване, ще обсъдим типове DFS: предварителна поръчка, поръчка и след поръчка.

Предварителна поръчка

Точно това направихме в горния пример.

  1. Отпечатайте стойността на възела.
  2. Отидете до лявото дете и го отпечатайте. Това е, ако и само ако има ляво дете.
  3. Отидете при правилното дете и го отпечатайте. Това е, ако и само ако има правилно дете.

В поръчка

Резултатът от алгоритъма за поръчка за този пример на дърво е 3–2–4–1–6–5–7.

Лявата първа, средната секунда и дясната последна.

Сега нека го кодираме

  1. Отидете до лявото дете и го отпечатайте. Това е, ако и само ако има ляво дете.
  2. Отпечатайте стойността на възела
  3. Отидете при правилното дете и го отпечатайте. Това е, ако и само ако има правилно дете.

Пост-поръчка

Резултатът от алгоритъма за поръчка за този пример за дърво е 3–4–2–6–7–5–1.

Лявата първа, дясната втора и средната последна.

Нека кодираме това.

  1. Отидете до лявото дете и го отпечатайте. Това е, ако и само ако има ляво дете.
  2. Отидете при правилното дете и го отпечатайте. Това е, ако и само ако има правилно дете.
  3. Отпечатайте стойността на възела

Първо търсене на ширина (BFS)

BFS алгоритъмът обхожда нивото на дървото по ниво и дълбочина по дълбочина.

Ето един пример, който помага за по-доброто обяснение на този алгоритъм:

Така че преминаваме ниво по ниво. В този пример резултатът е 1–2–5–3–4–6–7.

  • Ниво / Дълбочина 0: само възел със стойност 1
  • Ниво / Дълбочина 1: възли със стойности 2 и 5
  • Ниво / Дълбочина 2: възли със стойности 3, 4, 6 и 7

Сега нека го кодираме

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

Как работи?

Ето обяснението.

  1. Първо добавете коренния възел в опашката с метода put.
  2. Повторете, докато опашката не е празна.
  3. Вземете първия възел на опашката и след това отпечатайте неговата стойност.
  4. Добавете и левите, и десните деца в опашката (ако текущите възли имат деца).
  5. Свършен. Ние ще отпечатваме стойността на всеки възел, ниво по ниво, с нашия опашка.

Двоично дърво за търсене

„Двоично дърво за търсене понякога се нарича подредени или сортирани двоични дървета и запазва стойностите си в подреден ред, така че при търсене и други операции да се използва принципът на двоично търсене“ - Wikipedia

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

Ето разбивка на горната илюстрация:

  • A е обърнат. Под-дървото 7–5–8–6 трябва да бъде от дясната страна, а под-дърво 2–1–3 трябва да бъде отляво.
  • B е единствената правилна опция. Той удовлетворява свойството Binary Search Tree.
  • C има един проблем: възелът със стойността 4. Трябва да е от лявата страна на корена, защото е по-малък от 5.

Нека кодираме Двоично дърво за търсене!

Сега е време за кодиране!

Какво ще видим тук? Ще вмъкнем нови възли, ще търсим стойност, ще изтрием възли и баланса на дървото.

Да започваме.

Вмъкване: добавяне на нови възли към нашето дърво

Представете си, че имаме празно дърво и искаме да добавим нови възли със следните стойности в този ред: 50, 76, 21, 4, 32, 100, 64, 52.

Първото нещо, което трябва да знаем, е дали 50 е коренът на нашето дърво.

Вече можем да започнем да вмъкваме възел по възел.

  • 76 е по-голям от 50, затова поставете 76 от дясната страна.
  • 21 е по-малък от 50, така че поставете 21 от лявата страна.
  • 4 е по-малък от 50. Възел със стойност 50 има ляво дете 21. Тъй като 4 е по-малък от 21, поставете го от лявата страна на този възел.
  • 32 е по-малък от 50. Възел със стойност 50 има ляво дете 21. Тъй като 32 е по-голям от 21, поставете 32 от дясната страна на този възел.
  • 100 е по-голяма от 50. Възел със стойност 50 има дясно дете 76. Тъй като 100 е по-голям от 76, поставете 100 от дясната страна на този възел.
  • 64 е по-голяма от 50. Възел със стойност 50 има дясно дете 76. Тъй като 64 е по-малък от 76, поставете 64 от лявата страна на този възел.
  • 52 е по-голямо от 50. Възел със стойност 50 има дясно дете 76. Тъй като 52 е по-малък от 76, възел със стойност 76 има ляво дете 64. 52 е по-малък от 64, така че поставете 54 от лявата страна на този възел.

Забелязвате ли модел тук?

Нека го разградим

  1. По-голяма или по-малка е стойността на новия възел от текущия възел?
  2. Ако стойността на новия възел е по-голяма от текущия възел, отидете на дясното дърво. Ако текущият възел няма подходящо дете, го поставете там или иначе се върнете към стъпка №1.
  3. Ако стойността на новия възел е по-малка от текущата, отидете на лявото поддърво. Ако текущият възел няма ляво дете, го поставете там или иначе върнете назад към стъпка №1.
  4. Тук не обработвахме специални случаи. Когато стойността на нов възел е равна на текущата стойност на възела, използвайте правило номер 3. Помислете за поставяне на равни стойности в лявата част на поддървото.

Сега нека го кодираме

Изглежда много просто.

Мощната част на този алгоритъм е рекурсионната част, която е на линия 9 и ред 13. И двата реда код извикват метода insert_node и го използват съответно за левите и десните му деца. Редове 11 и 15 са тези, които правят вмъкването за всяко дете.

Нека търсим стойността на възела ... Или не ...

Алгоритъмът, който сега ще изградим, е свързан с извършване на търсене. За дадена стойност (цяло число) ще кажем дали нашето Двоично дърво за търсене има или няма тази стойност.

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

Нека да разгледаме един пример.

Представете си, че имаме това дърво.

Сега искаме да знаем дали имаме възел въз основа на стойност 52.

Нека го разградим

  1. Започваме с коренния възел като наш текущ възел. Дадената стойност по-малка ли е от текущата стойност на възела? Ако отговорът е да, тогава ще го търсим в лявото поддърво.
  2. Дадената стойност по-голяма ли е от текущата стойност на възела? Ако отговорът е да, тогава ще го търсим в дясното поддърво.
  3. Ако правилата №1 и # 2 са и фалшиви, можем да сравним текущата стойност на възела и дадената стойност, ако са равни. Ако сравнението се върне вярно, тогава можем да кажем: „Да! Дървото ни има дадената стойност “, в противен случай ние казваме:„ Не, не е. “

Сега нека го кодираме

Нека да отбележим кода:

  • Редове 8 и 9 попадат в правило №1.
  • Редове 10 и 11 попадат в правило №2.
  • Ред 13 попада под правило №3.

Как да го тестваме?

Нека създадем нашето Двоично дърво за търсене, като инициализираме коренния възел със стойността 15.

И сега ще вмъкнем много нови възли.

За всеки вмъкнат възел, ние ще тестваме дали методът find_node наистина работи.

Да, работи за тези зададени стойности! Нека тестваме стойност, която не съществува в нашето Двоично дърво за търсене.

О да.

Нашето търсене е направено.

Изтриване: премахване и организиране

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

  • Сценарий №1: Възел без деца (листов възел).

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

  • Сценарий №2: Възел само с едно дете (ляво или дясно дете).

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

  • Сценарий №3: Възел с две деца.

Когато възелът има 2 деца, трябва да намерим възела с минималната стойност, като се започне от правилното дете на възела. Ще поставим този възел с минимална стойност на мястото на възела, който искаме да премахнем.

Време е да кодирате

  1. Първо: Забележете стойността на параметрите и родителя. Искаме да открием, че нодетата има тази стойност, а родителят на възела е важен за премахването на възела.
  2. Второ: Забележете връщащата се стойност. Нашият алгоритъм ще върне булева стойност. Връща True, ако намери възела и го премахне. В противен случай ще се върне Фалшиво.
  3. От ред 2 до ред 9: Започваме да търсим възела, който има стойност, която търсим. Ако стойността е по-малка от текущата nodevalue, отиваме до лявото подребро, рекурсивно (ако и само ако текущият възел има ляво дете). Ако стойността е по-голяма, отидете на дясното подребро, рекурсивно.
  4. Ред 10: Започваме да мислим за алгоритъма за премахване.
  5. От ред 11 до ред 13: Ние покриваме възела без деца и това е лявото дете от неговия родител. Премахваме възела, като настройваме лявото дете на родителя на None.
  6. Редове 14 и 15: Ние покриваме възела без деца и това е правилното дете от неговия родител. Премахваме възела, като настройваме правилното дете на родителя на None.
  7. Метод на изчистване на възела: Ще покажа кода clear_node по-долу. Тя задава възлите ляво дете, дясното дете и стойността му на None.
  8. От ред 16 до ред 18: Ние покриваме възела само с едно дете (ляво дете) и това е лявото дете от неговия родител. Поставяме лявото дете на родителя на лявото дете на възела (единственото дете, което има).
  9. От ред 19 до ред 21: Ние покриваме възела само с едно дете (ляво дете) и то е правилното дете от неговия родител. Задаваме дясното дете на родителя на лявото дете на възела (единственото дете, което има).
  10. От ред 22 до ред 24: Ние покриваме възела само с едно дете (дясно дете) и то е лявото дете от неговия родител. Поставяме лявото дете на родителя към дясното дете на възела (единственото дете, което има).
  11. От ред 25 до ред 27: Ние покриваме възела само с едно дете (правилно дете) и то е правилното дете от неговия родител. Задаваме правилното дете на родителя на правилното дете на възела (единственото дете, което има).
  12. От ред 28 до ред 30: Покриваме възела както с леви, така и с десни деца. Получаваме възела с най-малката стойност (кодът е показан по-долу) и го задаваме на стойността на текущия възел. Завършете го, като премахнете най-малкия възел.
  13. Ред 32: Ако намерим възела, който търсим, той трябва да върне True. От ред 11 до ред 31 се занимаваме с този случай. Така че просто върнете True и това е всичко.
  • За да използвате метода clear_node: задайте стойност None на всичките три атрибута - (стойност, left_child и right_child)
  • За да използвате метода find_minimum_value: отидете надолу вляво. Ако не можем да намерим повече възли, намерихме най-малкия.

Сега нека го тестваме

Ще използваме това дърво, за да тестваме нашия алгоритъм на Remove_node.

Нека премахнем възела със стойност 8. Това е възел без дете.

Сега нека премахнем възела със стойност 17. Това е възел само с едно дете.

Накрая ще премахнем възел с две деца. Това е коренът на нашето дърво.

Тестовете вече са направени. :)

Това е всичко за сега!

Тук научихме много.

Поздравления за завършването на това плътно съдържание. Наистина е трудно да разберем концепцията, която не знаем. Но ти го направи. :)

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

Забавлявайте се, продължавайте да учите и кодирате.

Надявам се да ви е харесало това съдържание. Подкрепете моята работа по Ko-Fi

Моят Twitter & Github. ☺

Допълнителни ресурси

  • Въведение в структурата на данните за дърветата от mycodeschool
  • Дърво от Уикипедия
  • Как да не бъдете претъпкани от дървета от талантливия Вайдехи Джоши
  • Въведение в дърветата, лекция на професор Джонатан Коен
  • Въведение в дърветата, лекция на професор Дейвид Шмит
  • Въведение в дърветата, лекция на професор Виктор Адамчик
  • Дървета с Гейл Лаакман Макдауъл
  • Изпълнение и тестове на двоични дървета от TK
  • Курс на Coursera: Структури на данни от Калифорнийския университет, Сан Диего
  • Курс на Coursera: Структури на данните и ефективност от Калифорнийския университет, Сан Диего
  • Концепции и изпълнение на двоично дърво за търсене от Пол програмиране
  • Внедряване на бинарно дърво за търсене и тестове от TK
  • Обход на дърво от Wikipedia
  • Двоично дърво за търсене Премахване на алгоритъм на възела от GeeksforGeeks
  • Двоично дърво за търсене Премахване на алгоритъм на възел от Алголист
  • Учене на Python от нула до герой