PI (Subject) / Bäume: Grundlagen und Begriffe (Lesson)
There are 10 cards in this lesson
Bäume: Grundlagen und Begriffe
This lesson was created by blace.
This lesson is not released for learning.
- Was ist ein Baum und welche Eigenschaften hat er? Ein Baum ist eine verallgemeinerte Liste, die bei jedem Knoten mehrere Nachfolger hat. Sie werden benutzt, da Arrays statisch (daher teuer bei Größenänderung) sind und Listen zwar dynamisch, aber sie können nur linear durchsucht werden.
- Welche Arten von Knoten gibt es in einem Baum? Es gibt Elternknoten, Kindknoten, Wurzeln und Blätter(Terminalknoten) Kindknoten, sind Nachfolger Elternknoten sind Vorgänger Wurzel ist ein Knoten ohne Vorgänger Blatt hat keinen Nachfolger
- Was ist die Ordnung eines Baums? Die ordnung beschreibt den Maximalen verzweigungsgrad des Baumes bei einem geordneten Baum sind die Nachfolger geordnet (erster, zweiter, dritter nachfolger)
- Wie ist die Tiefe eines Knotens in einem Baum definiert Die Tiefe eines Knotens ist sein Abstand zur Wurzel (Also die Anzahl an Kanten) Die Wurzel hat daher die Tiefe 0 Knoten mit gleicher Tiefe sind auf der gleichen Ebene (dem gleichen Niveau)
- Wie ist die Höhe eines Baums definiert? Die Höhe eines Baumes ist die maximal auftretende Tiefe innerhalb des Baumes
- Wann ist ein Baum ein voller Baum und wann ein vollständiger Baum? Ein voller Baum ist, wenn der Verzwigungsgrad aller inneren Knoten die Ordnung des Baumes ist. Ein vollständiger Baum ist, wenn die Tiefe aller Blätter der Höhe des Baumes entsprechen
- Was ist ein Binärbaum? Ein Binärbaum ist eine unterart der Baume, welche be jedem Knoten nur höchsten zwei Kindknoten haben kann, welche oft eindeutig in Links und rechts eingeteilt werden müssen. Bsp Ahnentafel
- Welche Eigenschaften hat ein vollständiger Binärbaum? Ein Vollständiger Binärbaum hat, wie ein normaler baum n Knoten und n-1 Kanten, aber Ein vollständiger Binärbaum mit der Höhe n hat 2^n Blätter - Wurzel: 1 Blatt blätter(n+1)= 2*blätter(n) 2^n+1 -1 Knoten - Wurzel: 1 Knoten knoten(n+1)= 2*knoten(n)+1
- Was ist ein binärer Suchbaum? Ein Suchbaum ist eine abstrakte Datenstruktur,bei welcher die Menge von Elementen in der gesucht werden soll in einer Baumstruktur dargstellt wird. Bei binären Sucbäumen enthäkt jeder Knoten einen Schlüssel und maximal zwei Teilbäume einen linkne und einen rechten, jeder Teilbaum ist auch ein binärer Suchbaum
- Welche Vor- und Nachteile haben binäre Suchbäume gegenüber Arrays, welche im Vergleich zu Listen, unter welchen Bedingungen? Vorteile gegenüber von Arrays sind, dass Arrays statisch sind und dadurch die Größenänderung bei Ihnen teuer ist, Suchbäume aber dynamisch sind. Und Listen sind zwar dynamisch, aber bieten nur eine lineare Suche an im Gegensatz zu den Suchbäumen.