Bevezetés a fákba a programozásban: a hatékony kódolás oxigénje

Sokszor el akarja menteni az információkat a programjában, és sokszor hozzájuk fér. És gyakran nagyon egyszerű adatstruktúrában tárolja: egy tömbben. És gyakran nagyon jól működik! De néha csak sok időbe telik a befejezés.

Ezért az ilyen program optimalizálása érdekében sok okos ember kifejlesztett furcsa dolgokat, amelyeket adatstruktúráknak hívunk . Ma foglalkozom ezzel a témával kapcsolatos néhány alapismerettel, és megvitatok egy sajátos struktúrát, amelyről gyakran kérdeznek a kódoló interjúk során, és mindenkit megőrjít: a fákat.

Nem sokat fogok belemerülni a kódba, csak a minden működésének elméletébe. Több millió kódminta van online, ezért csak nézzen meg egyet, miután megértette a fák működését!

Mi tehát valójában az adatstruktúra?

A Wikipedia szerint:

Az adatstruktúra olyan adatszervezési és tárolási formátum, amely hatékony hozzáférést és módosítást tesz lehetővé”

Ez alapvetően azt jelenti, hogy ez nem más, mint az adatok tárolásának komplex módjának létrehozásához írt kód. Sok olyan adatstruktúra létezik, amelyeket megvalósíthat, és mindegyiknek van egy saját feladata. A valóban egyszerű felsorolásoktól - például a kapcsolt listáktól - valóban összetett struktúrákig - például grafikonokig - léphetnek.

A fák elég bonyolultak ahhoz, hogy valóban gyorsak legyenek, amit csinálnak, de elég egyszerűek ahhoz, hogy érthetőek legyenek. És egy dolog, amiben nagyon jók, az a minimális memóriafelhasználású értékek megtalálása.

De hogyan mérik, mennyire hatékony egy adatstruktúra?

Láttál már valaha olyan furcsa jelölést, amelyet az emberek online használnak, mint például O (n)? Ezt hívják Big O jelölésnek, és ez a szokásos módszer a struktúrák és algoritmusok teljesítményének értékelésére. A nagy O, amelyet használunk, a legrosszabb eset ábrázolása: ha van valami, ami O (n) (ahol n a benne lévő elemek száma), az azt jelenti, hogy a legrosszabb esetben n időre van szükség , ami nagyon jó.

A zárójelbe írtunk n-t, amely egyenértékű a kifejezés megírásával y = x →. Arányosan méretez. De néha különböző kifejezéseink vannak:

  • O (1)
  • O (log (n))
  • Tovább)
  • O (n²)
  • O (n³)
  • Tovább!)
  • O (e ^ n)

Minél alacsonyabb egy függvény eredménye, annál hatékonyabb egy szerkezet.

Többféle fa létezik. Beszélünk a BST-ről (bináris keresési fák) és az AVL fákról (automatikus kiegyensúlyozott fák), amelyeknek különböző tulajdonságai vannak:

Ok, beszéltél erről a furcsa jelölésről ... akkor hogyan működnek a fák?

A fa név valódi reprezentációjából származik: gyökérrel, levelekkel és ágakkal rendelkezik, és gyakran így ábrázolják:

Van néhány felekezet, amelyet használunk, nevezetesen a szülő és a gyermek, amelyek egyedülálló kapcsolatban állnak egymással. Ha x az y szülője, akkor y az x gyermeke . Ezen a képen 2 szülő 5-nek, majd 5 szülője 2-nek. Minden csomópontnak - mindegyik értékkel rendelkező pozíciónak - csak 1 szülője és 2 gyermeke lehet.

De mindezek mellett nincs követendő minta, így ez a fa nem igazán hasznos ... Tehát hozzá kell adnunk még néhány szabályt egy jó adatstruktúra kialakításához.

Bináris kereső fák

Ekkor jönnek be a bináris keresési fák! Ahelyett, hogy véletlenszerűen helyeznék el a gyermekcsomópontokat, egy meghatározott sorrendet követnek:

  • Ha nincsenek csomópontok, akkor az első beírt érték lesz a fa gyökere .
  • Ha vannak csomópontok, akkor a beillesztés a következő lépéseket hajtja végre: a gyökérből kiindulva, ha a beírt érték kisebb, mint az aktuális csomópont, akkor menjen át a bal ágon, máskülönben menjen át a jobb oldalon. Ha üres helyen vagy, akkor az értéked az!

Ez az elején kissé zavarónak tűnhet, de írjunk néhány álkódot annak egyszerűsítése érdekében:

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

Mi történik itt? Először ellenőrizzük, hogy üres-e az a hely, ahol most vagyunk. Ha igen, akkor létrehozunk egy csomópontot azon a helyen a függvénnyel createNode. Ha nem üres, akkor meg kell látnunk, hová tegyük a csomópontunkat.

Ez a bemutató bemutatja a működését:

Így bármilyen értéket megkereshetünk a fában anélkül, hogy az összes csomópontot át kellene mennünk. Nagy!

De nem mindig megy olyan jól, mint a fenti gif-ben. Mi van, ha ilyesmit kapunk?

Ebben az esetben a fa viselkedése arra készteti az összes csomópontot. Ezért a BST legrosszabb esetben az O (n) hatékonysága, ami lassúvá teszi.

A BST törlése szintén egyszerű:

  • Ha egy csomópontnak nincs gyermeke, → távolítsa el a csomópontot
  • Ha egy csomópontnak egy gyermeke van, → csatlakoztassa a szülő csomópontot az unoka csomóponthoz, és távolítsa el a csomópontot
  • Ha egy csomópontnak 2 gyermeke van → cserélje ki a csomópontot a legnagyobb gyermekére (a jobb szélső bal gyermek) → lásd az alábbi képet

Tehát most mindent tud a BST-ről. Nagyon klassz, mi?

De mi van, ha MINDIG hatékony fát akarsz ? Mit csinálnál?

Ha erre szükséged van, akkor az AVL fák ezt elég jól meg tudják tenni. Cserébe milliószor bonyolultabbak, mint a BST-k, de ugyanazt a szervezetet követik, mint korábban.

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