Höhe von B-Baum bestimmen

S

starbug

Erfahrenes Mitglied
Hallo ich hab noch ne Frage zu Bäumen, hab davon leider echt nicht viel Ahnung. Jedenfalls hab ich noch ne Aufgabe in der es darum geht zu prüfen ob das Level eines B-Baums korrekt ist. Hier hab ich mal den Code Schnipsel

Code: 
// Gibt die Höhe des Baums zurück, wenn sich alle Blätter
	// auf demselben Niveau befinden, ansonsten -1.
	// Das Kriterium eines B-Baums, dass alle Blätter
	// denselben Abstand zur Wurzel haben sollen ist also
	// erfüllt, wenn ein Wert >= 0 zurückgegeben wird.

	public static int levelsOK(BNode node)
	{ 
		
	}

Natürlich soll die methode wieder rekursiv aufgerufen werden. Ich weiss diesmal aber leider gar nicht wo ich anfangen soll. Bin für Tipps wie immer sehr dankbar.
 
Ich würde es etwa so versuchen:

Java: 
//Tiefe des ersten Knotens muss 1 sein
public static int getTreeDepth(BNode node, int actualDepth)
{ 
	if(node.getLeft() == null && node.getRight() == null) //Blatt gefunden, gib' Länge des Zweiges zurück
	{
		return actualDepth;
	}
	else
	{
		int leftDepth = (node.getLeft() != null) ? getTreeDepth(node.getLeft(), actualDepth + 1) : actualDepth;
		int rightDepth = (node.getRight() != null) ? getTreeDepth(node.getRight(), actualDepth + 1) : actualDepth;
		return (rightDepth > leftDepth) ? rightDepth : leftDepth;
	}
}
 
Zuletzt bearbeitet:
Das sieht eigentlich ganz gut aus, aber ich darf bei der Methode keinen weiteren Paramater mehr einfügen. Das is ja bei mir das Problem weshalb ich da auf keine Lösung komme.
 
Doch es geht. Ich poste die Lösung mach so, dass sie nicht direkt lesbar ist. Mit makieren des Quelltexts kannst du sie dir dann ansehen.


Code: 
public static int levelsOK(BNode node)
{
    BNode left = node.getLeft();
    BNode right = node.getRight();
    if(left == null && right == null) {
        return 1;
    }
    if(left == null && right != null) {
        return -1
    }
    if(left != null && right == null) {
        return -1;
    }
    
    int depthL = levelsOK(left) + 1;
    int depthR = levelsOK(right) + 1;
    
    return depthL == depthR ? depthL : -1;
}
 
Zuletzt bearbeitet:
Ich meine tatsächlich B-Bäume.

@ technoblade, ich werde mir den Code heute morgen mal angucken. Hoffentlich komm ich damit weite :)
 
Ohh, das mit dem BBaum war mir nicht bewusst, dachte das B stünde für binär.
Aber der Algorithmus lässt sich ja leicht auf Bäume mit jeweils n-Kindknoten übertragen.
Ich gehe mal davon aus, dass über BNode immer ein Array mit der Liste der Kindknoten. Wie ich in Wikipedia gelesen habe ist die Länge dieser Array durch das Level bestimmt. Daher gehe ich davon aus, dass das Array
immer die angepasste Größe hast, also in dem Fall, dass der Baum nicht ausgeglichen ist die Felder mit null gefüllt werden. Sollte also der Baum nach unten hin zuende sein sind alle Felder auf null gesetzt. Abhängig von einer ggf. etwas anderen Implementierung der BNode-Klasse muss der Algorithmus natürlich angepasst werden.


Code: 
public static int levelsOK(BNode node)
{
    BNode[] childs = node.getChilds();
    boolean nul = childs[0] == null;
    for(int i = 1; i < childs.length; i++) {
        if((childs[i] == null) != nul) {
            return -1;
        }
    }
    if(nul) {
        return 1;
    }

    int depth = levelsOK(childs[0]);
    for(int i = 1; i < childs.length; i++) {
        int tmp = levelsOK(childs[i]);
        if(tmp != depth) {
            return -1;
        }
    }
    
    return depth;
}
 
Zuletzt bearbeitet:
ich komm trotzdem nicht weiter. ich kann euch ja hier mal die kompletten klassen zeigen

1. Klasse BNode:


Code: 
public class BNode
{
	// Ordnung des B-Baums
	public static final int order = 2;
	
	// Nächstkleinerer Schlüssel im Elternknoten
	// (zum Prüfen auf korrekte Sortiereigenschaft).
	// Gibt es den nicht, ist dieser Wert mit dem kleinsten
	// int-Wert zu belegen.
	// Vereinfacht u.a. die Methode 'getChild'.
	protected int leftmostKey;
	
	// Feld für die Kinder / Nachfolger der Schlüssel im Knoten.
	// Den linken Nachfolger des Schlüssels keys[i] findet man in
	// children[i], den rechten Nachfolger in children[i+1];
	// dieser ist gleichzeitig der linke Nachfolger von keys[i+1].
	protected BNode children[] = new BNode[order*2+1];
	
	// Feld für die im Knoten zu speichernden Schlüssel.
	// Der erste Schlüssel wird an Position 0 gespeichert.
	// Das Element hinter dem letzten Nutzschlüssel im
	// Feld ist reserviert zum Eintragen des rechten Nachfolgers
	// des letzten Nutzschlüssels über 'addNode'. Der dort mit-
	// gegebene 'Dummy-Schlüssel' ist mit dem größten int-Wert zu belegen.
	protected int keys[] = new int[order*2+1];
	
	// Anzahl der im Knoten gespeicherten Schlüssel inklusive des
	// ggf. gespeicherten 'Dummy-Schlüssels' am Ende von keys[].
	// Gleichzeitig Anzahl der Nachfolger des B-Baum-Knotens.
	protected int cKeys;
	
	public BNode(int leftmostKey)
	{
		this.leftmostKey = leftmostKey;
	}
	
	// Gibt die Anzahl der Nachfolger des B-Baum-Knotens zurück.
	public int getChildCount()
	{
		return cKeys;
	}
	
	// Gibt den Schlüssel an Position 'no' im Attribut right von Child
	// zurück sowie den nächstkleineren Schlüssel im Attribut left.
	// Gibt es keinen nächstkleineren Schlüssel, wird leftmostKey zurückgegeben.
	// Zusätzlich zu den Schlüsselwerten wird der linke Nachfolger des 
	// Schlüssels an Position 'no' zurückgegeben.
	// Die Methode kann zum Baumdurchlauf verwendet werden.
	public Child getChild(int no)
	{
		if (no >= cKeys)
			return null;
			
		Child c = new Child();
		c.left = (no==0) ? leftmostKey : keys[no-1];
		c.right = keys[no];
		c.leftChild = children[no];
		
		return c;
	}
	
	// Fügt einen neuen Schlüssel zusammen mit dessen
	// linkem Nachfolger (Kind) ein.
	public void addNode(BNode leftChild, int newKey)
	{
		if (cKeys<=order*2)
		{
			children[cKeys] = leftChild;
			this.keys[cKeys++] = newKey;		
		}
	}
}

Code: 
2. Klasse Child

public class Child
{
	// In Bezug auf den aktuell betrachteten Schlüssel
	// in einem B-Baumknoten wird hier der nächstkeinere Schlüssel
	// gespeichert.
	public int left;
	
	// Schlüsselwert des aktuell betrachteten Schlüssels
	// in einem B-Baumknoten.
	public int right;
	
	// Linker Nachfolger des aktuell betrachteten Schlüssels
	// in einem B-Baumknoten.
	public BNode leftChild;
}

und 3 3.Klasse BTrees


Code: 
public class BTrees
{
	// Konstanten für 'Dummy-Schlüssel'
	private static final int minInt = Integer.MIN_VALUE;
	private static final int maxInt = Integer.MAX_VALUE;;
	
	// Durchläuft den B-Baum in Inorder-Reihenfolge, gibt also
	// bei bzgl. der Sortierung korrekt aufgebautem B-Baum die 
	// gespeicherten Schlüssel in aufsteigend sortierter Reihenfolge aus. 
	// Diese Methodenimplementierung soll Ihnen als Beispiel dienen.
	public static void traverseInOrder(BNode node)
	{
		if (node != null)
			for (int i = 0; i < node.getChildCount(); i++)
			{
				Child c = node.getChild(i);
				traverseInOrder(c.leftChild);
				if (i < 4)
					System.out.print(c.right+" ");
			}
	}
	
	// Gibt die Höhe des Baums zurück, wenn sich alle Blätter
	// auf demselben Niveau befinden, ansonsten -1.
	// Das Kriterium eines B-Baums, dass alle Blätter
	// denselben Abstand zur Wurzel haben sollen ist also
	// erfüllt, wenn ein Wert >= 0 zurückgegeben wird.
	public static int levelsOK(BNode node)
	{ 
		// ToDo
	}
	
	// Prüft, ob der B-Baum den Sortierkriterien genügt, d.h., ob
	// die folgenden zwei Kriterien erfüllt sind
	// 1) Die Schlüssel innerhalb eines Knotens sind aufsteigend sortiert.
	// 2) Für jeden Schlüssel s innerhalb eines Knotens gilt, dass
	//    alle Schlüssel im Teilbaum seines linken Nachfolgers kleiner
	//    sind als s und alle Schlüssel im Teilbaum seines rechten 
	//    Nachfolgers größer sind als s.
	// ACHTUNG: Zur Realisierung dürfen Sie die Methode 'traverseInOrder'
	//          NICHT verwenden!
	public static boolean isSorted(BNode node, int left, int right)
	{
		// ToDo
	}
	
	public static void main(String[] args)
    {
    	BNode trees[] = new BNode[4];
    	
    	// Baum 0 aufbauen
    	// Anlegen der Blätter
    	BNode tmp01 = new BNode(minInt);
    	tmp01.addNode(null, 1);
    	tmp01.addNode(null, 3);
    	BNode tmp02 = new BNode(4);
    	tmp02.addNode(null, 5);
    	BNode tmp03 = new BNode(9);
    	tmp03.addNode(null, 11);
    	tmp03.addNode(null, 12);
    	BNode tmp04 = new BNode(13);
    	tmp04.addNode(null, 14);
    	tmp04.addNode(null, 15);
    	tmp04.addNode(null, 16);
    	BNode tmp05 = new BNode(17);
    	tmp05.addNode(null, 20);
    	tmp05.addNode(null, 22);
    	tmp05.addNode(null, 30);
    	tmp05.addNode(null, 59);
    	
    	// Wurzel erzeugen und Schlüssel mit Nachfolgern
    	// hinzufügen
    	trees[0] = new BNode(minInt);
    	trees[0].addNode(tmp01, 4);
    	trees[0].addNode(tmp02, 9);
    	trees[0].addNode(tmp03, 13);
    	trees[0].addNode(tmp04, 17);
    	// addNode(tmp05, maxInt) speichert den rechten Nachfolger 
    	// des letzten Nutzschlüssels 17. Da für addNode immer auch 
    	// ein Schlüsselwert übergeben werden muss, wird hier der
    	// 'Dummy-Schlüssel' maxInt übergeben.
    	trees[0].addNode(tmp05, maxInt);
    	
    	// Baum 1 (s.o.)
    	BNode tmp11 = new BNode(minInt);
    	tmp11.addNode(null, 1);
    	tmp11.addNode(null, 3);
    	tmp11.addNode(null, 7);
    	BNode tmp12 = new BNode(9);
    	tmp12.addNode(null, 11);
    	tmp12.addNode(null, 12);
    	tmp12.addNode(null, 14);
    	BNode tmp13 = new BNode(minInt);
    	tmp13.addNode(tmp11, 9);
    	tmp13.addNode(tmp12, 15);
    	BNode tmp14 = new BNode(25);
    	tmp14.addNode(null, 30);
    	trees[1] = new BNode(minInt);
    	trees[1].addNode(tmp13, 25);
    	trees[1].addNode(tmp14, maxInt);
    	
    	// Baum 2
    	BNode tmp21 = new BNode(minInt);
    	tmp21.addNode(null, 1);
    	tmp21.addNode(null, 3);
    	tmp21.addNode(null, 5);
    	BNode tmp22 = new BNode(4);
    	tmp22.addNode(null, 5);
    	tmp22.addNode(null, 8);
    	BNode tmp23 = new BNode(9);
    	tmp23.addNode(null, 11);
    	tmp23.addNode(null, 12);
    	BNode tmp24 = new BNode(13);
    	tmp24.addNode(null, 14);
    	tmp24.addNode(null, 16);
    	trees[2] = new BNode(minInt);
    	trees[2].addNode(tmp21, 4);
    	trees[2].addNode(tmp22, 9);
    	trees[2].addNode(tmp23, 13);
    	trees[2].addNode(tmp24, maxInt);
    	
    	// trees[3] ist ein leerer B-Baum
    	
    	// Beispiel
    	System.out.println("Beispielausgabe Traversierung:");
    	traverseInOrder(trees[0]);
    	System.out.println("\n");
    	
    	// Tests
    	System.out.println("Baum Nr.\tAlle Blätter auf einem Niveau?\tSortierung ok?");
    	for (int i = 0; i < trees.length; i++)
    		System.out.println(i + "\t\t\t\t\t" + (levelsOK(trees[i])==-1 ? "nein" : "ja  ") +
    			                   "\t\t\t\t\t" + (isSorted(trees[i], minInt, maxInt) ? "ja" : "nein"));
    }
}

wie ihr sehen könnt muss ich da sogar 2 Aufgaben lösen aber ich bekomme nich mal die mit dem Level hin :-(
 
Hmm, hast recht genodeftest, könnte den Quelltext eig. auch sichtbar, posten war nur so gedacht, weil es ja eig. seine Aufgabe ist.

Also mal zu der Idee des Algorithmus:
Zuerst wird überprüft, auch die passende Anzahl an Kindknoten zu dem aktuellen Knoten vorhanden ist, sollte einer fehlen wird sofort -1 zurückgegeben.
Sollte es keine Kindknoten geben gibt man 1 zurück, da der aktuelle Knoten dann ja das Ende des Baums ist, es wird also nur diese eine Ebene als Tiefe gezählt.

Sollte die passende Anzahl an Kindknoten vorhanden sein, wird die Methode mit jedem der Kindknoten nochmals aufgerufen. liefern alle den selben Wert zurück (gehen also alle gleich weit tiefer), wird diese Tiefe +1, für das Level selber, zurückgegeben.

Konkret für diese implementierung kann ich den Algorithmus nicht liefern, da ich mich dafür erst da reindenken muss.
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück