Hoofdstuk 2 Week 4: Datastructuren 2.1
Leesopdracht
In het hoorcollege komen lijsten en bomen aan de orde. De eerste datastructuur komt in het boek in bladzijden 317-333 aan de orde. In dit dictaat komt uitsluitend de theorie van bomen aan de orde.
2.2
Bomen
De lineaire lijst heeft als grote bezwaar, dat doorzoeken van de lijst evenredig toeneemt met de lengte van de lijst. In een twee keer zo lange lijst moeten over het algemeen twee keer zoveel element-vergelijkingen worden gedaan. Eerder hebben we een effici¨enter zoekalgoritme besproken, nl. binary search. Hiervoor is het nodig dat de gegevens geordend aanwezig zijn. Zelfs bij een geordende lijst is binary search echter onmogelijk omdat we het “midden van de lijst” niet zo eenvoudig kunnen vinden. We zouden graag een structuur willen hebben, die dat wel kan. Zo’n structuur is er, nl. de boomstructuur (in het Engels: tree).
2.3
Definitie
We kunnen de volgende definitie vinden in de literatuur: “Een boom bestaat uit een (eventueel lege) verzameling gerichte verbindingen tussen tweetallen punten. E´en punt, de zg. wortel (root), heeft geen inkomende verbindingen. Vanuit de wortel is elk ander punt van de boom op precies ´e´en manier langs de gerichte verbindingen bereikbaar. Een punt zonder uitgaande verbindingen wordt wel blad (leaf ) genoemd. Een willekeurig punt een knoop (node).” Evenals met lijsten het geval was, hebben we hier een recursieve structuur: wijzen we een willekeurig punt van de boom aan als wortel, dan is de onderliggende structuur 1
wederom een boom (en wel een subboom (subtree van de originele boom).
2.4
Binaire bomen
We zullen hier alleen binaire bomen behandelen, d.w.z. dat vanuit elk punt hooguit twee verwijzingen naar subbomen mogelijk zijn. We gaan dus een class SearchTree maken. E´en van de problemen waar we binnen een object ge¨orienteerde taal tegenaan kunnen lopen is dat we ook een lege boom als een object uit de class SearchTree willen beschouwen. Een lege boom is echter het handigst als een null referentie te beschouwen. Je kunt echter geen methods van een null referntie aanroepen. De handigste aanpak onder deze omstandigheden is om binnen de class SearchTree een private class TreeNode te maken. Deze bevat de eigenlijke boom structuur, terwijl de class SearchTree alleen de wortel van de boom (root die dus null mag zijn) bevat. Iedere method in SearchTree zal dus eerst controleren of de boom leeg is, zonodig zelf actie ondernemen om deze uitzondering te behandelen, en anders de overeenkomstige method uit de private class TreeNode aanroepen. Dit levert de volgende structuur: public class SearchTree { private class TreeNode { // Data private private private
fields Object info; TreeNode left; TreeNode right;
// Methods within TreeNode ........................... } // Data fields public TreeNode root; // Methods within SearchTree } Een voorbeeld van het gebruik van een boomstructuur vinden we in het opslaan van een rekenkundige expressie. Zo kunnen we de expressie: (a × b)/(c + (d − e)) 2
root node /
+
*
a
b
c
-
d
leaf
e
Figuur 2.1: Binaire boom voor (a × b)/(c + (d − e)). in een binaire boom opslaan zoals in aangegeven in figuur 2.1. Uit de boomstructuur volgt direkt de evaluatie volgorde, zodat haakjes overbodig worden. Net als bij lijsten is het ook bij bomen verstandig om niet direct de datastuctuur te manipuleren, maar om methods te gebruiken die de structuur manipuleren. Op deze wijze is het handhaven van de integriteit (correctheid) van de datastructuur een stuk gemakkelijker. Voor bomen met rekenkundige expressies defini¨eren we daarom de volgende constructor public TreeNode(Object obj, TreeNode leftnode, TreeNode rightnode) { info = obj; left = leftnode; right = rightnode; } De bovenstaande rekenkundige expressie kunnen we nu gemakkelijk construeren met: root = new TreeNode ( "/", new TreeNode ( "*", new TreeNode( "a"), new TreeNode( "b" ) ), new TreeNode ( ’+’, new TreeNode( "c" ), new TreeNode ( ’-’, new TreeNode( "d" ), new TreeNode( "e" ) ) 3
) );
2.5
Doorlopen van een binaire boom
Er bestaan in principe drie manieren om een boomstructuur te doorlopen: 1 ) • preorder - behandel eerst de wortel en dan resp. de linker- en rechter subboom. • inorder - behandel eerst de linker subboom, dan de wortel zelf en tot slot de rechter subboom. • postorder - behandel eerst de linker resp. rechter subboom en pas dan de wortel. In Java kunnen we bijvoorbeeld het in preorder, inorder of postorder doorlopen van een boom beschrijven alsvolgt: public preOrderDoSomething ( ) { info.doSomething(); if ( left != null ) left.preOrderDoSomething( ); if ( right != null ) right.preOrderDoSomething( ); } public inOrderDoSomething ( ) { if ( left != null ) left.inOrderDoSomething( ); info.doSomething(); if ( right != null ) right.inOrderDoSomething( ); }
1
) Pre- en postorder is ook te defini¨eren voor algemene bomen, inorder alleen voor binaire bomen
4
public postOrderDoSomething ( ) { if ( left != null ) left.postOrderDoSomething( ); if ( right != null ) right.postOrderDoSomething( ); info.doSomething(); }
Indien info.doSomething bestaat uit het afdrukken van het item, ontstaat de volgende uitvoer voor de hiervoor gegeven expressieboom: preorder: • /×ab+c−de inorder: • a×b/c+d−d postorder: • ab×/cde−+ Zowel de preorder als de postorder uitvoer van deze expressie zijn zonder ambigu¨ıteit te begrijpen. De overeenkomstige prefix, resp. postfix notatie 2 ) is dan ook zonder haakjes te gebruiken. De bij de inorder uitvoer behorende infix notatie heeft zo nu en dan haakjes nodig (of strikte prioriteitsregels) om ambiguiteit te voorkomen. De postfix notatie staat wel bekend als de omgekeerde Poolse notatie. 3 )
2.6
Geordende lijsten
Tot nog toe hebben we ons bij lijsten niet bekommerd om de volgorde van de elementen. Vaak willen we dat de elementen in een lijst in opklimmende grootte geordend zijn. We spreken dan van een geordende lijst. Voorwaarde is dat de objecten in de lijst Comparable zijn. De insert moet dan als volgt geimplementeerd worden:
2 ) Prefix-notatie: de operator voor de operanden, postfix: de operator achter de operanden en infix: de operator ertussen in (de laatste alleen voor binaire operatoren). 3 ) De notatie is bedacht door de Pool Lukasiewicz, maar wordt niet Lukasiewicz-notatie genoemd omdat de naam zo moeilijk uit te spreken en te onthouden is.
5
public void insertOrdered( Comparable e ) { ListIterator iter = this.listIterator(); while (iter.hasNext()) { if ( e.compareTo((Comparable) iter.next()) < 0 ) { if (iter.hasPrevious()) iter.previous(); break; } } iter.add(e); } Het nadeel van een geordende lijst is dat het toevoegen van een nieuw element aan de lijst wat meer rekentijd kost, maar het voordeel is dat een groot aantal bewerkingen minder tijd kosten. Bijvoorbeeld: • Minimum: het zoeken van het kleinste element kan in constante tijd O {N 0 }, immers dit element staat vooraan in de lijst. • Uniek: het verwijderen van doublures, elementen die twee of meer keren voorkomen, uit de lijst kost voor ongeordende lijsten O {N 2 } tijd en voor geordende lijsten O {N } tijd. • Gelijkheid: de gelijkheidstest van twee lijsten kan in orde O {N } tijd, voor ongeordende lijsten is minimaal O {N 2 } tijd nodig.
2.7
Een geordende boom
In de vorige paragraaf bleek, dat zelfs met een geordende lijst geen effici¨ent zoekalgoritme mogelijk is. Ook met een geordende lijst blijft een zoekalgoritme O {N }. We kunnen (onder bepaalde voorwaarden 4 )) laten zien, dat in een geordende boom een zoekalgoritme mogelijk is van O {log N }. Duizend keer zoveel elementen betekent nu log 1000 ≈ 10 keer zoveel zoekacties. Voorwaar een hele verbetering. We zullen nu eerst defini¨eren, wat we onder een geordende boom zullen verstaan. 5 ) We gaan hierbij uit van de ordeningsrelatie ≥. 4 ) Hierbij moet de boom gebalanceerd zijn. D.w.z. dat in elke knoop de subbomen hooguit ´e´en in diepte verschillen. Over balanceren van bomen zullen we hier niet spreken. We kunnen dus niet garanderen dat de zoekalgoritmen O {log N } zijn. 5 ) Een veel gebruikte term voor een geordende boom is search tree, zodat we kunnen zeggen dat “tree search needs search trees.”
6
Een boom heet geordend (m.b.t. ≥) als alle waarden in de knopen van de linkersubboom niet groter zijn dan de waarde in de wortel van t en de waarde in de wortel in niet groter is dan enige waarde van de knopen in de rechtersubboom. Bovendien zijn de linker- en rechtersubboom weer geordend. Zoeken in een boom kan nu vrij eenvoudig worden geprogrammeerd. Het algoritme vertoont enige verwantschap met binary search: ook hier wordt in elke stap het aantal te doorzoeken elementen gehalveerd, hetgeen in een O {log N } algoritme resulteert. De boom wordt nu vanaf de wortel doorlopen, en wel zodanig, dat in iedere knoop wordt beslist of de zoekactie in de linker- of de rechtersubboom moet worden voortgezet. Als resultaat levert searchItem een verwijzing naar de knoop waarin het gezochte element staat; echter als het element niet gevonden wordt levert searchItem de waarde null op. public static TreeNode searchItem( TreeNode tree,
Comparable e ){
//Pre : true //Post: searchItem = null || ( searchItem.info = e ) if (tree == null) return null;
// niets gevonden
else { int test = e.compareTo( (Comparable) tree.info); if (test == 0)
// als e == tree.info
return tree;
// raak !!
else if (test<0)
// als e < tree.info
return searchItem( tree.left, e);
// links zoeken
else return searchItem( tree.right, e);
// anders rechts zoeken
} }
2.8
Basisoperaties op binaire zoekbomen
De basisoperaties op bomen verschillen niet veel van de basisoperaties op geordende lijsten. Het is zelfs verstandig om de interfacing m.b.t. bomen zo veel mogelijk gelijk te kiezen aan 7
de interfacing m.b.t. geordende lijsten; immers we kunnen dan bomen en lijsten gebruiken als verschillende implementaties behorende bij dezelfde interface. • • • • • • • •
add - het toevoegen van een element in een binaire zoekboom. clone - het copieren van een binaire zoekboom. isEmpty - controle of de boom leeg is. join - het samenvoegen van twee binaire zoekbomen. remove - verwijder node uit boom. toString - het converteren naar een string. first - het kleinste element last - grootste element
Elementen toevoegen in een geordende boom kan eenvoudig worden uitgeschreven. We maken hiervoor gebruik van onderstaand schema: 1. Als de huidige boom leeg is, wordt het betreffende element als wortel in de huidige boom opgenomen. 2. Is de huidige boom niet leeg, dan wordt het probleem verplaatst naar de linker- of rechter subboom en wel: • naar links, indien het wortelelement kleiner is en • naar rechts, indien het wortelelement groter is dan het in te voegen element. • bij gelijkheid voegen we in dit geval het element niet toe en signaleren dit door als return-waarde false te geven. 6 ) Het schema resulteert in de method add: public boolean add( Object item ){ if ( isEmpty() ){ root = new TreeNode( item ); return true; } else return root.addNode( item ); } De recursie wordt afgehandeld door de add method binnen de private class TreeNode:
6
) Er zijn ook andere keuzes mogelijk als element gelijk is aan het wortelelement. We kiezen hier voor een methode die gelijk is aan die in standaard classes van Java.
8
public boolean addNode(Object item) { // Voegt een element aan de binaire zoekboom toe if ( info.compareTo(item) == 0 ){ return false; } else { if ( info.compareTo(item) > 0 ){ // item.key < root.key if ( left == null ){ left = new TreeNode(item); return true; // new item added } else return left.addNode(item); // insert in left tree } else { // item.key >= root.key if ( right == null ){ right = new TreeNode(item); return true; // new item added } else return right.addNode(item); // insert in left tree } } } Voor de implementatie van clone gebruiken we een dergelijke opsplitsing. De clone method van class SearchTree is
9
public SearchTree clone() { SearchTree t = new SearchTree(); if ( ! isEmpty() ) t.root = root.clone(); return t; }
Die van class TreeNode: public TreeNode clone(){ TreeNode t = new TreeNode( ((Cloneable)info).clone() ); if ( left != null ) t.left = left.clone(); if ( right != null ) t.right = right.clone(); return t; }
De method join voegt alle elementen van een zoekboom aan een andere zoekboom, die als parameter wordt meegegeven. Deze method volgt ook het voorgaande patroon. In SearchTree hebben we public void join( SearchTree t ){ // Combineer twee binaire zoekbomen if ( !isEmpty() ) root.join(t); } En in TreeNode:
10
public void join( SearchTree t ){ // Combineer twee binaire zoekbomen t.insert( (Comparable) info); if ( left != null ) left.join(t); if ( right != null ) right.join(t); } Bij de implementatie van join gebruiken we ´e´en van de mogelijke wijzen om een binaire boom te doorlopen. In ons geval hebben we gekozen voor de preorder methode; we hadden ook inorder of postorder kunnen gebruiken. De inorder methode heeft echter als bezwaar dat de boom t dan snel uit balans raakt.
2.9
Verwijderen van een knoop uit een boom
Het verwijderen van een element uit een boom is minder eenvoudig dan het toevoegen. Merk op, dat toevoeging altijd plaatsvindt aan de bladeren van de boom. Een element, dat moet worden verwijderd, hoeft echter niet een blad te zijn. Het kan zich ook “ergens middenin” bevinden. We onderscheiden een drietal gevallen: 1. Het te verwijderen element heeft geen opvolgers: (left == null) && (right == null) 2. Het te verwijderen element heeft precies ´e´en opvolger: (left == null) != (right == null) Met != implementeren we de exclusief of (XOR), waarbij A != B betekent dat A is waar of B is waar maar niet beiden. 3. Het te verwijderen element heeft twee opvolgers: (left != null) && (right != null) Het eerste geval is het eenvoudigst. De verwijzing wordt leeg gemaakt: result = null; en het element is verdwenen. In het tweede geval kunnen result laten wijzen naar de niet lege subboom, dus: if (right == null) 11
result = left; else result = right; (Vergelijk met het verwijderen van een element uit een lineaire lijst.) Het derde geval is zoals gezegd lastiger. Omdat ´e´en referentie onmogelijk naar twee elementen tegelijk kan wijzen; result zou nu zowel naar left als right moeten gaan wijzen. We moeten van de twee resterende subbomen weer ´e´en boom maken. Bij dit proces moeten we ervoor zorgen dat de ordeningsrelatie tussen de knopen gehandhaafd blijft. Het gemakkelijkste gaat dit als we uitgaan van ´e´en van de twee subbomen; dientengevolge zijn er twee mogelijke oplossingen: • we kiezen voor de linker subboom en hangen de rechter subboom onder de meest rechtse knoop of • we kiezen voor de rechter subboom en hangen de linker subboom onder de meest linkse knoop. De eerste variant leidt tot de code: p = left; while (p.right != null ) p=p.right; p.right := right; return left; We smeden dit alles aaneen tot ´e´en method: public TreeNode removeRoot(){ // Verwijder het root element uit een boom TreeNode p; if (left == null){ if (right == null) return null; else return tree^.right; } else { if (right == null) return left; 12
else { p = left; while (p.right != null ) p=p.right; p.right := right; return left; } } } In de practijk willen we echter een remove-methode in class SearchTree in staat is om een node met een bepaalde inhoud te verwijderen, als die bestaat. We moeten dus een verwijzing opzoeken naar de betreffende node. Die kunnen we dan beschouwen als de root van zijn eigen subboom, en vervangen de verwijzing naar de subboom door die naar de subboom minus de wortel. In class TreeNode krijgen we dan een removeNode die er als volgt uit ziet: public boolean removeNode(Object item) { if ( info.compareTo(item) > 0 ){ // item.key < root.key if ( left == null ){ return false; // no item removed } else { if (left.info.compareTo(item) == 0){ left = left.removeRoot(); return true; } else return left.removeNode(item); // remove from left tree } } else { // item.key >= root.key if ( right == null ){ return false; // no item removed } 13
else { if (right.info.compareTo(item) == 0){ right = right.removeRoot(); return true; } else return right.removeNode(item); // remove from left tree } } } Tot slot moet binnen de class SearchTree een method remove gemaakt worden die drie situaties aan moet kunnen: • de boom is leeg: dan geven we als return-waarde false. • het root-element is het gezochte element: dan roep je de removeRoot method van root aan. • in alle overige gevallen moet de removeNode method van root aangeroepen worden We krijgen dan: public boolean remove(Object target){ if (isEmpty()) return false; else { if (root.info.compareTo(target)==0){ root = root.removeRoot(); return false; } else return root.removeNode(target); } } Tot slot nog een methode die de som van elementen van een boom gevuld met Integers berekent. Weer is de som natuurlijk te schrijven als de som van de linker sub-boom, plus die van de rechter, plus de waarde van het huidige element. Wel moeten we controleren of de sub-bomen leeg zijn. In TreeNode hebben we dan:
14
public int sumInt(){ int sum = ((Number)info).intValue(); if (left != null) sum += left.sumInt(); if (right != null) sum += right.sumInt(); return sum; } Let op dat we eerst info casten naar een Number. En alternatief is: public int sumInt(){ return (left != null ? left.sumInt() : 0 ) + (right != null ? right.sumInt() : 0 ) + ((Number)info).intValue(); } Dit is compacter, maar je vindt het misschien minder leesbaar. Gebruik in dat geval de eerste aanpak. In SearchTree hebben we dan de method: public int sumInt(){ if (isEmpty()) return 0; else return root.sumInt(); }
15
2.10
Practicum 2 Week 4: Bomen
Opgave 1
(SearchTree)
Opgavenaam: SearchTree In te leveren file: SearchTree.java In deze opgave gaan we een aantal methods maken die binaire zoekbomen manipuleren. We plaatsen deze methods in een class SearchTree, die grotendeels beschikbaar staat in directory ~csg112/java/practicum2. Let op dat je in iedere opgave zowel in de private class TreeNode, als in SearchTree zelf iets moet veranderen. In dezelfde directory staat ook een file met de class TreeTest waarin een main methode staat die de door jullie gemaakte methods test. Ook staan er drie test files namen.txt, kruiden.txt en namensort.txt. Deze kun je als parameter meegeven bij aanroep van TreeTest. 1. Construeer een method int size() die het aantal elementen in een binaire zoekboom oplevert ZONDER dat de class SearchTree intern extra administratie gebruikt (deze opdracht wordt namelijk bijzonder flauw als je het aantal nodes intern in de class bij laat houden). 2. Construeer methods Object first() en Object last() die het kleinste resp. grootste element van een binaire zoekboom opleveren. 3. Construeer een method int depth() die de diepte van een een binaire zoekboom bepaald. De diepte is de maximale afstand tot de wortel van enige knoop. Voor een lege boom geldt derhalve depth = 0. 4. Construeer een method String toString() die alle elementen in een boom gesorteerd in een string zet, gescheiden door end-of-line characters (”\n”). Stel je hebt in de nodes van de boom de volgende strings: ”Nootmuskaat”, ”Geelwortel”, ”Dragon”, ”Jeneverbes”, ”Salie”, ”Peterselie”, ”Waterkers”, dan moet de uitvoer van toString() zijn: Dragon Geelwortel Jeneverbes Nootmuskaat Peterselie Salie Waterkers Als je alles goed hebt gedaan, en je TreeTest en SearchTree hebt vertaald, dan levert het commando
java TreeTest kruiden.txt
16
als uitvoer Aantal elementen Diepte Boom Theoretisch optimum Eerste element Laatste element
: : : : :
7 3 3.0 Dragon Waterkers
Gesorteerde lijst : Dragon Geelwortel Jeneverbes Nootmuskaat Peterselie Salie Waterkers Vergelijk ook even de output bij gebruik van namen.txt en namensort.txt. Het bovenste stukje van de uitvoer moet eruit zien als: Aantal elementen Diepte Boom Theoretisch optimum Eerste element Laatste element
: : : : :
31 5 5.0 Allard Zef
Gesorteerde lijst : ........... bij namen.txt, en bij namensort.txt krijg je: Aantal elementen Diepte Boom Theoretisch optimum Eerste element Laatste element
: : : : :
31 31 5.0 Allard Zef
Gesorteerde lijst : 17
...........
Opgave 2
(SpeedTest)
Opgavenaam: SpeedTest In te leveren file: SpeedTest.txt In deze opgave verwachten we niet dat je een programma instuurt, maar dat je een kort textfile met je bevindingen instuurt. Ook als de vorige opgave niet is gelukt, is het mogelijk deze te doen. We gebruiken nl. alleen de constructor en add methods uit SearchTree. De class SearchTree implementeerd een groot aantal methods van de standaard class TreeSet. Zoek in de Java documentatie de specificatie van deze class op. Let op dat men het heeft over een red-black balanced tree implementatie. In het file SpeedTest.java in dezelfde directory als SearchTree wordt de snelheid van het toevoegen van N elementen van class Integer aan de boom getest. Vertaal class SpeedTest, en run het met de volgende commando’s: java SpeedTest 5000 java SpeedTest 10000 java SpeedTest 20000 java SpeedTest 40000 Heb geduld, het duurt best lang. Vervang nu in SpeedTest alle verwijzingen naar class SearchTree door TreeSet. Vertaal SpeedTest opnieuw, en run de commando’s weer. Maak een tabel met de tijden als functie van N , voor beide tree-classes. Verklaar het verschil. HINT: let op de volgorde van invoegen. Geef aan de hand van de tijden van de SearchTree class een schatting van de complexiteit in O-notatie (let op hoe de tijd veranderd bij verdubbeling van N ).
18
