1

Structuri de Date în Java (VIII)

● Arbori şi concepte● Reprezentarea arborilor● Arbori binari● Înălţime, adâncime, arbore plin, arbore complet● Structuri de date pentru arbori binari● Traversări: inordine, preordine, postordine● Construcţia arborelui pentru o expresie aritmetică● Arbori binari de căutare. Proprietăţi● Adăugarea şi ştergerea în arborele de căutare

2

Arbori

● Structură neliniară: nu există un prim element, al doilea ş.a.m.d.; există legături multiple între elemente, alcătuind o ierarhie

● Un arbore este un set finit de noduri pentru care:● există un singur nod special denumit rădăcină;● fiecare nod poate fi asociat mai jos în ierarhie

cu unul sau mai multe noduri fiu;● fiecare nod are exact un singur părinte, cu

excepţia rădăcinii, care nu are părinte.

3

Un arbore şi nodurile sale

● Accesul arborelui se facepornind de la rădăcina sa

● Nodurile pot fi:● rădăcină● frunze● noduri interne

4

Modurile de reprezentare ale arborilor● Diagrame

● Mulţimi incluse /------ G ------\ | /-- A --\ | | F | R D | | | \-------/ | \---------------/● Pe straturi /---------------\ | G | +-------+-------+ | F | A | +-------+---+---+ | R | D | \---+---/

● Prin indentareG

FA

RD

● Paranteze îmbricate(F, (R, D) A) G

GF A

DR

5

Arbori binari● Orice nod are maxim doi

fii cu excepţia funzelor– Din orice nod, frunză

sau nod intermediar, deplasarea către părinte şi apoi către părintele părintelui ne duce în final în ...

– Singurul nod în arbore fără părinte este ...

● RĂDĂCINA

14

11

13

53 4

719

17

9

6

Subarbore şi rădăcina sa● Pentru un nod se defineşte noţiunea de subarbore:

● Arborele obţinut dacă am şterge toate nodurile care nu sunt descendenţi ai nodului

14

11

13

53 4

719

17

9

7

Adâncimea şi înălţimea● Adâncimea = nivelul pe

care se află un nod● Adâncimea rădăcinii este

zero● Înălţimea se calculează

numărînd nivelele, pornind de la baza arborelui

● Care este înălţimea arborelui?

● Ce adâncime are 53?

14

11

13

53 4

719

17

9

8

Arbore binar plin / complet

17

9 53

11

4 41

14

a) arbore binar plin

17

9 53

11

4 41

14

13 33 16

b) arbore binar complet

9

Câte noduri are un arbore binar plin?

17

9 53

11

4 41

14

. . .

adâncime 0: 1 nod

adâncime 1: 2 noduri

adâncime 2: 4 noduri

adâncime n: 2n noduri

+

1 + 2 + 4 + ... + 2n = ?

. . .

10

Dar un arbore binar complet de înălţime n?

17

9 53

11

4

14 Pentru un arbore deînălţime n:

2n – 1 < noduri < 2n+1

11

Reprezentarea într-un vector a unui arbore binar complet

'L'

'O' 'R'

'G'

'I' 'T'

'A'

'H' 'M' 'S'

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]'A' 'L' 'G' 'O' 'R' 'I' 'T' 'H' 'M' 'S'

adâncime 0

adâncime 1

adâncime 2

adâncime 3fiu stâng = 2i + 1fiu drept = 2i + 2părinte = [(i-1) / 2]

12

Structura de date a unui nod

'L'

'O' 'R'

'G'

'T'

'A'

data 'A'left right

data 'L'left right

data 'G'left / right

data 'O'left / right /

data 'R'left / right /

data 'T'left / right /

referinţă la rădăcină

13

Clasa BTNode (i)

public class BTNode { public Object data; private BTNode left, right; public BTNode (Object data, BTNode left, BTNode right) { this.data = data; this.left = left; this.right = right; } public Object getData () { return data; } public BTNode getLeft () { return left; } public BTNode getRight () { return right; } public void setData (Object data) { this.data = data; } public void setLeft (BTNode left) { this.left = left; } public void setRight (BTNode right) { this.right = right; }

14

Clasa BTNode (ii)

public Object getLeftMostData () { if (left == null) return data; else return left.getLeftMostData (); } public Object getRightmostData () { if (right == null) return data; else return right.getRightmostData (); }

public boolean isLeaf () { return (left == null) &&

(right == null); }

'L'

'O' 'R'

'G'

'T'

'A'

'L'

'O' 'R'

'G'

'T'

'A'

15

Traversarea în preordine

Ordinea: A, L, O, R, G, T afişare, fiu stânga recursiv, fiu dreapta recursiv

'L'

'O' 'R'

'G'

'T'

'A'(1)

(2)

(3)

(4) (5)

16

preorderPrint

public void preorderPrint (int depth) { for (int i = 0 ; i < depth ; i ++) System.out.print (" "); System.out.println (data);

if (left != null) left.preorderPrint (depth + 1);

if (right != null) right.preorderPrint (depth + 1);

}

A

I S

N

T

C

17

Traversarea în inordine

Ordinea: O, L, R, A, G, Tfiu stânga recursiv, afişare, fiu dreapta recursiv

'L'

'O' 'R'

'G'

'T'

'A'

(1) (2) (3)

(4)

(5)

18

inorderPrint

public void inorderPrint (int depth) { if (left != null) left.inorderPrint (depth + 1);

for (int i = 0 ; i < depth ; i ++) System.out.print (" "); System.out.println (data);

if (right != null) right.inorderPrint (depth + 1);

}

A

I S

N

T

C

19

Traversarea în postordine

Ordinea: O, R, L, T, G, Afiu stânga recursiv, fiu dreapta recursiv, afişare

'L'

'O' 'R'

'G'

'T'

'A'

(1)

(2)(3)

(4)

(5)

20

postorderPrint

public void postorderPrint (int depth) { if (left != null) left.inorderPrint (depth + 1);

if (right != null) right.inorderPrint (depth + 1);

for (int i = 0 ; i < depth ; i ++) System.out.print (" "); System.out.println (data);

}

A

I S

N

T

C

21

Copierea unui subarbore

public static BTNode treeCopy (BTNode source) { BTNode leftCopy, rightCopy; if (null == source) return null; leftCopy = treeCopy (source.left); rightCopy = treeCopy (source.right); return new BTNode (source.data,

leftCopy, rightCopy);

}

22

Numărul de noduri şi înălţimea unui arbore

public static int treeSize (BTNode node) { if (null == node) return 0; return 1 + treeSize (node.left) + treeSize (node.right); }

public static int treeHeight (BTNode node) {if (null == node)

return 0;int lh = treeHeight (node.left);int rh = treeHeight (node.right);return 1 + (lh > rh ? lh : rh);

}

23

BTNodeDemopublic class BTNodeDemo { public static void main (String[] args) { BTNode a =

new BTNode (new Character('O'), null, null); BTNode b =

new BTNode (new Character('R'), null, null); BTNode c = new BTNode (new Character('L'), a, b); a = new BTNode (new Character('T'), null, null); b = new BTNode (new Character('G'), null, a); a = new BTNode (new Character('A'), c, b); a.inorderPrint (0); System.out.println ("---"); a.preorderPrint (0); System.out.println ("---"); a.postorderPrint (0); }}

O L R A G T --- A L O R G T ---

O R L T G A

24

Expresii aritmetice

4 * (2 - 3 + 7) / 2 – 3

Forma prefixată ?

Forma postfixată ?

Cum se face evaluarea ?2

2

4

3

7

3/

-

+

*

-

25

Construcţia arborelui asociat● Similară cu realizarea expresiei postfixate

● Se foloseşte o stivă pentru stocarea de numere, paranteze şi subarbori parţiali

● La întâlnirea unui număr, se creează un nod● Pentru un operator, se creează un nod cu fiul stânga nodul anterior existent deja în stivă● Trebuie ţinut cont de precedenţa operatorilor● Paranteza deschisă se 'împinge' pe stivă● Paranteza închisă forţează evaluarea conţinutului stivei, până la prima paranteză închisă, într-un nod

26

La momentul întâlniriiparantezei închise

4 * (2 - 3 + 7) / 2 – 3 4 * (2 - 3 + 7) / 2 – 3

4

*

2 3

7-

+

2

4

3

7-

+

*

27

După operatorul /

4 * (2 - 3 + 7) / 2 – 3 4 * (2 - 3 + 7) / 2 – 3

2

4

3

7-

+

*

/

2

4

3

7-

+

*

/

2

28

Arbori binari de căutare

● Un nod x al unui arbore binar de căutare respectă următoarele reguli:

● orice nod din subarborele stâng este mai mic decât nodul x

● orice nod din subarborele drept este mai mare decât nodul x

● Căutarea în arbore seamănă întrucâtva cu căutarea binară● Cu cât arborele este mai mic de înălţime cu atât căutarea durează mai puţin

29

Căutarea elementului 17

9

3 17

55

59

45

53

20

9

3 17

55

59

45

53

20

9

3 17

55

59

45

53

20

subarborele potenţialse restrânge din ce înce mai mult

30

Căutarea în arbore public static BTNode search (BTNode node, int k) { if (null == node || node.data == k) return node; if (node.data < k) return search (node.left, k); else return search (node.right, k); }

public static BTNode iterSearch (BTNode node, int k) { while (null != node && node.data != k) { if (k < node.data) node = node.left; else node = node.right; } }

31

Câteva proprietăţi

● Cum se obţin următoarele:● Minimul;● Maximul;● Elementele sortate crescător;● Dar descrescător?

32

Adăugarea elementului 16

9

3 17

55

59

45

53

9

3 17

55

59

45

53

9

3 17

55

59

45

53

9

3 17

55

59

45

53

16

33

Adăugarea unui nod în arbore

public static BTNode insert (BTNode node, int k) { BTNode pred = null; while (null != node) { pred = node; if (k < node.data) node = node.left; else node = node.right; }

if (k < pred.data) pred.left = new BTNode (k, null, null); else pred.right = new BTNode (k, null, null);}

34

Adăugarea nu este optimă

● 'Viteza' cu care găsim un element în arbore depinde direct de înălţimea sa

● Cu cât aceasta este mai mare cu atât găsirea unui element necesită examinarea mai multor elemente

● Daţi un exemplu de introducere a numerelor 5, 2, 7, 1, 3, 9, 6 astfel ca înălţimea arborelui rezultat să fie maximă (cât?)

35

Ştergerea unui nod fără succesori

Nodul 3 nu are fii

Nu necesită construcţiispeciale

9

3 17

55

59

45

53

19

36

Ştergerea unui nod cu un singur fiu

Nodul 17 are doar fiu drept

Legătura de la părintese reface prin conectare directă la fiu

9

3 17

55

59

45

53

19

37

Ştergerea unui nod cu doi fiiNodul 45 are doi fii

Se caută succesorul lui 45,care este 53 şi care poate aveamaxim un fiu drept(de ce?)

Nodul se şterge şi în locul luise pune succesorul

9

3 17

55

59

45

53

19

9

3 17

55

59

53

19

38

Succesor cu fiu

9

3 17

55

59

45

53

19 54

9

3 17

55

59

53

54

19

39

Bibliografie

Thomas H. Cormen, Charles E. Leiserson,

and Ronald L. Rivest

Introduction to Algorithms

Chapter 13. Binary Search Trees(vedeţi bibliografia cursului)