Föreläsning 12: Mer om binärträd

Ett binärt sökträd är sorterat från vänster till höger i storleksordning (om det innehåller tal) eller i bokstavsordning (om det innehåller ord). Vi såg förut hur man kunde skriva ut trädet från vänster till höger (kallas inordning) med en enkel rekursiv metod. Nu ska vi se hur sökning efter ett visst tal går till.

Sökning i binärträd

All sökning utgår från roten och man kan tänka sej att man först sätter pekfingret på rottalet. Det sökta talet jämförs med pekfingertalet och då är tre fall möjliga: Om man med satsen if (exists(17))... vill kunna kolla om talet 17 finns i trädet kan man programmera exists() så här:
boolean exists(int value) {
    // Börja titta från rotnoden...
    return exists(value, root);
}

boolean exists(int value, BinNode node) {
    while (node != null) {
	if (value < node.value) 
	    node = node.left;
	else if (value > node.value)
	    node = node.right;
	else 
	    return true;
    }
    return false;
}

Om trädet är balanserat blir det inte så många tal man behöver jämföra med innan man kommit längst ner i trädet. Med N poster i trädet blir det cirka logN jämförelser, så som visades i föreläsning 11.

Att deklarera metoden som static går bra om man vill ha ett enda binärträd som existerar under hela körningen. Bäst är dock att låta bli att skriva static för att med new BinTree() kunna skapa hur många binärträd som helst just när man behöver dem.

Insättning i binärträd

Insättning av ett nytt tal i trädet går egentligen till på samma sätt som sökningen. Man söker efter talet och om man finner det skriver man bara ut att det är en dubblett. Men om man längst ner i trädet utan att ha funnit talet, dvs man står vid en null-referens, skapar man en ny post med det nya talet i och låter den forna null-referensen referera till den nya posten i stället.

Ett avsnitt ur koden för insert() ska alltså se ut så här:

    if (node == null) {
	node = new BinNode(value);
	return node;
    }


Här returnerar metoden en pekare till den nya posten. Om trädet är tomt tidigare ska pekaren root peka på den nya ensamma posten, därför måste det någonstans finnas ett anrop

root = insert(talet, root);

Hela insert() blir:
BinNode insert(int value, BinNode node) {
    if (node == null) {
	node = new BinNode(value);
	return node;
    }
    
    if (value < node.value)
	node.left = insert(value, node.left);
    else if (value > node.value) 
	node.right = insert(value, node.right);
    else 
	System.out.println("Dubblett: " + talet);
    
    return node;
}

Det står BinNode insert(...) eftersom metoden returnerar typen BinNode, nämligen en referens till toppnoden (roten) i det träd där det nya talet har stoppats in.

Privatsaker och publika metoder

Vår binärträdsklass blev så bra att vi vill låta alla andra javaklasser använda den. Vår lilla klass TestTree kan till exempel göra anrop av typen
    BinTree tree = new BinTree();
    tree.insert(17);
    tree.write();
    n = tree.nElements();    
    if (tree.exists(4711)) 
        ...
Notera att referensen root inte förekommer och att man inte från huvudprogrammet kan avläsa att det finns poster med left- och rightreferenser eller liknande. Man säger att binärträdet är abstrakt, och det är så man bör programmera. Genom att skriva private framför allt som har med referensvariabler att göra ser man till att ingen utomstående klass kan komma åt dessa privatsaker. För tydlighets skull skriver vi public på resten.

Liksom exists() bör även författaren tillhandahålla publika metoder där det anses lämpligt. Utan vettiga publika metoder kan till exempel kan inte en utomstående göra anropet insert(17). Nedan visas koden i sin helhet. Notera vilka delar som kan användas av utomstående (markerade public) och vilka delar som endast kan användas av metoder i klassen BinTree.

public class BinTree {
    private BinNode root;
    
    public BinTree() {
	root = null;
    }

    public boolean exists(int value) {
	// Börja titta från rotnoden...
	return exists(value, root);
    }
    
    private boolean exists(int value, BinNode node) {
	while (node != null) {
	    if (value < node.value) 
		node = node.left;
	    else if (value > node.value)
		node = node.right;
	    else 
		return true;
	}
	return false;
    }

    public void insert(int value) {
	root = insert(value, root);
    }

    private BinNode insert(int value, BinNode node) {
	if (node == null) {
	    node = new BinNode(value);
	    return node;
	}
	
	if (value < node.value)
	    node.left = insert(value, node.left);
	else if (value > node.value) 
	    node.right = insert(value, node.right);
	else 
	    System.out.println("Dubblett: " + value);
	
	return node;
    }

    public void write() {
	write(root);
    }

    private void write(BinNode node) {
	if (node == null)
	    return;
	write(node.left);
	System.out.println(node.value);
	write(node.right);
    }

    public int nElements() {
	return nElements(root);
    }

    private int nElements(BinNode node) {
	if (node == null) 
	    return 0;
	return nElements(node.left) + 1 + nElements(node.right);
    }
}

class BinNode {
    int value;
    BinNode left;
    BinNode right;
    
    BinNode(int v) {
	value = v;
	left = null;
	right = null;
    }
}

Testprogrammet kan se ut som följer:
class TestTree {
    public static void main(String[] args) {
	BinTree tree = new BinTree();

	System.out.print("Ange några tal: ");
	while (!Mio.eoln()) 
	    tree.insert(Mio.getInt());

	tree.write();
	System.out.println(tree.nElements() + " poster");
	Mio.getLine();

	System.out.print("Sök efter ett tal: ");
	if (tree.exists(Mio.getInt()))
	    System.out.println("OK!");
	else 
	    System.out.println("Fanns inte!");
    }
}

Att spara binärträd

Om man under körningen bygger upp ett bra binärträd vill man troligen spara trädet på fil till nästa körning. Den metod som ligger närmast till hands är att använda write(root), men med System.out utbytt mot utfil, så som beskrivits i föreläsning 4. Tyvärr kommer då trädposterna att ligga i ordning på filen, och det betyder att man får en långtarm ner åt höger när man senare bygger upp ett nytt träd från filen. Det riktiga är att skriva ut trädet i preordning på filen. Då kommer rotposten ut först på filen och blir därmed vid senare inläsning rotpost även i det nybyggda trädet. Några sekunders eftertanke övertygar en om att hela trädet kommer att bli så som det var vid förra körningen.

^ Upp till kurssidan.


Sidansvarig: <vahid@nada.kth.se>
Senast ändrad 30 september 2003
Tekniskt stöd: <webmaster@nada.kth.se>