Bäume Flashcards
(18 cards)
Tafelübung
Definitionen
balancierter Baum
Für jeden Teilbaum gilt: Die Höhe des
linken und des rechten Teilbaums
unterscheiden sich maximal um 1.
Tafelübung
Definitionen
voller Baum
Ein Binärbaum heißt voll, falls alle inneren Knoten den
Verzweigungsgrad zwei besitzen.
Tafelübung
Definitionen
vollständiger Baum
ein voller Baum dessen Blätter alle
dieselbe Ebene haben
Tafelübung
Binärer Suchbaum
Elementare Operationen
create: erzeugt einen neuen, leeren binären Suchbaum
makeTree: erzeugt aus einem linken und rechten Teilbaum und
einem Wert vom Typ T einen neuen Binärbaum
insert: fügt einen Wert vom Typ T in den Baum ein
find: überprüft, ob ein Wert vom Typ T im Baum vorhanden ist
delete: löscht einen Wert vom Typ T aus dem Baum
Tafelübung
Binärer Suchbaum
Laufzeit (vollständiger Baum)
Anzahl der Schritte = Höhe des Baums
Laufzeit O(log n)
(es muss ja nicht jeder Wert durchsucht werden)
Tafelübung
Binärer Suchbaum
Implementierung class TreeNode
private static class TreeNode {
public int value;
public TreeNode left;
public TreeNode right;
}
private TreeNode root;Tafelübung
Binärer Suchbaum
Implementierung iterativ Einfügen
TreeNode newNode = new TreeNode(value);
if (root == null) {
root = newNode;
return;
}
TreeNode node = root;
while (true) {
if (value < node.value) {
// links
if (node.left == null) {
node.left = newNode;
break;
}
node = node.left;
} else {
// analog für rechts
}
}
Tafelübung
Binärer Suchbaum
Anzahl knoten (rekursiv)
vorher if Statement, falls node == 0 return 0
return 1 + count(node.left) + count(node.right)
Tafelübung
Binärer Suchbaum
Anzahl knoten (rekursiv)
public int height(TreeNode node) {
// Abbruchfall
if (node == null ||
(node.left == null && node.right == null)) {
return 0;
}
// Rekursionsfall
return 1 + Math.max(height(node.left),
height(node.right));
}Tafelübung
Binärer Suchbaum
Größter Wert
größter Wert steht ganz rechts!
if (node.right == null) {
return node.value;
} else {
return max(node.right);
}
Tafelübung
Binärer Suchbaum
Traversieren von Bäumen
- Tiefensuche (Depth-First Search, DFS):
- Pre-Order
Wurzel – linker Teilbaum – rechter Teilbaum
- In-Order
linker Teilbaum – Wurzel – rechter Teilbaum
- Post-Order
linker Teilbaum – rechter Teilbaum – Wurzel - Breitensuche
erste Ebene – zweite Ebene – dritte Ebene – . . .
Tafelübung
Binärer Suchbaum
Laufzeit (worst case)
Komplexität O(n)
Dann wenn Binärbaum genau einen Strang hat.
Abhilfe AVL-Baum
Tafelübung
Binärer Suchbaum
Implementierung - Print der Knoten in in-Order Reihenfolge
public class Tree {
private int value;
private Tree left;
private Tree right;
/* ... */
public void print() {
if (left != null) {
left.print();
}
System.out.println(value);
if (right != null) {
right.print();
}
}
}KLAUSURAUFGABE WS 17
Welche Aussage(n) trifft/treffen auf binäre Bäume zu?
Binäre Bäume können unbalanciert sein, aber ein binärer Baum kann
unter keinen Umständen zu einer verketteten Liste werden.
Wenn ein binärer Baum post-order traversiert wird, werden die Einträge
immer in einer sortierten Reihenfolge zurückgegeben, unabhängig davon,
ob der Baum balanciert ist oder nicht.
Wenn ein binärer Baum pre-order traversiert wird, wird das Maximum
der Datenelemente immer zuletzt besucht.
eigene Lösung
1. falsch, wenn Binärbaum einen Strang hat wird er zur Liste
- falsch, da der rechte Teilbaum vor der Wurzel durchlaufen wird
- Richtig, da bei PreOrder von oben nach unten und links nach rechts gegangen wird
KLAUSURAUFGABE WS17 Sind die folgenden Aussagen zu Binärbäumen wahr oder falsch?
- „Jeder volle Baum ist gleichzeitig auch ein balancierter Baum.“
- „Jeder vollständige Baum ist gleichzeitig auch ein balancierter Baum. “
eigene Lösung
Baum kann “voll” aber nicht “balanciert” sein. Also alle Endebenen haben Blätter unterscheiden sich aber um teilweise mehr als 1 (Kriterium für balancierten Baum)
Ein vollständiger Baum ist ein voller Baum, bei dem alle Blätter auf der gleichen Ebene liegen. Dieser ist dann auch balanciert
KLAUSURAUFGABE WS15
Welche Aussage(n) trifft/treffen auf voll besetzte Binärbäume zu?
- Jeder Knoten außer der Wurzel hat 2 Vorgänger.
- Alle inneren Knoten haben den gleichen Verzweigungsgrad.
- Die Gesamtzahl der Knoten ist immer 2^h, wobei h die Höhe des Binärbaumes
ist. - Die Anzahl der Knoten der letzten besetzten Ebene ist eine 2er-Potenz.
- Die Anzahl der Knoten der letzten besetzten Ebene der Höhe h ist immer
2^h. - Die Anzahl der Blatt-Knoten des Binärbaumes der Höhe h ist 2^h
eigene Lösung
1. ja voll = überall blätter
- ja voll = alle 2 Blätter/Nachfolgeknoten
- falsch
- falsch, können auch 6 oder 10 sein
- falsch, da ja nicht alle knoten bis zur letzten Ebene gehen
- falsch
Welche Aussage(n) trit/treen auf vollständig besetzte Binärbäume zu?
- Jeder Knoten außer der Wurzel hat 2 Vorgänger.
- Alle inneren Knoten haben den gleichen Verzweigungsgrad.
- Die Gesamtzahl der Knoten ist immer 2^h, wobei h die Höhe des Baumes
ist. - Die Anzahl der Knoten der letzten besetzten Ebene ist eine 2er-Potenz.
- Die Anzahl der Knoten der letzten besetzten Ebene der Höhe h ist immer
2^h.
eigene Lösung
1. richtig
- richtig
- nein, immer 2^h +1
- richtig, weil vollständig: 2,4,8…
- richtig
KLAUSURAUFGABE SS15
Welche Aussage(n) trifft/treffen auf binäre Bäume zu?
- Binäre Bäume können unbalanciert sein, aber ein binärer Baum kann
unter keinen Umständen zu einer verketteten Liste werden. - Wenn ein binäre Baum postorder traversiert wird, werden die Einträge
immer in einer sortierten Reihenfolge zurückgegeben, unabhängig davon,
ob der Baum balanciert ist oder nicht. - Wenn ein binärer Baum präorder traversiert wird, wird das Maximum
der Datenelemente immer zuletzt besucht.
eigene Lösung
1. falsch, wenn Binärbaum einen Strang hat wird er zur Liste
- falsch, da der rechte Teilbaum vor der Wurzel durchlaufen wird
- Richtig, da bei PreOrder von oben nach unten und links nach rechts gegangen wird
