Metainformationen zur Seite
  •  

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

Link zu dieser Vergleichsansicht

Nächste Überarbeitung		Vorhergehende Überarbeitung
informatik:algorithmisch:python:binaerbaeume [2024/07/20 12:59] – angelegt technikinformatik:algorithmisch:python:binaerbaeume [2024/07/21 07:33] (aktuell) – [Kanten und Gewicht] technik
Zeile 1: Zeile 1:
 ===== Binärbäume ===== ===== Binärbäume =====
 +Bäume sind ein sehr gutes Beispiel dafür, wie man mit Hilfe der Objektorientierung sehr eleganten Code schreiben kann. Wir betrachten an dieser Stelle vollständige und volle Binärbäume, weil diese in der Implementierung am einfachsten zu handhaben sind. 
  
 +==== Grundbegriffe ====
 +Ein Baum besteht aus **Knoten**. Ganz oben befindet sich der **Wurzelknoten**. Mit ihm sind im Falle eines Binärbaumes zwei **Blattknoten** verbunden. Die Verbindung zwischen den Knoten bezeichnet man als **Kante**. Die Information, welche Blattknoten mit dem Wurzelknoten verbunden sind, befindet sich nur im Wurzelknoten. Der Wurzelknoten "zeigt" damit auf die Blattknoten, weswegen man die Kante auch als **gerichtet** bezeichnet.  
 +{{ :informatik:algorithmisch:python:tree_basics.png?direct |}}
 +
 +Hier eine einfache Implementierung in Python:
 +<file python simplenode.py>
 +class Node:
 +    def __init__(self) -> None:
 +        self.left = None
 +        self.right = None
 +
 +# die drei Knoten erstellen
 +wurzel = Node()
 +blattlinks = Node()
 +blattrechts = Node()
 +
 +# Verweise vom Wurzelknoten auf die Blätter erstellen (Baum aus den Knoten bauen)
 +wurzel.links = blattlinks
 +wurzel.rechts = blattrechts
 +</file>
 +
 +Normalerweise trägt ein Knoten nicht nur Information darüber, welche anderen Knoten mit ihm verbunden sind, sondern speichert zusätzlich Daten. Das werden wir weiter unten bei den Gewichten von Kanten noch in einer Anwendung sehen. 
 +
 +==== Spezialfall Binärbäume ====
 +
 +Ein Binärbaum besitzt immer zwei Blattknoten an einem übergeordneten Knoten. Bei einem vollständigen Binärbaum sind zum alle Ebenen komplett ausgefüllt:
 +{{ :informatik:algorithmisch:python:binary_full-tree.png?direct&400 |}}
 +
 +Alle denkbaren Bäume (mit z.B. mehr Blättern pro Knoten) lassen sich durch Umhängen von Knoten zu einem Binärbaum umformen, der jedoch dann nicht immer vollständig ist. 
 +{{ :informatik:algorithmisch:python:binary_transformation.png?direct&600 |}}
 +
 +==== Kanten und Gewicht ====
 +Eine Kante kann ein Gewicht bekommen, das z.B. angibt, wie wahrscheinlich es ist, dass Daten, die in einem Baum gespeichert sind, aufeinander folgen.
 +{{ :informatik:algorithmisch:python:tree_data_weight.png?direct&400 |}}
 +Auf diese Weise könnte in einem Sprachmodell hinterlegt sein, wie wahrscheinlich es ist, welches Wort auf den Satzanfang "Es" folgt. Hier einmal ein Beispielimplementierung für den letzten Baum. Die Knoten werden als zusätzliche Erweiterung in einer Liste **nodes[]** organisiert, damit man bei der Implementierung besser durch den Baum "scannen" (Fachwort: **traversieren**) kann. . 
 +
 +<file python treedataweighted.py>
 +class Node:
 +    def __init__(self, data) -> None:
 +        self.left = None
 +        self.right = None
 +        self.leftweight = 0
 +        self.rightweight = 0
 +        self.data = data
 +
 +# Liste für die Knoten des Baumes anlegen
 +nodes[]
 +
 +# Knoten anlegen
 +nodes[0] = Node("Es")
 +nodes[1] = Node("war")
 +nodes[2] = Node("kam")
 +
 +# Knoten verbinden
 +nodes[0].left = nodes[1]
 +nodes[0].right = nodes[2]
 +
 +# Gewichte der Kanten setzen
 +nodes[0].leftweight = 8
 +nodes[0].rightweight = 5
 +</file>
 ==== Ein kleines Sprachmodell ==== ==== Ein kleines Sprachmodell ====
 +Hier sehr ihr ein Beispiel für ein "Sprachmodell", welches Märchenanfänge generiert und von all dem Gebrauch macht, was wir bisher über Binärbäume besprochen haben. Alle wesentlichen Aktionen, die in großen Sprachmodellen stattfinden, lassen sich hier erleben, z.B. dass immer Interaktion mit Menschen notwendig sind, um ein Sprachmodell zu optimieren. 
  
 <file python littlelanguangemodell.py> <file python littlelanguangemodell.py>