Datastrukturer & Algoritmer, Datalogi C

ForelÊsning 29/10-2002

OHπer brugt ved forelÊsningen; sm rellelser 30/10-2002

TrÊer

En meget vigtig datastruktur

ReprÊsentation af sprog (i meget generel betydning), syntakstrÊer:

∑ Java (i en compiler), SQL (i et databasesystem), XML ....

∑ Naturligt sprog

S¯getrÊer:

∑ Generel reprÊsentation af (sorterede) mÊngder og funktioner

∑ Databasesystemer....

Dagens program:

∑ Hvad er et trÊ (datalogisk set)?

∑ Eksempel p syntakstrÊer udtrykt vha. nedarvning

NB: udenfor bogen; find Javafiler via kursets hjemmeside

∑ Java-stil implementation af generiske trÊer

Traversering af trÊer vha. TreeIterator preorder, postorder, inorder, levelorder

∑ BinÊre s¯getrÊer

∑ Princip og generisk implementation i Java

∑ Balancerede trÊer, AVL-trÊer (+ omtale af et par andre)

Hvad er et trÊ?

Matematikeren:

∑ Et specialtilfÊlde af en graf:

∑ En sammenhÊngende skov, hvor en skov er en orienteret, acyklisk graf, med h¯jst Èn vej mellem to forskellige knuder

∑ Og s kan vi jo bare bruge kendte reprÊsentationer for grafer og grafalgoritmer...

Datalogen udnytter naturlig rekursion:

∑ Et trÊ bestÂr af et stykke data samt nul eller flere trÊer kaldet deltrÊer

TrÊalgoritmer

∑ Naturligt rekursive

f.eks. summe trÊer med tal ...

Sum( t(k,T₁,...,T_n) ) = k + Sum(T₁) + ... + Sum(T_n)

∑ En gang imellem benytte en stak (og sommetider en k¯...)

Eksempel p reprÊsentation af syntaktrÊer vha. nedarvning

TrÊer for udtryk defineret ved f¯lgende ≥abstrakte≤ grammatik

<udtryk> ::= <tal>

| <udtryk> + <udtryk>

| <udtryk> * <udtryk>

Et udtrykstrÊ er enten

Et tal-trÊ, som indeholder en talkonstant (og 0 deltrÊer)

Et plus-trÊ har to deltrÊer, som er udtrykstrÊer

Et gange-trÊ har to deltrÊer, som er udtrykstrÊer

+

/ \

1 *

/ \

2 3

Brug af Javas nedarvning til reprÊsentation af syntakstrÊer

abstract class ExpressionTree { }

class PlusTree extends ExpressionTree

{ ExpressionTree first; ExpressionTree second;

public PlusTree(ExpressionTree f, ExpressionTree s) {first=f;second=s;} }

class TimesTree extends ExpressionTree

{ ExpressionTree first; ExpressionTree second;

public TimesTree(ExpressionTree f, ExpressionTree s) {first=f;second=s;} }

class NumberTree extends ExpressionTree

{ int value;

public NumberTree(int v) {value=v;}}

(Alternativt: Definere klasse for binÊre operatorer, og s specialisere den...)

Nedarving udnyttes til at definere et typehierarki ã modsat ≥generiske≤ trÊer i Java-stil.

SyntakstrÊer kan bygges eksplicit

ExpressionTree exp =

new PlusTree ( new NumberTree(1),

new TimesTree( new NumberTree(2),

new NumberTree(3)));

Eller i praksis ved en parser, som lÊser tegn ind fra fil og konstruerer trÊ efterhÂnden, enten

∑ top-down, eller

∑ bottom-up

Rekursive metoder udnytter ogs nedarvning....

exp.printStackCode();

==>

PUSH 1

PUSH 2

PUSH 3

TIMES

PLUS

abstract class ExpressionTree

{ public abstract void printStackCode(); }

class PlusTree extends ExpressionTree

{ ExpressionTree first; ExpressionTree second;

public void printStackCode()

{first.printStackCode();

second.printStackCode();

System.out.println("PLUS");} }

class TimesTree extends ExpressionTree

{ ExpressionTree first; ExpressionTree second;

public void printStackCode()

{first.printStackCode();

second.printStackCode();

System.out.println("TIMES");} }

class NumberTree extends ExpressionTree

{ int value;

public void printStackCode()

{System.out.println("PUSH "+value);} }

Analogt ≥post-order traversal≤ â

1. g¯r noget ved deltrÊerne, 2. g¯r noget for denne knude

exp.printExpression();

==> (1+(2*3))

abstract class ExpressionTree

{ public abstract void printExpression(); }

class PlusTree extends ExpressionTree

{ ExpressionTree first; ExpressionTree second;

public void printExpression()

{System.out.print("(");

first.printExpression();

System.out.print("+");

second.printExpression();

System.out.print(")");} }

class TimesTree extends ExpressionTree

{ ExpressionTree first; ExpressionTree second;

public void printExpression()

{System.out.print("(");

first.printExpression();

System.out.print("*");

second.printExpression();

System.out.print(")");} }

class NumberTree extends ExpressionTree

{ int value;

public void printExpression()

{System.out.print(value);} }

Ser vi bort fra udskrift af parenteserne: Analogt ≥in-order traversal≤ â

1 G¯r noget ved venstre deltrÊ,

2 G¯r noget for denne knude,

3 G¯r noget ved h¯jre deltrÊ

exp.printLispCode ();

==> (PLUS 1(TIMES 2 3))

abstract class ExpressionTree

{ public abstract void printLispCode(); }

class PlusTree extends ExpressionTree

{ ExpressionTree first; ExpressionTree second;

public void printLispCode()

{System.out.print("(PLUS");

first.printLispCode();

second.printLispCode();

System.out.print(")");} }

class TimesTree extends ExpressionTree

{ ExpressionTree first; ExpressionTree second;

public void printLispCode()

{System.out.print("(TIMES");

first.printLispCode();

second.printLispCode();

System.out.print(")");} }

class NumberTree extends ExpressionTree

{ int value;

public void printLispCode()

{System.out.print(" "+value);} }

Ser vi bort fra udskrift af parenteserne: Analogt ≥pre-order traversal≤ â

1 G¯r noget for denne knude,

2 G¯r noget ved deltrÊerne

ReprÊsentation af Java-stil generiske binÊre trÊer

public class BinaryNode {

// konstruktorer og de metoder kan kan forvente

private Object element;

private BinaryNode left;

private BinaryNode right; }

public class BinaryTree

{ // konstruktorer og de metoder kan kan forvente

private BinaryNode root; }

abstract class TreeIterator

{ public TreeIterator( BinaryTree theTree ) {t=theTree;current=null;}

// den slags metoder som h¯rer til en iterator...

// blandet abstract og def. vha. abstract

protected BinaryTree t;

protected BinaryNode current; }

class PostOrder extends TreeIterator

{ //definition af abstrakte metoder fra TreeIterator

...

//internt snask:

protected static class StNode { }

protected Stack s; }

class InOrder extends PostOrder { } // usmukt genbrug :(

class PreOrder extends TreeIterator { ... ogs noget med en stak }

class LevelOrder extends TreeIterator { ... noget med en k¯}

abstract class TreeIterator {

public TreeIterator(BinaryTree theTree) {t = theTree; current = null;}

abstract public void first( );

final public boolean isValid( ) {return current != null;}

final public Object retrieve( ) {

if( current == null ) throw ... ;

return current.getElement( ); }

abstract public void advance( );

protected BinaryTree t;

protected BinaryNode current; }

class PostOrder extends TreeIterator {...}

Hvis Java havde haft Êgte co-rutiner kunne det implementeres ved rekursion

Pseudokode:

class PostOrder extends TreeIterator {...}

public void first {postOrderTraverse(t.getRoot());}

private void postOrderTraverse(BinaryNode t); {

if(t==null) return;

postOrderTraverse(t.getLeft());

postOrderTraverse(t.getRight());

current=t;

detach();

return;}

public void advance( ); {resume()} }

Primitiver a la Simila68 (ikke i Java)

detach() ã lÊg metode til at sove indtil der kommer en resume()

resume() ã start en detachπet proces

OBS: Preorder og inorder fÂs ved at bytte rundt linjerne i xxxOrderTraverse()

NB: Det er muligt man kan lave noget i samme stil med Javas trÂde, men jeg har ikke checket det!!!

Disse primitiver findes ikke i Java, s derfor programmeres med eksplicit stak.

class PostOrder extends TreeIterator {

// Intern stak i mangel p rekursion:

protected static class StNode

{ BinaryNode node;

int timesPopped;

StNode( BinaryNode n )

{node = n; timesPopped = 0;}}

protected Stack s;

.... }

class PostOrder extends TreeIterator {

// Intern stak i mangel p rekursion:

protected static class StNode

{ BinaryNode node;

int timesPopped;

StNode( BinaryNode n )

{node = n; timesPopped = 0;}}

protected Stack s;

public PostOrder( BinaryTree theTree )

{super(theTree); s=new ArrayStack();

s.push(new StNode(t.getRoot()));}

public void first( )

{s.makeEmpty( );

if( t.getRoot( ) != null ) {s.push(new StNode(t.getRoot()));advance();}}

public void advance( )

{if( s.isEmpty( ) )

{if( current == null ) throw ...;

current = null; return; }

StNode cnode;

for( ; ; )

{cnode = ( StNode ) s.topAndPop( );

if( ++cnode.timesPopped == 3 ) {current = cnode.node; return;}

s.push( cnode );

if( cnode.timesPopped == 1 )

{ if(cnode.node.getLeft() !=null) s.push(new StNode(cnode.node.getLeft()));}

else // cnode.timesPopped == 2

{if(cnode.node.getRight()!=null)s.push(newStNode(cnode.node.getRight()));}}}

}

//NB: der stilles ingen eksamenssp¯rgsmÂl om hvordan den stak bruges

// (lÊreren synes det er noget knoldkode)
BinÊrt s¯getrÊ

En mÂde at opbevare og vedligeholde en samling objekter pÂ.

∑ objekterne holdes sorterede

o dvs. at finde objekter â log n

∑ indsÊttelse af nye objekter krÊver ikke ny sortering eller flytning af n/2 elementer

∑ indsÊttelse med ≥inkrementel sortering≤ â log n

Definition: Et binÊrt s¯getrÊ er et binÊrt trÊ hvor hver knude holder et element af en mÊngde udstyret med ≥<≤ og ≥=≤, sÂledes at

alle vÊrdier i venstre deltrÊ < vÊrdi p knude < alle vÊrdier i h¯jre deltrÊ

Eksempel

7

≠≠≠≠≠/ \≠≠≠≠

/ \

2 9

/ \

1 5

/

3

Egenskab: Hvis et binÊrt s¯getrÊ udskrives ≥in-order≤ kommer elementerne ud i voksende rÊkkef¯lge

Skitse af definition: En binÊrt trÊ er balanceret hvis det er ca. lige dybt over det hele.

Egenskab: Et balanceret, binÊrt trÊ med n elementer har h¯jde â log n.

Dvs. s¯gning i balanceret, binÊrt s¯getrÊ er O(log n).

ReprÊsentation af BinÊre s¯getrÊer i Java-stil

Upraktisk at specialisere fra BinaryTree fra f¯r, da Objectπerne i trÊet nu skal vÊre Comparable + at der skal lukkes af for modifikationer.

class BinaryNode

{ BinaryNode(Comparable theElement){element=theElement;left=right=null;}

Comparable element;

BinaryNode left; BinaryNode right; }

public class BinarySearchTree

{ public BinarySearchTree( ) {root = null; }

// diverse nyttige metoder, bl.a.

public void insert (Comparable x) { halv-kompliceret stads }

public Comparable find( Comparable x ) // returnerer x hvis den findes;ellers null

{ return elementAt( find( x, root ) );}

private Comparable elementAt( BinaryNode t )

{return t == null ? null : t.element;}

private BinaryNode find( Comparable x, BinaryNode t )

{ while( t != null )

{ if( x.compareTo( t.element ) < 0 ) t = t.left;

else if( x.compareTo( t.element ) > 0 ) t = t.right;

else return t; }

return null; }

protected BinaryNode root; }

IndsÊttelse af element x â

At lede efter elementet x, og hvis det ikke findes, indsÊtte det, hvor det burde have vÊret:

I Java:

//Metode i BinarySearchTree:

public void insert(Comparable x) { root = insert(x, root); }

BinaryNode insert(Comparable x, BinaryNode t) {

if (t == null)

t = new BinaryNode(x, null, null);

else if (x.compareTo(t.element) < 0)

t = insert(x, t.left);

else if (x.compareTo(t.element) > 0)

t = insert(x, t.right);

else

throw new DuplicateItemException(x.toString());

return t; }

Sletning af element x i binÊrt s¯getrÊ

BemÊrk: Problemet kan altid reduceres til at fjerne x i position som rod af et trÊ (det undertrÊ, som har x i toppen).

Erstat roden med den knude, der er mindst i rodens h¯jre undertrÊ.

Denne knude befinder sig lÊngst til venstre i rodens h¯jre undertrÊ.

Hvis det h¯jre undertrÊ er tomt, fjernes roden blot fra trÊet.

I Java:

public void remove(Comparable x) {root = remove(x, root);}

protected BinaryNode remove( Comparable x, BinaryNode t )

{if( t == null ) throw new ItemNotFoundException( x.toString( ) );

if( x.compareTo( t.element ) < 0 ) t.left = remove( x, t.left );

else if( x.compareTo( t.element ) > 0 ) t.right = remove( x, t.right );

else if( t.left != null && t.right != null ) // Two children

{ t.element = findMin( t.right ).element;

t.right = removeMin( t.right ); }

else t = ( t.left != null ) ? t.left : t.right;

return t; }

findMin â s¯g til venstre

removeMin â s¯g rekursivt til venstre, og da minimum element ikke har to undertrÊer, kan trÊet ≥trÊkkes sammen≤

Dette er altsammen meget godt, men det er kun interessant hvis indsÊttelser og sletninger ankommer sÂledes passende at trÊet forbliver balanceret.

Eksempel: VÊrdier indsÊttes i voksende rÊkkef¯lge:

1

\

2

\

3

\

4

\

5

\

...

TrÊet degenererer til en hÊgtet liste. O(log n) ==> O(n) :(

AltsÂ: IndsÊttelse og sletning skal justere p trÊet s det er nogenlunde balanceret.

Bogen omtaler forskellige strategier (og der er mange andre beskrevet i litteraturen)

Vi n¯jes med at skitsere AVL-trÊer!

AVL-trÊer (Adelson-Velskii og Landis, 1962)

For enhver knude i trÊet gÊlder, at h¯jden af dens venstre undertrÊ og h¯jden af dens h¯jre undertrÊ h¯jst afviger med 1.

Eksempel p AVL-trÊ:

Det kan bevises, at denne egenskab er tilstrÊkkelig for at sikre log n dybde.

Skitse af metode for indsÊttelse i AVL-trÊ

IndsÊttelse i Xπs venstre undertrÊ kan ¯delÊgge AVL-egenskaben.

I det f¯lgende betegner X den ≥dybeste≤ knude, som er rod i et deltrÊ, der ikke lÊngere opfylder AVL-egenskaben.

TilfÊlde 1: En h¯jrerotation genskaber balancen

TilfÊlde 2: En h¯jrerotation genskaber ikke balancen

Der skal en dobbeltrotation til:

F¯rst rotere til venstre i venstre deltrÊ; dernÊst til h¯jre i hele trÊet!

ãããããããããããããããããããããããããããã

Vi skÂner tilh¯reren (og lÊreren!) for implementationen i Java!

Afslutning:

TrÊer ã vigtig datastruktur til at reprÊsentere ≥af natur trÊagtige ting≤

∑ syntakstrÊer

∑ katalogstrukturer

∑ procestrÊer i operativsystemer

∑ ....

(BinÊre) s¯getrÊer:

∑ Vigtig datastrukturer til effektiv lagring og genfinding.

∑ Essentielt: At holde trÊerne balancerede!

∑ Databasesystemer er fyldt med trÊer og balanceringsalgoritmer

∑ ....

og hashing som vi kommer til nÊste gang. (om to uger)