Datastructuren; (Zoek)bomen

Datastructuren; (Zoek)bomen Bomen, zoekbomen, gebalanceerde zoekbomen

José Lagerberg FNWI, UvA

Jos´ e Lagerberg (FNWI, UvA)

Datastructuren; (Zoek)bomen

1 / 50

Bomen Traversal van bomen Datastructuur van bomen Binaire zoekbomen Operaties op binaire zoekbomen Gebalanceerde zoekbomen



2 / 50

Bomen Boom is hi¨ erarchische datastructuur

Toegang tot tree bij root knoop Elke knoop is of blad (externe knoop) of interne knoop Interne knoop heeft één of meer kindknopen en heet parent Geordende boom heeft eerste kind, tweede kind, derde kind, etc.



3 / 50

Boom-Terminologie

Een boom bestaat uit verzameling knopen en verzameling randen Een boom heeft eigenschap dat er ´ e´ en pad is tussen twee knopen Een pad is verbonden rij van randen Een rooted tree bevat speciale knoop: de wortel Elke knoop c, behalve de wortel, heeft precies één parent knoop p, dat is de eerste knoop die je tegen komt op het pad van c naar wortel c is kind van p Een knoop kan willekeurig aantal kinderen hebben



4 / 50

Definities

Een blad heeft geen kinderen Siblings zijn knopen met dezelfde parent Voorouders van knoop d zijn knopen vanaf d naar wortel Als a een voorouder van d, dan is d nakomeling van a De lengte van pad is aantal randen in pad De diepte van knoop n is lengte van pad van n naar wortel (De diepte van wortel is nul) De hoogte van knoop is lengte van pad van n naar diepste nakomeling (De hoogte van blad is nul) De hoogte van boom is de hoogte van de wortel



5 / 50

Boom-Terminologie

wortel (T) = A interne knopen (T) = {A,B,C,F} bladeren (T) = {E,I,J,K,G,H,D} voorouders (F) = {A,B} diepte (K) = #voorouders(K) = 3 hoogte (T) = max{diepte(k) | k ∈ T} nakomelingen; subboom; . . .



6 / 50

Toepassing van bomen is structuur van directory

In meeste besturingssystemen files hierarchisch opgeslagen in directories Structuur zichtbaar gemaakt met boom



7 / 50

Linux commando tree

% tree . |-- homeworks | |-- h1nc.doc | ‘-- hc1.doc |-- programs | |-- DDR.java | |-- Robot.java | ‘-- Stocks.java ‘-- todo.txt 2 directories, 6 files



8 / 50

Boom ADT Boom ADT: data zijn objecten positions in boom zijn de knopen met parent-child relatie generieke methoden: I I I I

integer size() boolean isEmpty () objectIterator elements() positionIterator positions()

accessor operaties: I I I

position root() position parent(p) positionIterator children(p)



9 / 50

Boom ADT (vervolg): query methoden: I I I

boolean isInternal(p) boolean isExternal(p) boolean isRoot(p)

update methode: I I

swapElements(p, q) object replace(p, o)



10 / 50

Boom traversal

Een van belangrijkste operaties op boom is traversal: door alle knopen van de boom heen lopen en elke knoop bezoeken voor lijsten is traversal het doorlopen van de lijst van eerste tot laatste knoop voor bomen zijn er veel manieren om erdoor heen te lopen



11 / 50

Preorder traversal: elke parent systematisch bezocht v´ o´ or kindknopen

Algorithm preOrder(p) visit(p) for each child q of p preOrder(q) preOrder(root()): O(n) (n aantal knopen) Toepassing: afdrukken document of directory structuur Jos´ e Lagerberg (FNWI, UvA)


12 / 50

Postorder traversal: elke parent systematisch bezocht na kindknopen

Algorithm postOrder(p) for each child q of p postOrder(q) visit(p) postOrder(root()): O(n) (n aantal knopen) Toepassing: berekenen disk usage file system Jos´ e Lagerberg (FNWI, UvA)


13 / 50

Binaire Bomen Een boom is ordered als de kinderen van iedere knoop geordend zijn Een binaire boom is geordende boom met elke knoop hoogstens 2 kinderen Een binaire boom is proper als elke interne knoop precies 2 kinderen heeft



14 / 50

Toepassing: Expression tree

(2 × (a − 1) + (3 × b)) interne knopen zijn operatoren en bladeren zijn operanden als knoop extern, dan is zijn waarde een variabele of constante als knoop intern, dan is zijn waarde gedefinieerd door operatie op kinderen haakjes niet nodig, boomstructuur geeft volgorde operaties aan Jos´ e Lagerberg (FNWI, UvA)


15 / 50

Toepassing van Binaire Bomen: Beslisboom

interne knopen: vragen bladeren: beslissingen



16 / 50

Binaire boom ADT

Binaire boom ADT: Boom ADT + position leftChild(p) position rightChild(p) position sibling (p)



17 / 50

Inorder traversal van Binaire Bomen Inorder traversal van binaire boom:

Algorithm InOrder(p) if isInternal(p) inOrder(leftChild(p)) visit(p) if isInternal(p) inOrder(rightChild(p))

inOrder(root()): O(n) (n aantal knopen)



18 / 50

Inorder traversal: infix expressie Afdrukken van aritmetische expressies Algorithm printExpression(p) if isInternal(p) print("(") printExpression(leftChild(p)) print(p.element()) if isInternal(p) printExpression(rightChild(p)) print(")")

Infix expressie ((2 × (a − 1)) + (3 × b))



19 / 50

Postorder traversal: postfix expressie

Postfix expressie (RPN) 2 5 1 − ∗ 3 2 ∗ +



20 / 50

Recursieve traversal algoritmen

Algorithm traverse(T) if (T is not empty) { // preorder visit traverse(Left subtree of T) // inorder visit traverse(Right subtree of T) // postorder visit }



21 / 50

Samenvatting traversal algoritmen

Preorder, inorder en postorder traversals van expression tree: prefix, infix of postfix expressies, resp.

+ / \ ∗ / \ 3

+ ∗ 3 7 ˆ 4 2

Inorder :

3 ∗ 7 + 4 ˆ 2

( Infix )

Postorder :

3 7 ∗ 4 2 ˆ +

(RPN)

\

/

Preorder :

ˆ / \ 7 4

2



22 / 50

Linked datastructuur voor binaire bomen:



23 / 50

Implementatie in Java public class BinaryTree { TreeNode r o o t ; int size ; public BinaryTree () { } ... } c l a s s TreeNode { Object element ; TreeNode p a r e n t , l e f t , r i g h t ; p u b l i c TreeNode ( O b j e c t o ) { element = o ; } }



24 / 50

Datastructuur voor willekeurige bomen:



25 / 50

Big-Oh’s: Operatie

Tijd

size, isEmpty positions, elements replace root, parent, children leftChild, rightChild isInternal, isExternal, isRoot

O(1) O(n) O(1) O(1) O(1) O(1)



26 / 50

Dictionary ADT

Dictionary is een geordende of niet-geordende verzameling van paren (key, value), waarbij keys gebruikt worden om value te benaderen (woord, definitie) (studentID, studentGegevens) (vluchtNummer, vluchtInformatie) Gegevens toegankelijk via key: Object f i n d E l e m e n t ( key k ) // a l s n i e t g e v o n d e n NO SUCH KEY void i n s e r t I t e m ( key k , Object o ) Object removeElement ( key k )



27 / 50

Binaire zoekboom Binaire zoekboom is binaire boom met volgende eigenschappen: bladeren zijn leeg; iedere interne knoop bevat paar (k, e) binary-search-tree-property voor elke interne knoop geldt dat I

I

ieder knoop in linker subboom heeft kleinere key ieder knoop in rechter subboom heeft grotere key

Merk op: inorder traversal van binaire zoekboom bezoekt elementen in oplopende volgorde!



28 / 50

Binaire zoekboom

Belangrijkste voordeel van binary search trees: veel operaties efficiënt zoeken findElement(k, p) insert insertElement(k) creëert nieuwe knoop op plaats van nietgevonden zoekopdracht Operatie removeElement(k) is ingewikkeld: 1

kan delen van boom los maken

2

weer vast maken zo dat binary search tree eigenschap behouden

3

mag boom niet onnodig diep maken



29 / 50

Zoeken naar sleutel

Sleutel k zoeken, loop vanaf root naar beneden Volgende knoop wordt bepaald door uitkomst van vergelijking van k met sleutel van huidige knoop Als blad bereikt, sleutel niet gevonden Voorbeeld: findElement(4)



30 / 50

Recursief binair zoeken Algorithm findElement(k, p) if isExternal(p) return NO SUCH ELEMENT if k < p.element() return findElement(k, leftChild(p)) else if k = p.element() return p else return findElement(k, rightChild(p))

findElement(k,root()): O(h) (h hoogte van T) Jos´ e Lagerberg (FNWI, UvA)


31 / 50

Niet-recursief binair zoeken Algorithm findElement(k, p) while ! isExternal(p) en k != p.element() do if k < p.element() then p = leftChild(p) else p = rightChild(p) return p



32 / 50

binary-search-tree-property garandeert dat: 1 2

minimum sleutel in meest linkse knoop maximum sleutel in meest rechtse knoop

Algorithm minimumTree(p) while leftChild(p) != null then p = leftChild(p) return p



33 / 50

Successor van knoop (inorder) Successor van knoop p is knoop met kleinste sleutel > sleutel van p 1

2

Als knoop p een niet-lege rechter subboom heeft, dan is successor(p) minimum van rechtersubboom Als knoop p een lege rechter subboom heeft, dan I I

als omhoog is ’naar rechts’, dan successor(p) is parent als omhoog is ’naar links’, dan successor(p) vinden we door omhoog te bewegen tot ’naar rechts’, dan successor(p) is laatste knoop bereikt



34 / 50

Insertion (at bottom)

Om operatie insertElement(k, p) uit te voeren, zoeken we sleutel k Neem aan dat k niet in boom, en stel w is blad bereikt met zoeken Insert k op knoop w en breid w uit tot interne knoop Voorbeeld: insert 5

insertElement(5,root()): O(h) (h hoogte van T) Jos´ e Lagerberg (FNWI, UvA)


35 / 50

Deletion van knoop uit binaire zoekboom

Deletion van knoop Geval 0: knoop heeft geen kinderen Geval 1: knoop heeft één kind Geval 2: knoop heeft twee kinderen



36 / 50

Geval 0: Deletion van knoop zonder kinderen

removeElement(k): zoeken van sleutel k knoop v met key (v ) = k gevonden Als knoop v twee bladeren heeft, verwijder v uit boom Voorbeeld: remove 4



37 / 50

Geval 1: Deletion van knoop v met één kind

removeElement(k): zoeken van sleutel k knoop v met key (v ) = k gevonden Als knoop v één blad w heeft, verwijder v en w uit boom (v vervangen door sibling van w ) Voorbeeld: remove 4



38 / 50

Geval 2: Deletion van knoop v met twee kinderen Stel gevonden knoop v alleen interne knopen als kinderen w volgende knoop in inorder traversal (knoop w is meest linkse interne knoop in rechter subboom van v ) Kopieer key (w ) naar knoop v Verwijder w en diens linkerkind z (moet blad zijn) Voorbeeld: remove 3 Jos´ e Lagerberg (FNWI, UvA)


39 / 50

Performance binaire zoekboom Performance met hoogte boom h

Operatie

Tijd

findElement O(h)

insertElement O(h)

removeElement O(h)



40 / 50

Performance findElement, insertElement, removeElement Worst case met O(n) operaties:

Best case met O(log n) operaties:



41 / 50

Balanced trees

Definitie van hoogte van knoop Hoogte van knoop is lengte van langste pad naar externe knoop

Definitie van completely balanced tree In completely balanced tree hebben linker en rechter subboom van elke knoop dezelfde hoogte

Definitie van balanced tree Een boom is balanced ⇔ als voor elke interne knoop hoogtes van twee subbomen hoogstens 1 verschillen Dit noemt men ook Height-balance eigenschap



42 / 50

AVL-bomen (Adel’son-Vel’skii & Landis, 1962)

Hoogte van knoop is lengte van langste pad naar externe knoop

Height-balance eigenschap voor elke interne knoop geldt dat hoogtes van twee subbomen hoogstens 1 verschillen Een AVL-boom is binaire zoekboom met Height-balance eigenschap Dat heeft volgende consequentie: De hoogte van AVL-boom met n elementen is O(log n)



43 / 50

Height-balance eigenschap AVL-bomen

Height-balance eigenschap van AVL-boom: linker en rechter subbomen verschillen hoogstens 1 in hoogte



44 / 50

Height-balance eigenschap AVL-bomen

Linker subboom heeft hoogte 1 groter dan elke rechter subboom ⇒ AVL-boom


Subboom met wortel 8 heeft hoogte 4 en subboom met wortel 18 heeft hoogte 2 ⇒ geen AVL-boom


45 / 50

Stelling De hoogte van AVL-boom met n elementen is O(log n)

Bewijs Staat in het boek. Gebeurt met volledige inductie. Bewijs wordt niet gevraagd op tentamen.



46 / 50

Balance factor van knoop

De balance factor van knoop is hoogte van rechter subboom minus hoogte van linker subboom Een knoop is gebalanceerd als zijn balance factor gelijk aan 1, 0 of −1 is Een knoop met andere balance factor is ongebalanceerd



47 / 50

Balance factor BF

BF = (height right subtree - height left subtree) Dus, BF = -1, 0 or +1 voor AVL boom Balance factor van aantal voorbeeld AVL-bomen

−1

0 / \ 0

/ −1 /

0 0

+1 \

/ −1 /

0 0

\ −1 \

/ +1 \

0 0



48 / 50

Balance factor BF

Balance factor van nietAVL-boom

+1 \ −2

/ −1 / 0

/ +1 \ 0



49 / 50

Na insertion kan balans verstoord zijn

Balans herstellen met Boomrotaties Dat doen we volgende week



50 / 50

Datastructuren; (Zoek)bomen

Recommend Documents