Въведение в дърветата в програмирането: кислородът на ефективното кодиране

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

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

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

И така, какво всъщност е структурата на данните?

Според Уикипедия:

Структурата на данните е формат за организация на данни и съхранение, който позволява ефективен достъп и модификация“

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

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

Но как измервате колко ефективна е структурата на данните всъщност?

Виждали ли сте някога странни обозначения, които хората използват онлайн като O (n)? Това се нарича Big O Notation и това е стандартният начин за оценка на ефективността на структурите и алгоритмите. Голямото O, което използваме, е представянето на най-лошия сценарий: наличието на нещо, което е O (n) (като n е броят на елементите вътре), означава, че в най-лошия случай е необходимо време n , което е наистина добро.

Вътре в скобата написахме n, което е еквивалентно на писането на израза y = x →. Мащабира се пропорционално. Но понякога имаме различни изрази:

  • O (1)
  • O (log (n))
  • На)
  • O (n²)
  • O (n³)
  • На!)
  • O (e ^ n)

Колкото по-нисък е резултатът от дадена функция, толкова по-ефективна е структурата.

Има няколко вида дървета. Ще говорим за BST (двоични дървета за търсене) и AVL дървета (автоматично балансирани дървета), които имат различни свойства:

Добре, говорихте за цялата тази странна нотация ... как работят дърветата?

Името на дървото идва от реалното му представяне: то има корен, листа и клони и често се представя по следния начин:

Има няколко деноминации, които използваме, а именно родител и дете, които имат уникална връзка. Ако x е родител на y, тогава y е дъщеря на x . В това изображение 2 е родител на 5, след това 5 е дете на 2. Всеки възел - всяка позиция със стойност - може да има само 1 родител и 2 деца.

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

Бинарни дървета за търсене

Точно тогава се появяват Binary-Търсене дървета! Вместо просто на случаен принцип да поставят дъщерни възли, те следват определен ред:

  • Ако няма възли, тогава първата въведена стойност става коренът на дървото.
  • Ако има възли, вмъкването прави следните стъпки: започвайки от корена, ако въведената стойност е по-малка от текущия възел, преминете през левия клон, в противен случай преминете през десния. Ако сте на празно място, значи там принадлежи вашата стойност!

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

//This code won't compile in any language (that I know of) and only serves to demonstrate how the code would look like
def insert(Node n, int v) { if n is NULL: return createNode(v) else if n.value < v: n.right = insert(n.right, v) else: n.left = insert(n.left, v) return n}

Сега какво се случва тук? Първо проверяваме дали мястото, където сме сега, е празно. Ако е, ние създаваме възел на това място с функцията createNode. Ако не е празно, тогава трябва да видим къде да поставим възела си.

Тази демонстрация показва как работи:

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

Но не винаги върви така добре, както в gif-а по-горе. Ами ако получим нещо подобно?

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

Изтриването от BST също е лесно:

  • Ако възел няма деца → премахнете възела
  • Ако възел има едно дете → свържете родителския възел с неговия възел и премахнете възела
  • Ако възел има 2 деца → заменете възела за най-голямото му дете (най-дясното ляво дете) → вижте изображението по-долу

Така че сега знаете всичко необходимо за BST. Доста готино, а?

Но какво, ако искате ВИНАГИ да имате ефективно дърво? Какво би направил?

Ако имате такава необходимост, AVL дърветата могат да направят това за вас доста добре. В замяна на това те са милиони пъти по-сложни от BST, но следват същата организация като преди.

An AVL tree is a self-balancing tree that has specific operations (called rotations) that allow the tree to stay balanced . This means that each node in the tree will have a difference of height between its two child branches of maximum 1.

With this, the tree will always have a height of log(n) (n being the number of elements) and this allows you to search for elements in a really efficient way.

So now you see how good and perfect balanced trees are. But how to make them is the real question. I have mentioned the word depth before, so let’s first understand it.

Height is what allows us to understand if our tree is balanced or not. And with it we’re able to determine where the problem is and apply the balancing functions: rotations. These are really simple functions that consist of exchanging nodes between each other in order to remove the height difference, but they might look really strange at first.

There are 4 operations:

  • Rotation Left
  • Rotation Right
  • Rotation Left-Right
  • Rotation Right-Left

Wow that was strange… how do rotations work?

Rotations are strange at first, and I suggest checking out some animations of them working.

Try with your own trees on this website: //www.cs.usfca.edu/~galles/visualization/AVLtree.html

It allows you to dynamically see the rotations happening and is a great tool!

There are only four cases, so understanding them will be easy.

That’s all for now!

Trees are pretty easy to understand, and with practice you can work with them easily. Applying them in your code is a major key to make your programs a lot more efficient.

If you have any questions about something you didn’t understand, disagree with, or would like to suggest, feel free to contact me through Twitter or by email!

Email: tiago.melo.antunes [at] tecnico [dot] ulisboa [dot] pt