AuD Übung 08 Bäume (Stefan Bosse) [22.1.2026]

AuD Übung Bäume (08)

Gruppennummer und Namen der Gruppenmitglieder (Zeilenformat!)
Punkte:Total/21./22./23./24./25./26./27./2

Ausgabe: 16.1.2026

Abgabe: 24.1.2026

AuD Übung Bäume (08)
Bäume - Grundlagen
Bäume - Programmierung
Datenstrukturen
Algorithmen
Programm

Es dürfen keine Standard Java Packages verwendet werden mit Ausnahme von System und String.

In dieser Übung soll die Erzeugung, der Zugriff und die Manipulation von Daten mit Baumstrukturen erfolgen und untersucht werden.

Bäume - Grundlagen

Aufgabe 1. Welche Eigenschaften haben Binärbäume?


Aufgabe 2. Es wird von geordneten Binärbäumen ausgegenagen. Was muss beachtet werden wenn neue Knoten eingefügt und bestehende gelöscht werden? Wie ist die Ordnungsrelation?


Bäume - Programmierung

Datenstrukturen

Definition 1. Knoten eines Baums und der Baum gleich dem Wurzelknoten 
type node = {
  left  : node|null,
  right : node|null,
  data  : string,
  key   : number
}
type tree = node|null

Algorithmen

Nachfolgend sind die aus der Vorlesung bekannten Algorithmen in Pseudonotation zusammengefasst.

Algorithmus 1. Einfügen eines Elements in den Baum mit node als Wurzelknoten 
function insert(node,data,key) {
  if (node.key==key) error(Error);
  if (k>node.key) {
    if (!node.right) node.right=Node(data,key)
    else insert(node.right,data,key)
  } else {
    if (!node.left) node.left=Node(data,key)
    else insert(node.left,data,key)    
  }
}
Algorithmus 2. Entfernen eines Elements aus dem Baum mit dem Wurzelknoten root 
function removeNode(root,k) {
  // Eingabe: Wurzel vom Suchbaum T, Schlüssel k des zu löschenden Elementes

  node = searchNode (root, k)
  if (node = null) error(Error)
  parent = searchParentofNode(root, node) // Sollte mit Search kombiniert werden

  /* 1. Fall */
  if (!node.left && !node.right) { // node ist Blattknoten 

    if (parent.left===node) // node ist linkes Kind 

      parent.left = null
    else 
      parent.right = null
  /* 2. Fall */
  } else if (!node.left)  {
    if (parent.left===node)  // node ist linkes Kind 

      parent.left = node.right
    else 
      parent.right = node.right
  } else if (!node.right) {
    if (parent.left===node) // node ist linkes Kind 

      parent.left  = node.left
    else
      parent.right = node.left
  } else /* 3. Fall */
    child = searchMinimalElement (node.right) 
    replaceNode(node,child) // Ersetze node durch child

  }
}
Algorithmus 3. Suche eines Knotens mit dem Schlüssel k in einem Baum mit dem Wurzelknoten node 
function search (node,k) {
  if (node.key==k) return node
  if (node.left && node.left.key<k) return search(node.left,k)
  if (node.right && node.right.key<k) return search(node.right,k)
  error(NOTFOUND)
}

searchNode liefert den Knoten zum Schlüssel k, seachParentNode sucht dann den Vorgänger zu diesem Knoten. Beide Suchfunktionen sollten kombiniert werden in dem die Suche zustandsbasiert den letzten Elternknoten speichert und seachParentNode dann auf das letzte Ergebnis zurückgreift (ein Cache).

Programm

Aufgabe 3. Erstelle die Knotenklasse Node und füge den Programmkode unten ein. Neben der Konstruktionsmethode soll es noch eine print Methode geben die den aktuellen Inhalt eines Knotens formattiert ausgibt.

Klasse Node (websh0) 

PGI+aW1wb3J0PC9iPiBqYXZhLmxhbmcuKjsKPGI+aW1wb3J0PC9iPiB1ai5sYW5nLio7CnB1YmxpYyA8Yj5jbGFzczwvYj4gTm9kZSB7CiAgcHVibGljIFN0cmluZyBkYXRhOwogIHB1YmxpYyBpbnQga2V5OwogIHB1YmxpYyBOb2RlIGxlZnQ7CiAgcHVibGljIE5vZGUgcmlnaHQ7CgogIHB1YmxpYyBOb2RlIChTdHJpbmcgZGF0YSwgaW50IGtleSkgewogICAgdGhpcy5kYXRhPWRhdGE7CiAgICB0aGlzLmtleT1rZXk7CiAgICB0aGlzLmxlZnQ9bnVsbDsKICAgIHRoaXMucmlnaHQ9bnVsbDsKICB9CgogIHB1YmxpYyB2b2lkIHByaW50ICgpIHsKICAJU3lzdGVtLm91dC5wcmludGxuKCJLZXk6ICIrdGhpcy5rZXkrIiwgRGF0YTogIit0aGlzLmRhdGEpOwogIH0KCn0=

Aufgabe 4. Erstelle die Baumklasse Tree und füge den Programmkode unten ein. Diese Klasse muss alle oben eingeführten Funktionen und Hilfsfunktionen enthalten um Knoten einfügen, entfernen und suchen zu können. Weiterhin soll eine Methode print geben die den Baum im ASCII Format ausgibt (s.u.).

Klasse Tree (websh0) 

bXBvcnQgamF2YS5sYW5nLio7CjxiPmltcG9ydDwvYj4gdWoubGFuZy4qOwoKcHVibGljIDxiPmNsYXNzPC9iPiBUcmVlIHsKICAgIHB1YmxpYyBOb2RlIHJvb3Q7CgoJcHVibGljIFRyZWUgKCkgewogICAgCXRoaXMucm9vdD1udWxsOwogICAgfQogICAgcHVibGljIE5vZGUgaW5zZXJ0KFN0cmluZyBkYXRhLCBpbnQga2V5KSB7CiAgICAgICAgcm9vdCA9IGluc2VydChyb290LCBkYXRhLCBrZXkpOwogICAgICAgIDxiPnJldHVybjwvYj4gcm9vdDsKICAgIH0KCiAgICBwcml2YXRlIE5vZGUgaW5zZXJ0KE5vZGUgbm9kZSwgU3RyaW5nIGRhdGEsIGludCBrZXkpIHsKICAgICAgICA8Yj5pZjwvYj4gKG5vZGUgPT0gbnVsbCkgPGI+cmV0dXJuPC9iPiA8Yj5uZXc8L2I+IE5vZGUoZGF0YSwga2V5KTsKICAgICAgICA8Yj5pZjwvYj4gKGtleSA9PSBub2RlLmtleSkgdGhyb3cgPGI+bmV3PC9iPiBSdW50aW1lRXhjZXB0aW9uKCJLZXkgYWxyZWFkeSBleGlzdHMhIik7CiAgICAgICAgPGI+aWY8L2I+IChrZXkgJmx0OyBub2RlLmtleSkgbm9kZS5sZWZ0ID0gaW5zZXJ0KG5vZGUubGVmdCwgZGF0YSwga2V5KTsKICAgICAgICA8Yj5lbHNlPC9iPiBub2RlLnJpZ2h0ID0gaW5zZXJ0KG5vZGUucmlnaHQsIGRhdGEsIGtleSk7CiAgICAgICAgPGI+cmV0dXJuPC9iPiBub2RlOwogICAgfQoKICAgIHB1YmxpYyBOb2RlIHJlbW92ZShpbnQga2V5KSB7CiAgICAgICAgcm9vdCA9IHJlbW92ZShyb290LCBrZXkpOwogICAgICAgIDxiPnJldHVybjwvYj4gcm9vdDsKICAgIH0KCiAgICBwcml2YXRlIE5vZGUgcmVtb3ZlKE5vZGUgbm9kZSwgaW50IGtleSkgewogICAgICAgIDxiPmlmPC9iPiAobm9kZSA9PSBudWxsKSB0aHJvdyA8Yj5uZXc8L2I+IFJ1bnRpbWVFeGNlcHRpb24oIk5PVEZPVU5EIik7CiAgICAgICAgPGI+aWY8L2I+IChrZXkgJmx0OyBub2RlLmtleSkgewogICAgICAgICAgICBub2RlLmxlZnQgPSByZW1vdmUobm9kZS5sZWZ0LCBrZXkpOwogICAgICAgIH0gPGI+ZWxzZTwvYj4gPGI+aWY8L2I+IChrZXkgJmd0OyBub2RlLmtleSkgewogICAgICAgICAgICBub2RlLnJpZ2h0ID0gcmVtb3ZlKG5vZGUucmlnaHQsIGtleSk7CiAgICAgICAgfSA8Yj5lbHNlPC9iPiB7CiAgICAgICAgICAgIDxiPmlmPC9iPiAobm9kZS5sZWZ0ID09IG51bGwpIDxiPnJldHVybjwvYj4gbm9kZS5yaWdodDsKICAgICAgICAgICAgPGI+aWY8L2I+IChub2RlLnJpZ2h0ID09IG51bGwpIDxiPnJldHVybjwvYj4gbm9kZS5sZWZ0OwogICAgICAgICAgICBOb2RlIG1pbk5vZGUgPSBub2RlLnJpZ2h0OwogICAgICAgICAgICA8Yj53aGlsZTwvYj4gKG1pbk5vZGUubGVmdCAhPSBudWxsKSBtaW5Ob2RlID0gbWluTm9kZS5sZWZ0OwoKICAgICAgICAgICAgbm9kZS5rZXkgPSBtaW5Ob2RlLmtleTsKICAgICAgICAgICAgbm9kZS5kYXRhID0gbWluTm9kZS5kYXRhOwogICAgICAgICAgICBub2RlLnJpZ2h0ID0gcmVtb3ZlKG5vZGUucmlnaHQsIG1pbk5vZGUua2V5KTsKICAgICAgICB9CiAgICAgICAgPGI+cmV0dXJuPC9iPiBub2RlOwogICAgfQoKICAgIHB1YmxpYyBOb2RlIHNlYXJjaChpbnQga2V5KSB7CiAgICAgICAgTm9kZSBub2RlID0gcm9vdDsKICAgICAgICA8Yj53aGlsZTwvYj4gKG5vZGUgIT0gbnVsbCkgewogICAgICAgICAgICA8Yj5pZjwvYj4gKGtleSA9PSBub2RlLmtleSkgPGI+cmV0dXJuPC9iPiBub2RlOwogICAgICAgICAgICA8Yj5lbHNlPC9iPiA8Yj5pZjwvYj4gKGtleSAmbHQ7IG5vZGUua2V5KSBub2RlID0gbm9kZS5sZWZ0OwogICAgICAgICAgICA8Yj5lbHNlPC9iPiBub2RlID0gbm9kZS5yaWdodDsKICAgICAgICB9CiAgICAgICAgdGhyb3cgPGI+bmV3PC9iPiBSdW50aW1lRXhjZXB0aW9uKCJOT1RGT1VORCIpOwogICAgfQoKICBwdWJsaWMgdm9pZCBwcmludCgpIHsKICAgICAgPGI+aWY8L2I+ICh0aGlzLnJvb3QgPT0gbnVsbCkgPGI+cmV0dXJuPC9iPjsKICAgICAgTm9kZVtdIHF1ZXVlID0gPGI+bmV3PC9iPiBOb2RlWzI1Nl07CiAgICAgIGludCBxcyA9IDAsIHFlID0gMDsKICAgICAgcXVldWVbcWUrK10gPSByb290OwogICAgICBpbnQgaGVpZ2h0ID0gMDsKICAgICAgPGI+d2hpbGU8L2I+IChxcyAmbHQ7IHFlKSB7CiAgICAgICAgICBpbnQgc2l6ZSA9IHFlIC0gcXM7CiAgICAgICAgICBoZWlnaHQrKzsKICAgICAgICAgIDxiPmZvcjwvYj4gKGludCBpID0gMDsgaSAmbHQ7IHNpemU7IGkrKykgewogICAgICAgICAgICAgIE5vZGUgbiA9IHF1ZXVlW3FzKytdOwogICAgICAgICAgICAgIDxiPmlmPC9iPiAobiAhPSBudWxsKSB7CiAgICAgICAgICAgICAgICAgIDxiPmlmPC9iPiAobi5sZWZ0ICE9IG51bGwpIHF1ZXVlW3FlKytdID0gbi5sZWZ0OwogICAgICAgICAgICAgICAgICA8Yj5pZjwvYj4gKG4ucmlnaHQgIT0gbnVsbCkgcXVldWVbcWUrK10gPSBuLnJpZ2h0OwogICAgICAgICAgICAgIH0KICAgICAgICAgIH0KICAgICAgfQogICAgICBOb2RlW10gbGV2ZWwgPSA8Yj5uZXc8L2I+IE5vZGVbXSB7IHJvb3QgfTsKICAgICAgaW50IG5vZGVXaWR0aCA9IDY7CiAgICAgIDxiPmZvcjwvYj4gKGludCBsID0gMDsgbCAmbHQ7IGhlaWdodDsgbCsrKSB7CiAgICAgICAgICBpbnQgc3BhY2VzID0gKGludCkgTWF0aC5wb3coMiwgaGVpZ2h0IC0gbCAtIDEpIC0gMTsKICAgICAgICAgIGludCBsZWFkaW5nID0gc3BhY2VzICogbm9kZVdpZHRoOwogICAgICAgICAgaW50IGJldHdlZW4gPSAoc3BhY2VzICogMiArIDEpICogbm9kZVdpZHRoOwogICAgICAgICAgPGI+Zm9yPC9iPiAoaW50IGkgPSAwOyBpICZsdDsgbGVhZGluZzsgaSsrKSBTeXN0ZW0ub3V0LnByaW50KCIgIik7CiAgICAgICAgICBOb2RlW10gbmV4dCA9IDxiPm5ldzwvYj4gTm9kZVtsZXZlbC5sZW5ndGggKiAyXTsKICAgICAgICAgIDxiPmZvcjwvYj4gKGludCBpID0gMDsgaSAmbHQ7IGxldmVsLmxlbmd0aDsgaSsrKSB7CiAgICAgICAgICAgICAgTm9kZSBuID0gbGV2ZWxbaV07CiAgICAgICAgICAgICAgPGI+aWY8L2I+IChuID09IG51bGwpIHsKICAgICAgICAgICAgICAgICAgPGI+Zm9yPC9iPiAoaW50IHMgPSAwOyBzICZsdDsgbm9kZVdpZHRoOyBzKyspIFN5c3RlbS5vdXQucHJpbnQoIiAiKTsKICAgICAgICAgICAgICAgICAgbmV4dFsyICogaV0gPSBudWxsOwogICAgICAgICAgICAgICAgICBuZXh0WzIgKiBpICsgMV0gPSBudWxsOwogICAgICAgICAgICAgIH0gPGI+ZWxzZTwvYj4gewogICAgICAgICAgICAgICAgICBTeXN0ZW0ub3V0LnByaW50KCJbIiArIG4ua2V5ICsgIl0iKTsKICAgICAgICAgICAgICAgICAgbmV4dFsyICogaV0gPSBuLmxlZnQ7CiAgICAgICAgICAgICAgICAgIG5leHRbMiAqIGkgKyAxXSA9IG4ucmlnaHQ7CiAgICAgICAgICAgICAgfQogICAgICAgICAgICAgIDxiPmZvcjwvYj4gKGludCBzID0gMDsgcyAmbHQ7IGJldHdlZW47IHMrKykgU3lzdGVtLm91dC5wcmludCgiICIpOwogICAgICAgICAgfQogICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCk7CiAgICAgICAgICBsZXZlbCA9IG5leHQ7CiAgICAgIH0KICB9Cgp9Cg==

Definition 2. Ausgabeformat der print Methode für einen Binärbaum. Bei den Abständen (Leerraum und Positionierung der Knotenschlüssel) wird immer von einem balanziertn Baum der Höhe H ausgegangen. H ist hier die tatsächliche Höhe. Bei einem nicht balanzierten Baum bleiben Positionen leer. Der minimale Abstand zwischen Klammerpaaren sind zwei Leerzeichen. 
                       [10]
                [2]           [11]
            [1]     [5]  [20]      [30]

Aufgabe 5. Erstelle eine Tabelle mit allen Nobelpreisträgern wo die Jahreszahl (letze beiden Jahreszahlen) eine Primzahl darstellen, also z.B. 1907, 2013. Die Daten finden sich unter https://de.wikipedia.org/wiki/Liste_der_Nobelpreistr%C3%A4ger.

Datentabellen Klasse (websh0) 

PGI+aW1wb3J0PC9iPiBqYXZhLmxhbmcuKjsKPGI+aW1wb3J0PC9iPiB1ai5sYW5nLio7CnB1YmxpYyA8Yj5jbGFzczwvYj4gRGF0YVRhYmxlcyB7CiAgc3RhdGljIFN0cmluZ1tdIG5hbWVzID0gewogICAgIlJvZW50Z2VuIiwKICAgICJCZWNxdWVyZWwiLAogICAgIk1pY2hlbHNvbiIsCiAgICAiV2llbiIsCiAgICAiT25uZXMiLAogICAgIkJhcmtsYSIsCiAgICAiU3RhcmsiLAogICAgIk1pbGxpa2FuIiwKICAgICJkZUJyb2dsaWUiLAogICAgIkRhdmlzc29uIiwKICAgICJTdGVybiIsCiAgICAiQXBwbGV0b24iLAogICAgIlplcm5pa2UiLAogICAgIlNlZ3JlIiwKICAgICJIb2ZzdGFkdGVyIiwKICAgICJCZXRoZSIsCiAgICAiR2Fib3IiLAogICAgIkVzYWtpIiwKICAgICJDcm9uaW4iLAogICAgIkNoYW5kcmFzZWtoYXIiLAogICAgIkxlZGVybWFuIiwKICAgICJDaHUiLAogICAgIkFicmlrb3NvdiIsCiAgICAiUGVybG11dHRlciIsCiAgICAiU3RyaWNrbGFuZCIsCiAgICAiUGVlYmxlcyIsCiAgICAiQWdvc3RpbmkiCiAgfTsKCiAgc3RhdGljIGludFtdIHllYXJzID0gewogICAgMTkwMSwKICAgIDE5MDMsCiAgICAxOTA3LAogICAgMTkxMSwKICAgIDE5MTMsCiAgICAxOTE3LAogICAgMTkxOSwKICAgIDE5MjMsCiAgICAxOTI5LAogICAgMTkzNywKICAgIDE5NDMsCiAgICAxOTQ3LAogICAgMTk1MywKICAgIDE5NTksCiAgICAxOTYxLAogICAgMTk2NywKICAgIDE5NzEsCiAgICAxOTczLAogICAgMTk3OSwKICAgIDE5ODMsCiAgICAxOTg5LAogICAgMTk5NywKICAgIDIwMDMsCiAgICAyMDExLAogICAgMjAxNywKICAgIDIwMTksCiAgICAyMDIzCiAgfTsKCn0=

Aufgabe 6. Teste nun die Implementierung mit nachfolgenden Beispielen. Da die Datentabellen vermutlich aufsteigend nach dem Schlüssel sortiert sind sollen die Datensätze randomisiert eingeführt werden. Dazu soll randomisiert ein Index der Datentabelle (names,years) ausgewählt werden. Das Problem: Ein Datensatz darf nicht zweimal eingefügt werden. Suche nach einer Lösung! Teste den Baum indem alle Datensätze gesucht werden und der Schlüssel und der ermittelte Knoten verglichen werden. Anschliessend werden die Knoten mit den Jahren 1903, 1913, 2003 und 2013 entfernt. Teste nochamls auf Korrektheit des Baums.

Test (websh0)

Test der Klasse Baumstruktur Tree. Ausführung von make (Linux, Mac) oder makew (Windows) und run. (websh0)
Type help or hit TAB for a list of commands.

PGI+aW1wb3J0PC9iPiBqYXZhLmxhbmcuKjsKPGI+aW1wb3J0PC9iPiB1ai5sYW5nLio7CgpwdWJsaWMgPGI+Y2xhc3M8L2I+IFRlc3QgewogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oKSB7CiAgICAgICAgVHJlZSB0ID0gPGI+bmV3PC9iPiBUcmVlKCk7CiAgICAgICAgaW50IG4gPSBEYXRhVGFibGVzLm5hbWVzLmxlbmd0aDsKCiAgICAgICAgaW50W10gaW5kaWNlcyA9IDxiPm5ldzwvYj4gaW50W25dOwogICAgICAgIDxiPmZvcjwvYj4gKGludCBpID0gMDsgaSAmbHQ7IG47IGkrKykgaW5kaWNlc1tpXSA9IGk7CgogICAgICAgIDxiPmZvcjwvYj4gKGludCBpID0gbiAtIDE7IGkgJmd0OyAwOyBpLS0pIHsKICAgICAgICAgICAgaW50IGogPSAoaW50KShNYXRoLnJhbmRvbSgpICogKGkgKyAxKSk7IAogICAgICAgICAgICBpbnQgdGVtcCA9IGluZGljZXNbaV07CiAgICAgICAgICAgIGluZGljZXNbaV0gPSBpbmRpY2VzW2pdOwogICAgICAgICAgICBpbmRpY2VzW2pdID0gdGVtcDsKICAgICAgICB9CgogICAgICAgIDxiPmZvcjwvYj4gKGludCBpID0gMDsgaSAmbHQ7IG47IGkrKykgewogICAgICAgICAgICBpbnQgaWR4ID0gaW5kaWNlc1tpXTsKICAgICAgICAgICAgdC5pbnNlcnQoRGF0YVRhYmxlcy5uYW1lc1tpZHhdLCBEYXRhVGFibGVzLnllYXJzW2lkeF0pOwogICAgICAgIH0KCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJCYXVtIG5hY2ggenVmYWVsbGlnZW0gRWluZnVlZ2VuOiIpOwogICAgICAgIC8vPGk+dC5wcmludCgpOzwvaT4KCgogICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiVWViZXJwcnVlZnVuZyBhbGxlciBEYXRlbnNhZXR6ZToiKTsKICAgICAgICA8Yj5mb3I8L2I+IChpbnQgaSA9IDA7IGkgJmx0OyBuOyBpKyspIHsKICAgICAgICAgICAgTm9kZSBub2RlID0gdC5zZWFyY2goRGF0YVRhYmxlcy55ZWFyc1tpXSk7CiAgICAgICAgICAgIFN5c3RlbS5vdXQucHJpbnRsbigiR2VmdW5kZW46ICIgKyBub2RlLmtleSArICIgLSZndDsgIiArIG5vZGUuZGF0YSk7CiAgICAgICAgfQoKICAgICAgICBpbnRbXSB5ZWFyc1RvUmVtb3ZlID0gezE5MDMsIDE5MTMsIDIwMDMsIDIwMTN9OwogICAgICAgIDxiPmZvcjwvYj4gKGludCB5ZWFyIDogeWVhcnNUb1JlbW92ZSkgewogICAgICAgICAgICB0LnJlbW92ZSh5ZWFyKTsKICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJFbnRmZXJudDogIiArIHllYXIpOwogICAgICAgIH0KCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJCYXVtIG5hY2ggRW50ZmVybmVuIGJlc3RpbW10ZXIgSmFocmU6Iik7CiAgICAgICAgLy88aT50LnByaW50KCk7PC9pPgoKCiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJVZWJlcnBydWVmdW5nIGFsbGVyIERhdGVuc2FldHplIG5hY2ggRW50ZmVybmVuOiIpOwogICAgICAgIDxiPmZvcjwvYj4gKGludCBpID0gMDsgaSAmbHQ7IG47IGkrKykgewogICAgICAgICAgICBOb2RlIG5vZGUgPSB0LnNlYXJjaChEYXRhVGFibGVzLnllYXJzW2ldKTsKICAgICAgICAgICAgPGI+aWY8L2I+IChub2RlPT1udWxsKSB7CiAgICAgICAgICAgIAlTeXN0ZW0ub3V0LnByaW50bG4oIkZlaGx0OiAiICsgRGF0YVRhYmxlcy55ZWFyc1tpXSk7CiAgICAgICAgICAgICAgICA8Yj5jb250aW51ZTwvYj47CiAgICAgICAgICAgIH0KICAgICAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKCJHZWZ1bmRlbjogIiArIG5vZGUua2V5ICsgIiAtJmd0OyAiICsgbm9kZS5kYXRhKTsKICAgICAgICB9CiAgICB9Cgp9

Aufgabe 7. Untersuche die Laufzeit für das Einfügen (in VM Ops) und das Suchen nach einem zufällig ausgewählten Schlüssel. Füge die Knoten in randomisierter Reihenfolge eine und teste (und messe) für N=10 Versuche. Wie groß ist die Streuung? Korreliert die VM Ops Zahl mit der theoretischen Kompliextätskalsse für das Suchen? Gebe diese an.



Hilfe


Created by the NoteBook Compiler Ver. 1.41.3 (c) Dr. Stefan Bosse (Mon Jan 26 2026 12:34:23 GMT+0100 (Central European Standard Time))