Как да не се препъвам от дървета

Обърнете това дърво с главата надолу!

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

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

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

Отглеждайте какъв вид клони искате!

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

Линейни структури от данни в природата

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

В нелинейните структури от данни данните всъщност не следват подредба - поне не е очевидна цифрова, като например с масиви или свързани списъци. И тъй като не е задължително данните да бъдат подредени в определен ред, е лесно (и всъщност е доста често срещано) да се пресече нелинейна структура на данни по не последователен начин.

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

Дърветата - като свързани списъци - са съставени от възли и връзки.

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

Идентифициране на части от структурата на данните за дърво

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

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

Ако тези термини изобщо се чувстват непосилни, ми е полезно да мисля за структури от данни на дърво като родословно дърво или дори корпоративна стълбица. Данните са винаги йерархични. Ще имате някой (корен възел) в горната част, който да се делегира на някои други възли (родителски възли), които могат или могат да имат някой друг да им докладва (дъщерни възли). Или имате огромно семейство, с родителски възли, детски възли, всички водещи обратно към коренния възел на предците.

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

Говорете вашата (дърво) истина

Без значение как изглежда едно дърво, колко клони или листа има или колко голямо расте, има някои универсални „дървени истини“, които считат себе си за самостоятелни.

Намирам, че те са много по-лесни за разбиране, когато ги визуализираме, така че тук ще се облегнем на някои примери. Нека разгледаме това дърво, което имаме по-долу. Той има общо 10 възли, включително коренния възел.

Дървесни истини: дървото винаги ще има една по-малка връзка от общия му брой възли

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

Ако дървото има n възли, то винаги ще има един по-малък брой ръбове (n-1).

И ако погледнем дървото, започва да става ясно защо това е така. Коренният възел е възел, който никога не може да има родители. Следователно, никога не може да има нещо, което го препраща. Ако всеки възел трябва да има един друг възел, препращащ към него чрез връзка / ръб (с изключение на коренния възел), тогава винаги можем да сме сигурни, че нашето дърво ще има n-1 връзки, когато n е общият брой възли в дървото. Колко готино (и мощно!) Е, че можем да узнаем тази информация толкова лесно, без да се налага да обикаляме дървото ?!

Но изчакайте - ето още една истина, която е възможно дори по-готина: дърветата всъщност съдържат дървета в тях!

Дървесни истини: дърветата са рекурсивни структури от данни

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

Но все още няма да попаднем в обиколка на дърветата. Вместо това ще разгледаме нещо, което е по-важно да разберем първо: различните начини, по които можем да класифицираме дърветата си, което ще е полезно по пътя.

Колко висок е дървото ви?

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

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

Един прост начин да се мисли за дълбочината на възела е чрез отговор на въпроса: колко далеч е възелът от корена на дървото?

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

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

Дълбочината и височината на възел върху структурата на данните за дърво

Сега, когато знаем как работи дълбочината, второто свойство е малко по-лесно. Височината на възел може да бъде опростена, като се зададе въпросът: колко далеч е този възел от най-отдалеченото му листо? (Запомнете: ние обръщаме дърветата с главата надолу в дивия свят на компютрите, което е причината височината да се определя по този начин!)

Така че, можем да намерим височината на възела, като намерим най-отдалеченото му детско листо и преброим пътя на връзките, които са необходими за достигането му. В примера височината на оранжевия възел е 3, защото най-отдалечените му детеви листа (всъщност има три от тях!) Са на три връзки от оранжевия възел. Бонус точки, ако разберете каква е дълбочината на оранжевия възел!

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

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

Балансирани дървета срещу небалансирани дървета

Счита се, че едно дърво е балансирано, ако някой от двата подреждане не се различава по височина с повече от едно ниво. Ако обаче две подребристи братя се различават значително по височина (и имат повече от едно ниво на дълбочина на разликата), дървото е небалансирано.

Балансираните дървета се появяват, когато говорим за операции с дървета, и по-специално за преминаване. Идеята зад това е, че ако успеем да пресечем дърво и да намалим половината от броя на операциите, ще имаме по-добре работеща структура на данните. Въпреки това, при небалансирано дърво това определено не е така, тъй като едно поддърво може да бъде значително по-голямо от поддървото на неговия близък. Много от проблемите с оперативната ефективност, които балансираните дървета решават, всъщност се наричат ​​двоични дървета - но много повече за следващата седмица!

Непокриващи корени на дърветата

За да оценим истински силата на едно дърво, трябва да ги разгледаме в контекста на тяхното приложение. С други думи: вероятно не са толкова готини, докато не ги видите в природата!

Един прост пример се намира в обектно ориентираните езици: основният обект е коренният възел, докато класовете, които наследяват от него, са деца от основния клас. Това има повече смисъл, докато мислите за това; фактът, че често се нарича „йерархия на класовете“, се поддава добре на структурата на данните на йерархичното дърво.

Най-очевидната (която може би не е била очевидна досега!) Е файловата структура на проекта - или дори файловата система на вашия компютър! Ако се замислим, всички важни парчета вече са налице: коренова директория, с дъщерни възли, които биха могли да бъдат собствени поддиректории, или листа от дървото, които завършват само с обикновен файл. Всичко това наистина е просто йерархична структура на данните за дърво!

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

ресурси

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

  1. Структури на данните: Въведение в дърветата, mycodeschool
  2. Структури на данни: Дървета, HackerRank
  3. Дървета, професор Джонатан Коен
  4. Структури на данните за дърветата, професор Дейвид Шмид
  5. Балансиращи дървета, професор Р. Клейтън