En introduktion til træer i programmering: ilt ved effektiv kodning

Mange gange ønsker du at gemme oplysninger i dit program og få adgang til det mange gange. Og du gemmer det ofte i en meget enkel datastruktur: et array. Og det fungerer ofte rigtig godt! Men nogle gange tager det bare meget tid at afslutte.

Og så, for at optimere denne form for program, udviklede mange smarte mennesker nogle underlige ting, som vi kalder datastrukturer . I dag vil jeg behandle nogle grundlæggende om dette emne, og jeg vil diskutere en bestemt struktur, som ofte bliver spurgt om under kodningssamtaler og gør alle vanvittige: Træer.

Jeg dykker ikke meget ind i koden, kun i teorien om, hvordan alt fungerer. Der er millioner af kodeeksempler online, så bare se på en, når du har forstået, hvordan træer fungerer!

Så hvad er egentlig en datastruktur?

Ifølge Wikipedia:

“En datastruktur er et dataorganisations- og lagerformat, der muliggør effektiv adgang og modifikation”

Dette betyder grundlæggende, at det ikke er andet end kode skrevet for at skabe en kompleks måde at gemme data på. Der er mange datastrukturer, som du kan implementere, og hver enkelt har en specifik opgave. De kan gå fra virkelig enkle - som sammenkædede lister - til virkelig komplekse strukturer - som grafer.

Træer er komplekse nok til at være rigtig hurtige til hvad de gør, men enkle nok til at de er forståelige. Og en ting, de er rigtig gode til, er at finde værdier med mindst mulig hukommelsesforbrug.

Men hvordan måler du, hvor effektiv en datastruktur virkelig er?

Har du nogensinde set nogle mærkelige notationer, som folk bruger online som O (n)? Det kaldes Big O Notation, og det er standardmetoden til at evaluere ydeevnen for strukturer og algoritmer. Den store O, som vi bruger, er repræsentationen af ​​det værst tænkelige scenario: at have noget, der er O (n) (hvor n er antallet af elementer indeni) betyder, at det i værste fald tager tid n , hvilket er virkelig godt.

Inde i parentesen skrev vi n, hvilket svarer til at skrive udtrykket y = x →. Det skaleres proportionalt. Men nogle gange har vi forskellige udtryk:

  • O (1)
  • O (log (n))
  • På)
  • O (n²)
  • O (n3)
  • På!)
  • O (e ^ n)

Jo lavere resultatet af en funktion er, jo mere effektiv er en struktur.

Der er flere typer træer. Vi vil tale om BST (Binary-Search Trees) og AVL Trees (Auto balanced træer), som har forskellige egenskaber:

Ok, du talte om al denne underlige notation ... så hvordan fungerer træer?

Navnetræet kommer fra dets virkelige repræsentation: det har en rod, blade og grene og er ofte repræsenteret således:

Der er et par trosretninger, som vi bruger, nemlig forælder og barn, som har et unikt forhold. Hvis x er forælder til y, er y barn til x . I dette billede er 2 forælder til 5, så er 5 barn til 2. Hver knude - hver position med en værdi - kan kun have 1 forælder og 2 børn.

Men udover alt dette er der ikke et mønster, der følges, så dette træ er ikke så nyttigt ... Så vi skal tilføje et par flere regler for at skabe en god datastruktur.

Binære søgetræer

Det er, når træer med binær søgning kommer ind! I stedet for bare tilfældigt at placere underordnede noder følger de en bestemt rækkefølge:

  • Hvis der ikke er nogen noder, bliver den første værdi, der indtastes, træets rod .
  • Hvis der er noder, tager indsættelsen følgende trin: starter ved roden, hvis den værdi, du indtaster, er mindre end den aktuelle node, skal du gå gennem den venstre gren, ellers gå gennem den rigtige. Hvis du er på et tomt sted, så er det her din værdi hører til!

Dette kan føles lidt forvirrende i begyndelsen, men lad os skrive noget pseudokode for at forenkle det:

//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}

Hvad sker der nu her? Først kontrollerer vi, om det sted, hvor vi er nu, er tomt. Hvis det er tilfældet, opretter vi en node på det sted med funktionen createNode. Hvis det ikke er tomt, skal vi se, hvor vi skal placere vores knude.

Denne demo viser, hvordan den fungerer:

På denne måde kan vi søge efter enhver værdi i træet uden at skulle gå gennem alle knudepunkter. Store!

Men det går ikke altid så godt som i gifen ovenfor. Hvad hvis vi får noget som dette?

I dette tilfælde får træets opførsel dig til at gå gennem alle knudepunkterne. Derfor er en BST's worst case-effektivitet O (n), hvilket gør det langsomt.

Sletning fra BST er også let:

  • Hvis en knude ikke har børn → fjern knuden
  • Hvis en knude har et barn → skal du forbinde forældreknudepunktet til dets børnebarnknude og fjerne noden
  • Hvis en knude har 2 børn → erstat knuden for dens største barn (det venstre barn til højre) → se billedet nedenfor

Så nu ved du alt hvad du har brug for om BST'er. Temmelig sej huh?

Men hvad nu hvis du ALLTID ville have et effektivt træ? Hvad ville du gøre?

Hvis du har den nødvendighed, kan AVL-træer gøre det ret godt for dig. Til gengæld er de millioner af gange mere komplekse end BST'er, men følger den samme organisation som før.

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!

Træer er ret nemme at forstå, og med praksis kan du nemt arbejde med dem. Anvendelse af dem i din kode er en vigtig nøgle til at gøre dine programmer meget mere effektive.

Hvis du har spørgsmål om noget, du ikke forstod, er uenig i eller gerne vil foreslå, er du velkommen til at kontakte mig via Twitter eller via e-mail!

E-mail: tiago.melo.antunes [at] tecnico [dot] ulisboa [dot] pt