Die bisher verwendete Python Listen sind sehr einfach zu bedienen. Allerdings verschleiern sie die zu Grunde liegende Datenstruktur.
Bei einer Python Liste handelt es sich um ein dynamisches Array. Ein Array ist eine Datenstruktur, bei der im Voraus ein zusammenhängender Speicherbereich von fixer Grösse definiert wird. Bei einem dynamischen Array fällt die Restriktion der fixierten Grösse weg und dem Speicherplatz wird laufend den Bedürfnissen angepasst. Die Anpassung der Grösse des Speicherbereichs ist allerdings mit erheblichem Rechenaufwand verbunden. Diesem Nachteil steht allerdings der Vorteil gegenüber, dass in einem Array mittels des Index mit konstantem Aufwand auf die einzelnen Elemente zugegriffen werden kann. Falls das Array sortiert ist, kann ausserdem relativ effizient nach einem Element in dieser Datenstruktur gesucht werden.
Eine Alternative für das Ablegen einer Sequenz von Elementen mit nicht im Voraus bestimmten Umfang, ist eine verkettete Liste (linked list).
Die verkettete Liste (linked list) ist eine Datenstruktur, bei der mit einer Variabel auf das erste gespeicherte Element verwiesen wird. Zusammen mit diesem Element wird auch der Speicherort des nächsten Elementes gespeichert. Von dieser Verkettung von Element zu Element hat die Datenstruktur ihren Namen. In einer verketteten Liste lassen sich neue Elemente mit konstantem Aufwand einfügen. Allerdings hat die verkettete Liste den Nachteil, dass die Suche nach einem Element mit linearem Aufwand verbunden ist.
An dieser Stelle kommt der binäre Suchbaum (binary search tree, bst) ins Spiel.
Bäume in der Informatik
Quelle: xkcd.com/835, besucht am 4. Mai 24
Ein Baum in der Informatik ist eine Datenstruktur die aus Knoten (engl. Vertex bzw. vertices, V) und Kanten (engl. edge, E) besteht. Der erste Knoten ist die Wurzel (engl. root). Alle anderen Knoten haben einen Knoten als Elternknoten. Ein Elternknoten kann ein oder mehrere Kindknoten haben. Ein Knoten ohne Kinder wird als Blatt bezeichnet. Üblicherweise werden Bäume vom Wurzelknoten aus nach unten dargestellt.
Ein binärer Suchbaum ist eine baumförmige Datenstruktur, bei der jeder Knoten ein oder zwei Kinder hat. Die Werte in den Knoten sind dabei so in den Baum eingeordnet, dass jedes linke Kind kleiner ist als der Elternknoten und jedes rechte Kind grösser. Im Idealfall ist der Baum symmetrisch ausbalanciert. Es kann allerdings auch sein, dass ein binärer Suchbaum derart aus dem Gleichgewicht ist, dass er wie eine verkettete Liste aussieht. Aus diesem Grund muss bei der Effizienzbetrachtung dieser Datenstruktur zwischen Idealfall und Worst Case unterschieden werden. Im Idealfall ist die Suche und das Einfügen neuer Elemente mit einem Aufwand von \(log(n)\) möglich. Im Worst Case verursacht die Suche einen linearen Aufwand.
Die folgende Grafik zeigt ein Beispiel eines binären Suchbaums.
