AuD Übung Bäume (08)

Abgabe: 24.1.2025

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

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.

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

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

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

• Die Funktion searchMinimalElement gibt denjenigen Knoten eines (Teil)Baums zurück den den kleinsten Schlüssel enthält. Nur bei einem Elementarbaum ist das der Wurzelknoten.
• Die Funktion replaceNode ersetzt node mit child (und child muss ausgekoppelt werden).

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.

VEJB

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.).

VEJB

                       [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.

VEJB

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.

VEJB