Eine Einführung in Bäume in der Programmierung: der Sauerstoff einer effizienten Codierung

Oft möchten Sie Informationen in Ihrem Programm speichern und mehrmals darauf zugreifen. Und Sie werden es oft in einer sehr einfachen Datenstruktur speichern: einem Array. Und es funktioniert oft sehr gut! Aber manchmal dauert es einfach viel Zeit, bis es fertig ist.

Um diese Art von Programm zu optimieren, haben viele kluge Leute einige seltsame Dinge entwickelt, die wir Datenstrukturen nennen . Heute werde ich einige Grundlagen zu diesem Thema ansprechen und eine bestimmte Struktur diskutieren, nach der beim Codieren von Interviews häufig gefragt wird und die alle verrückt macht: Bäume.

Ich werde nicht viel in den Code eintauchen, nur in die Theorie, wie alles funktioniert. Es sind Millionen von Codebeispielen online. Schauen Sie sich also eines an, nachdem Sie verstanden haben, wie Bäume funktionieren!

Was ist eigentlich eine Datenstruktur?

Laut Wikipedia:

"Eine Datenstruktur ist ein Datenorganisations- und Speicherformat, das einen effizienten Zugriff und eine effiziente Änderung ermöglicht."

Dies bedeutet im Grunde, dass es sich nur um Code handelt, der geschrieben wurde, um eine komplexe Methode zum Speichern von Daten zu erstellen. Es gibt viele Datenstrukturen, die Sie implementieren können, und jede hat eine bestimmte Aufgabe. Sie können von wirklich einfachen - wie verknüpften Listen - zu wirklich komplexen Strukturen - wie Grafiken - übergehen.

Bäume sind komplex genug, um wirklich schnell zu sein, aber einfach genug, dass sie verständlich sind. Und eine Sache, in der sie wirklich gut sind, ist das Finden von Werten bei minimaler Speichernutzung.

Aber wie messen Sie, wie effizient eine Datenstruktur wirklich ist?

Haben Sie jemals eine seltsame Notation gesehen, die Leute online verwenden, wie O (n)? Dies wird als Big O-Notation bezeichnet und ist die Standardmethode zur Bewertung der Leistung von Strukturen und Algorithmen. Das große O, das wir verwenden, ist die Darstellung des Worst-Case-Szenarios: Etwas zu haben, das O (n) ist (wobei n die Anzahl der Elemente im Inneren ist), bedeutet, dass es im schlimmsten Fall Zeit n braucht , was wirklich gut ist.

In der Klammer haben wir n geschrieben, was dem Schreiben des Ausdrucks entspricht y = x →. Es skaliert proportional. Aber manchmal haben wir unterschiedliche Ausdrücke:

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

Je niedriger das Ergebnis einer Funktion ist, desto effizienter ist eine Struktur.

Es gibt mehrere Arten von Bäumen. Wir werden über BST (Binary-Search Trees) und AVL Trees (Auto Balanced Tree) sprechen, die unterschiedliche Eigenschaften haben:

Ok, du hast über all diese seltsame Notation gesprochen. Wie funktionieren Bäume?

Der Namensbaum stammt aus seiner realen Darstellung: Er hat eine Wurzel, Blätter und Zweige und wird oft so dargestellt:

Es gibt einige Konfessionen, die wir verwenden, nämlich Eltern und Kind, die eine einzigartige Beziehung haben. Wenn x Eltern von y ist, ist y Kind von x . In diesem Bild ist 2 ein Elternteil von 5, dann ist 5 ein Kind von 2. Jeder Knoten - jede Position mit einem Wert - kann nur 1 Elternteil und 2 Kinder haben.

Abgesehen davon gibt es kein Muster, dem gefolgt wird, so dass dieser Baum nicht wirklich nützlich ist. Deshalb sollten wir ein paar weitere Regeln hinzufügen, um eine gute Datenstruktur zu erstellen.

Binäre Suchbäume

Dann kommen Binary-Search-Bäume ins Spiel! Anstatt nur untergeordnete Knoten zufällig zu platzieren, folgen sie einer bestimmten Reihenfolge:

  • Wenn keine Knoten vorhanden sind, wird der erste eingegebene Wert zur Wurzel des Baums.
  • Wenn Knoten vorhanden sind, werden beim Einfügen die folgenden Schritte ausgeführt: Wenn der eingegebene Wert an der Wurzel beginnt und kleiner als der aktuelle Knoten ist, gehen Sie durch den linken Zweig, andernfalls durch den rechten. Wenn Sie sich an einem leeren Ort befinden, gehört Ihr Wert dorthin!

Dies mag sich am Anfang etwas verwirrend anfühlen, aber schreiben wir einen Pseudocode, um es zu vereinfachen:

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

Was passiert hier? Zuerst prüfen wir, ob der Ort, an dem wir uns jetzt befinden, leer ist. Wenn ja, erstellen wir an dieser Stelle einen Knoten mit der Funktion createNode. Wenn es nicht leer ist, müssen wir sehen, wo wir unseren Knoten platzieren sollen.

Diese Demo zeigt, wie es funktioniert:

Auf diese Weise können wir nach beliebigen Werten im Baum suchen, ohne alle Knoten durchlaufen zu müssen. Toll!

Aber es geht nicht immer so gut wie im obigen GIF. Was ist, wenn wir so etwas bekommen?

In diesem Fall führt das Verhalten des Baums dazu, dass Sie alle Knoten durchlaufen. Aus diesem Grund liegt die Worst-Case-Effizienz eines BST bei O (n), was ihn langsam macht.

Das Löschen aus der BST ist ebenfalls einfach:

  • Wenn ein Knoten keine untergeordneten Knoten hat → Entfernen Sie den Knoten
  • Wenn ein Knoten ein Kind hat → Verbinden Sie den Elternknoten mit seinem Enkelknoten und entfernen Sie den Knoten
  • Wenn ein Knoten 2 Kinder hat → Ersetzen Sie den Knoten durch sein größtes Kind (das am weitesten links stehende Kind) → siehe Abbildung unten

Jetzt wissen Sie also alles, was Sie über BSTs brauchen. Ziemlich cool, oder?

Aber was ist, wenn Sie IMMER einen effizienten Baum haben möchten ? Was würden Sie tun?

Wenn Sie diese Notwendigkeit haben, können AVL-Bäume das ziemlich gut für Sie tun. Im Gegenzug sind sie millionenfach komplexer als BSTs, folgen jedoch derselben Organisation wie zuvor.

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