Mnogo puta želite podatke spremiti u svoj program i pristupiti im puno puta. A često ćete ga pohraniti u vrlo jednostavnu strukturu podataka: niz. I to često djeluje jako dobro! Ali ponekad treba puno vremena da se završi.
Tako su, da bi optimizirali ovu vrstu programa, mnogi pametni ljudi razvili neke čudne stvari koje nazivamo strukturama podataka . Danas ću se pozabaviti nekim osnovama o ovoj temi i razgovarat ću o jednoj specifičnoj strukturi o kojoj se često pita tijekom kodiranja intervjua i sve izluđuje: Drveće.
Neću puno zaranjati u kod, samo u teoriju kako sve funkcionira. Postoje milijuni uzoraka koda na mreži, pa samo pogledajte jedan nakon što shvatite kako drveće funkcionira!
Pa što je zapravo struktura podataka?
Prema Wikipediji:
" Struktura podataka je format organizacije podataka i pohrane koji omogućuje učinkovit pristup i izmjenu"To u osnovi znači da nije ništa drugo nego kod napisan za stvaranje složenog načina za pohranu podataka. Postoji mnogo podatkovnih struktura koje možete implementirati, a svaka ima određeni zadatak. Oni mogu prijeći od stvarno jednostavnih - poput povezanih popisa - do stvarno složenih struktura - poput grafova.
Drveće je dovoljno složeno da može biti vrlo brzo u svom poslu, ali dovoljno jednostavno da bude razumljivo. A jedna stvar u kojoj su stvarno dobri jest pronalaženje vrijednosti uz minimalno korištenje memorije.
Ali kako mjeriti koliko je struktura podataka zapravo učinkovita?
Jeste li ikada vidjeli neke neobične zapise koje ljudi koriste na mreži poput O (n)? To se naziva Big O Notation i to je standardni način procjene izvedbe struktura i algoritama. Veliko O koje koristimo predstavlja prikaz najgoreg scenarija: imati nešto što je O (n) (s n brojem elemenata unutar) znači da je u najgorem slučaju potrebno vrijeme n , što je stvarno dobro.
Unutar zagrade napisali smo n što je ekvivalent pisanju izraza y = x →. Proporcionalno se skalira. Ali ponekad imamo različite izraze:
- O (1)
- O (log (n))
- Na)
- O (n²)
- O (n³)
- Na!)
- O (e ^ n)
Što je rezultat funkcije niži, to je struktura učinkovitija.
Postoji više vrsta drveća. Govorit ćemo o BST-u (binarno-tragačko drveće) i AVL drveću (automatski uravnotežena stabla) koja imaju različita svojstva:
Ok, razgovarali ste o svim tim čudnim notacijama ... pa kako rade stabla?
Stablo imena dolazi iz stvarnog prikaza: ima korijen, lišće i grane, a često je predstavljeno ovako:
Postoji nekoliko denominacija koje koristimo, naime roditelj i dijete, koje imaju jedinstveni odnos. Ako je x roditelj y, tada je y dijete x . Na ovoj je slici 2 roditelj 5, a zatim 5 podređeno dijete 2. Svaki čvor - svaki položaj s vrijednošću - može imati samo 1 roditelja i 2 djece.
Ali uz sve ovo, ne postoji obrazac koji se slijedi, pa ovo stablo zapravo nije toliko korisno ... Stoga bismo trebali dodati još nekoliko pravila da bismo napravili dobru strukturu podataka.
Binarna stabla pretraživanja
Tada se pojavljuju binarna stabla za pretraživanje! Umjesto da nasumično postavljaju podređene čvorove, oni slijede određeni redoslijed:
- Ako nema čvorova, prva unesena vrijednost postaje korijen stabla.
- Ako postoje čvorovi, umetanje poduzima sljedeće korake: počevši od korijena, ako je vrijednost koju unosite manja od trenutnog čvora, prođite kroz lijevu granu, u suprotnom prođite kroz desnu. Ako ste na praznom mjestu, onda tamo pripada vaša vrijednost!
Na početku bi se ovo moglo činiti pomalo zbunjujućim, ali napišite neki pseudo kôd da bismo ga pojednostavili:
//This code won't compile in any language (that I know of) and only serves to demonstrate how the code would look likedef 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}Što se ovdje događa? Prvo provjerimo je li mjesto na kojem smo sada prazno. Ako jest, na tom mjestu stvaramo čvor s funkcijom createNode. Ako nije prazan, onda moramo vidjeti gdje bismo trebali postaviti svoj čvor.
Ova demonstracija pokazuje kako to radi:
Na taj način možemo tražiti bilo koju vrijednost na stablu, a da ne moramo prolaziti kroz sve čvorove. Sjajno!
Ali to ne ide uvijek tako dobro kao u gornjem gifu. Što ako dobijemo ovako nešto?
U ovom slučaju, ponašanje stabla tjera vas da prođete kroz sve čvorove. Zbog toga je najgora efikasnost BST-a O (n), što ga čini sporim.
Brisanje s BST-a također je jednostavno:
- Ako čvor nema djece → uklonite čvor
- Ako čvor ima jedno dijete → povežite roditeljski čvor s njegovim unukom i uklonite čvor
- Ako čvor ima 2 djece → zamijenite čvor za njegovo najveće dijete (krajnje lijevo dijete) → pogledajte sliku dolje
Dakle, sada znate sve što vam treba o BST-ovima. Prilično cool ha?
Ali što ako biste UVIJEK željeli imati učinkovito drvo? Što bi ti napravio?
Ako imate tu potrebu, AVL stabla to mogu učiniti za vas prilično dobro. U zamjenu su milijuni puta složeniji od BST-a, ali slijede istu organizaciju kao i prije.
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