Algorithmen und Datenstrukturen

[Link] Fischlin, SS 2023

03
Basic Data Structures

13. Oktober 2010 | [Link] Fischlin | Kryptosicherheit | 1

 Stacks

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 2

 zur Erinnerung
Abstrakte Datentypen (ADTs) und Datenstrukturen

näher an der Anwendung

Beispiel:

Stack mit Operationen

Abstrakter Datentyp („was“) isEmpty,pop,push

Übergang fließend; ADTs

werden daher oft auch als
Datenstruktur bezeichnet

Stack-Operationen
Datenstruktur („wie“) als Array
oder verkettete Liste

näher „an der Maschine“

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 3

 Bemerkung: auch Schreibweise
Abstrakter Datentyp Stack [Link](k) oder einfach pop()

new(S) - erzeugt neuen (leeren) Stack namensO

S

isEmpty(S) - -
gibt an, ob Stack S leer

pop(S) - gibt oberstes Element vom Stack S zurück

und löscht es vom Stack
(bzw. Fehlermeldung, wenn Stack leer)

push(S,k) - schreibt&
k als neues oberstes Element auf Stack o
-
S
(bzw. Fehlermeldung, wenn Stack voll) -

push(S,k) pop(S)

Formale Erfassung Oz.B.

&
(LIFO – last in, first out)

per algebraischer Spezifikation Stack S

-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 4

 Exkurs

Algebraische Spezifikation von Stacks

Stack mit Operationen new,isEmpty,push,pop muss

folgende Regeln erfüllen:

(1) Wenn new(S), dann unmittelbar isEmpty(S),

ergibt Ergebnis true.

(2) Wenn push(S,k) und keine Fehlermeldung,

dann unmittelbar pop(S), ergibt Ergebnis k.

(3) …

Fokus dieses Teils der Vorlesung liegt auf Entwurf der Datenstrukturen;
alle Lösungen erfüllen „natürliche“ Forderungen an solche Operationen.
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 5
Beispiel: Bitcoin
scriptPubKey:
OP_DUP OP_HASH160 56fa64a8bd7852d2c58095fa9a2fcd52d2c580b65d35549d
OP_EQUALVERIFY OP_CHECKSIG

56fa64a8…

PK Hash(PK) Hash(PK)

PK PK PK PK PK

Signature Signature Signature Signature Signature

OP_DUP OP_HASH160 56fa64a8… OP_EQUALVERIFY OP_CHECKSIG

entspricht entspricht entspricht entspricht entspricht

k=pop() k=pop() push(56fa…) k=pop() k=pop()
push(k) //h=Hash(k) h=pop() h=pop()
push(k) push(h) //k==h? //k,h gültig?

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 6

Stacks als Array (I) Annahme: maximale GrößeO
-
MAX
des Stacks vorher bekannt
-

0 1 2 3 4 5 6 7 8

S 12 47 17 98 72

[Link]
pop() zeigt auf oberstes Element

0 1 2 3 4 5 6 7 8

S 12 47 17 98

[Link]
bewegt sich eine Position nach links
gibt 72 zurück
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 7
Stacks als Array (II) Annahme: maximale Größe MAX
des Stacks vorher bekannt
0 1 2 3 4 5 6 7 8

S 12 47 17 98

[Link]
push(9)

0 1 2 3 4 5 6 7 8

S 12 47 17 98 9

[Link]
bewegt sich eine Position nach rechts

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 8

Stacks als Array: Algorithmen Annahme: maximale GrößeO MAX
des Stacks vorher bekannt
0 1 2 3 4 5 6 7 8

S 12 47 17 98 9

new(S) [Link] isEmpty(S)

1 S.A[]=ALLOCATE(MAX); 1 IF [Link]<0 THEN

2 [Link]=-1; 2 return true
3 ELSE
4 return false;

pop(S) push(S,k)

1 IF isEmpty(S) THEN
-
1 IF [Link]==MAX-1 THEN
- -

2 error-‘underflow‘ 2 error -
‘overflow‘
3 ELSE 3 ELSE
4 [Link]=[Link]-1; 4 [Link]=[Link]+1;
-

-
-

5 return -
S.A[[Link]+1]; 5 S.A[[Link]]=k;
-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 9

Stacks mit variabler Größe
0 1 2 3 4 5 6 7 8

S 12 47 17 98 9 13 45 7 33

[Link]
push(14)

Kopiere entweder in größeres,

-
oder verteile auf viele Arrays
-

-
zusammenhängendes Array um, ( Datenstruktur verkette Listen)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 10

Einfache Feldarbeit Erzeuge bei Bedarf neues Array mit zusätzlichem
-

Eintrag und kopiere aktuellen Stack um

-

12 47 17 98 9 13 45
push(7)
Kopiere

12 47 17 98 9 13 45 7

Kopiere push(33)

12 47 17 98 9 13 45 7 33

Kopiere push(34)

12 47 17 98 9 13 45 7 33 34

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 11

.
Laufzeit 𝑛 = 𝑀𝐴𝑋 Elemente in Liste undO
𝑛 weitere Push-Befehle
-

In Summe also
𝑛 Kopier-Schritte 1 ①
𝑛 + ∑ gü 𝑖 = Ω(𝑛 )
Y Kopier-Schritte
-

𝑛 + 1 Kopier-Schritte 2
Somit durchschnittlich
&
Ω 𝑛 Kopier-Schritte
-

②
pro Push-Befehl!
… -

n n Push befehl
.
n
-2 (n) =
R(n))
2𝑛 − 2 Kopier-Schritte

2𝑛 − 1 Kopier-Schritte
⑰
-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 12

Verbesserung?

Triviale Lösung: reserviere „unendlich“ viel Speicher

-

---
Gesucht: Lösung, die maximal jeweils O(#𝐸𝑙𝑒𝑚𝑒𝑛𝑡𝑒) Zellen benötigt

Idee: Wenn Grenze erreicht, verdoppele Speicher und kopiere um

-

Push
-Befehle

Verdopple Speicher und kopiere um

-
Schrumpfe und kopiere um, sofern weniger als ein Viertel belegt
-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 13

Feldarbeit: Algorithmen -
RESIZE(A,m)
reserviert neuen Speicher der Größe m,
kopiert&
A um, und lässt⑧A auf neuen Speicher zeigen
-

⑧ --
-

new(S) Array isEmpty(S)

1 S.A[]=ALLOCATE(1); 1 IF [Link]<0 THEN

-

2 [Link]=-1; -
2 return true
-

3 [Link]=1;
-
3 ELSE
4 return false;

pop(S) auf Array push(S,k)

1 IF isEmpty(S) THEN 1 [Link]=[Link]+1;

2 error ‘underflow‘
2 S.A[[Link]]=k;
3
4
ELSE
[Link]=[Link]-1;
3 IF [Link]+1==[Link] THEN ②
I
5 IF 4*([Link]+1)==[Link] THEN 4 [Link]=2*[Link];
6
7 [Link]=[Link]/2;
RESIZE(S.A,[Link]);
belegt
Den
5 RESIZE(S.A,[Link]);
alle plätze belegt ,
dane

8 return S.A[[Link]+1]; ↓
rerdoppele Speicher und

Kopie um
Speicher
halbite

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 14

 push(S,k) top memsize=4
top=1
1 [Link]=[Link]+1; push
2 S.A[[Link]]=k; top 1 top=2
3 IF [Link]+1==[Link] THEN
4 [Link]=2*[Link]; 2

&
5 RESIZE(S.A,[Link]); push
top=3
+
-1 2 p 1

2 memsize=8
3-5

pop(S)
pop
1-4 top=2

&
1 IF isEmpty(S) THEN
2 error ‘underflow‘
3
4
ELSE
[Link]=[Link]-1; wil
Arrag Trageg pop (8)
1-4 top=1
5 >
-
IF 4*([Link]+1)==[Link] THEN
6 [Link]=[Link]/2; memsize=4
7 RESIZE(S.A,[Link]); 5-7
8 return S.A[[Link]+1];
(8)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 15

Analyse Laufzeit & Vergrößern (gilt analog für Verkleinern)

& imedt
(1) 𝑛 Elemente (unmittelbar
nach letzter Vergrößerung) (2) neue Speichergrenze wird nur erreicht,
wenn dann mindestens 𝑛 viele Push-Befehle
-

Verdopple Speicher und kopiere um

-
(3) Umkopieren kostet dann O(𝑛) Schritte

Im Durchschnitt für jeden der mindestensD-

𝑛 Befehle Θ 1 Umkopierschritte!
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 16
Stacks in Java
Class Stack in Java 13

Quelle: Wikipedia

capacityIncrement gibt an,

wieviel Vector wachsen soll,
wenn zu viele Elemente (default = 2)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 17

 Geben Sie eine „schlechte“ Eingabe für die Java-Klasse
Stack an, bei der wegen des fehlenden Schrumpfens
viel Speicher verschwendet wird.

Stellen Sie die Operation clear für einen Stack

in Pseudocode dar, die den Stack leert.

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 18

 Verkettete Listen

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 19

Datenstruktur Verkettete Listen

(doppelt) verkettete Liste

5 12 17 47 72 98

head
zeigt auf
erstes Element
(bzw. ist nil für
3 Jedes Element x besteht aus:
key – Wert (hie( +* )
prev – Zeiger auf Vorgänger (bzw. nil)
leere Liste) next – Zeiger auf Nachfolger (bzw. nil)

evtl. schon als Datenstruktur implementiert, oder aber…

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 20

Datenstruktur Verkettete Listen durch Arrays
-

[Link]=6 13
12
A

LED

0 1 2 3 4 5 6 7 8

12 6 nil 45 nil 0

key prev next key prev next key prev next

entspricht ats pricht
index =2 Index
von
von reächstem
Vorgänger Element.
Element entspricht doppelt verketteter Liste

45 12

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 21

Elementare Operationen auf verketteten Listen
-

-
search(L,k) -
//returns pointer to k in L (or nil)
short circuit
evaluation
1 current=[Link]; (wie in Java)

2 WHILE current != nil AND [Link] != k DO

3 current=[Link]; > wenn nicht gefunden -
und nicht Ende
der Liste
4 return current; agekomme
dann
gehe zu nächstem

Search(L,17)
Laufzeit= (n)
head 2/3 2/3
1
#
nur

einneh
5 12 17 47 durchlaufen
1 2/3
2/3 2/3 2/3 nil
Search(L,18)
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 22
Elementare Operationen auf verketteten Listen
insert(L,x) //inserts element x in L call-by-reference
-
-

bzw. call-by-value
1 [Link]=[Link]; - für Objekte wie in Java
Anfang
am -

2 [Link]=nil;
de
3 IF [Link] != nil THEN Liste
4
5
[Link]=x;
[Link]=x;
einfügen Laufzeit= (1)

5 Insert(L,x)
head

2 1
37 5 12 17 47
3/4

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 23

Elementare Operationen auf verketteten Listen

Achtung: Einfüge-Operation prüft nicht, ob Wert bereits in Liste

e
Wenn zuerst Suche nach Wert, dann wiederum Laufzeit (n)! ⑧

x head

37 5 12 37 47

5
head Insert(L,x)

2 1
37 5 12 37 47
3/4

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 24

Elementare Operationen auf verketteten Listen
E
delete(L,x)
O
>
-
//deletes elementO
zeigt die
x from L
Element von Liste 1. Laufzeit= (1)
1 IF [Link] != nil THEN 1/ checks if

Ell
2 & [Link]=[Link]
Achtung: Löschen

⑭
3 ELSE
eines Wertes k
4 [Link]=[Link];
kostet Zeit①
(n)
5 IF [Link] != nil THEN - -

6 [Link]=[Link];
e wenn zu lischende
Element
gefunden werden
soll, dann Zeit)
5/6
head O
x
Delete(L,x)
C >
5 12 17 47
-

1/2

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 25

Vereinfachung per Wächter/Sentinels
delete(L,x) //deletes element x from L

1 IF [Link] != nil THEN Ziel:

2 [Link]=[Link] eliminiere die

-
Spezialfälle für
3 ELSE
4 [Link]=[Link]; Listenanfang/-ende
5 IF [Link] != nil THEN
6 [Link]=[Link];

Sentinel
[Link] head =[Link]

nil 5 12 17 47

Sentinel ist „von außen“ nicht sichtbar Leere Liste besteht nur aus Sentinel
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 26
Löschen mit Sentinels

deleteSent(L,x) Andere Operationen

// deletes x from L with sentinel wie Einfügen
und Löschen
1 [Link]=[Link]; müssen auch
2 [Link]=[Link]; angepasst werden

Sentinel
Delete(L,x)
[Link] head =[Link] x

nil 5 12 17 47

1/2

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 27

 Queues

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 28

 sirada bekleyen insanlar. Ilk gelen ilk hizmet alir.
-

son gelen arkadan (rear) dan siraya girerler,

Abstrakter Datentyp Queue ilk gelenler hizmet aldiktan sonra siradan önden (front)
-
-

&
cikar.

new(Q) - erzeugt neue (leere) Queue namens Q

isEmpty(Q) - gibt an, ob Queue Q leer

dequeue(Q) - gibt vorderstes Element der QueueO

-
Q zurück
und löscht es aus⑤
-
Queue
(bzw. Fehlermeldung, wenn Queue leer)

enqueue(Q,k) - schreibtO
k als neues hinterstes Element aufO
-
Q
(bzw. Fehlermeldung, wenn Queue voll)

Queue Q

enqueue(Q,k) dequeue(Q)

①
(FIFO – first in, first out) rear front

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 29

Queues als Array? (I) Wo ist front, wo rear?

0 1 2 3 4 5 6 7

Q 17 98 9 23 37 8 47

[Link] [Link]

zu Beginn auch rechts, zu Beginn ganz rechts,

wandert dann nach links wandert dann nach links
beim Einfügen beim Auswerfen

Problem:
Selbst wenn maximale Anzahl Elemente, die gleichzeitig in der Queue sind,
vorher bekannt, kann --
-

[Link] die Array-Grenze links erreichen

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 30
Queues als Array? (II) Wo ist front, wo rear?

0 1 2 3 4 5 6 7

Q 47 8 37 23 9 98 17

[Link] [Link]

zu Beginn ganz links, zu Beginn auch links,

wandert dann nach rechts wandert dann nach rechts
beim Auswerfen beim Einfügen

Problem:
Selbst wenn Array nach rechts unendlich lang,
wird Speicher links von [Link] verschwendet
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 31
 MAX Elemente
Queues als (virtuelles) zyklisches Array gleichzeitig in Queue
[Link] 0 1

wandert zyklisch
nach rechts beim 7 2
Auswerfen
nur virtuell

6 3

[Link] Zeiger muss beim

Wandern nach rechts
wandert zyklisch 5 4 von 7 auf 0 springen
nach rechts beim (und links von 0 auf 7)
Einfügen

0 1 2 3 4 5 6 7

47 8 37 23 9 98 17 real

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 32

 Exkurs

Modulo-Operator

Modulo-Operator 𝒙 𝒎𝒐𝒅 𝒏 für 𝒏 > 𝟎

Der Modulo-Operator 𝑥 𝑚𝑜𝑑 𝑛 bildet eine ganze Zahl 𝑥 auf die Zahl 𝑦
zwischen 0 und 𝑛 − 1 ab, so dass 𝑦 = 𝑥 − 𝑖 𝑛 für eine ganze Zahl 𝑖.

Beispiele: 15 mod 5 = 0, weil 0 = 15 − 3 5

(6 + 7) 𝑚𝑜𝑑 8 = 5, weil 5 = 13 − 1 8
−4 𝑚𝑜𝑑 7 = 3, weil 3 = −4 + 1 7

Achtung: In Java ist der %-Operator als Divisionsrest für negative Zahlen 𝑥
anders definiert, dort ist z.B. −4 % 7 = −4. Man kann dies unter Beachtung
eventueller Überläufe abbilden durch 𝑥 𝑚𝑜𝑑 𝑛 = ((𝑥 % 𝑛) + 𝑛 ) % 𝑛.

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 33

 MAX Elemente
Ein Bit, bitte gleichzeitig in Queue
[Link]
0 1
[Link]

7 2

6 3

5 4

Ist das eine leere Schlange oder eine volle Schlange?

Speichere diese Information in Boolean empty

(alternativ: reserviere ein Element des Arrays als „Abstandshalter“)
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 34
 MAX Elemente
Queues als zyklisches Array: Algorithmen gleichzeitig in Queue
Q leer, wenn front==rear Q voll, wenn front==rear
und empty==true und empty==false
new(Q) isEmpty(Q)

1 Q.A[]=ALLOCATE(MAX); 1 return [Link];

2 [Link]=0;
3 [Link]=0;
4 [Link]=true;

dequeue(Q) enqueue(Q,k)
f

O ↑
9
1 IF isEmpty(Q) THEN 1 IF [Link]==[Link] AND ![Link]
-
↑

2 error ‘underflow‘ 10 2 THEN error ‘overflow‘ volke

>
-

Queue W
3 ELSE S 10 16 3 ELSE
4 [Link]=[Link]+1 mod MAX; 4 Q.A[[Link]]=k;
5 IF [Link]==[Link] THEN 5 [Link]=[Link]+1 mod MAX;
6 [Link]=true; 6 [Link]=false;
7 return Q.A[[Link]-1 mod MAX];

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 35

Queues durch einfach (!) verkettete Listen
# next and
bey ,

(einfach) verkettete Liste

5 12 17 47 72 98

front rear

wandert nach rechts wandert auch nach

beim Auswerfen rechts weiter
beim Einfügen

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 36

Queues durch Liste: Algorithmen

isEmpty(Q)
new(Q)
1 IF [Link]==nil THEN
1 [Link]=nil;
2 return true
2 [Link]=nil;
3 ELSE
4 return false;

dequeue(Q) enqueue(Q,x)

1 IF isEmpty(Q) THEN 1 IF isEmpty(Q) THEN

2 error ‘underflow‘ 2 [Link]=x;
3 ELSE 3 ELSE
X,
-
4 x=[Link]; 1 bastakini a 4 [Link]=x; >
-

Song

5 [Link]=[Link]; 11
-
5 [Link]=nil; aix
-
sen eleve
1j4 göste sağle
>

6 return x; 6 [Link]=x; -

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 37

 *Worst Case
Anzahl Operationen

Stack Queue

Operation Laufzeit* Operation Laufzeit*

Push (1) Enqueue (1)
Pop (1) Dequeue (1)

Verkettete Liste

Operation Laufzeit*
Einfügen (1)
Löschen
Suchen
es(1)
(n)
Laufzeit Löschen
eines Wertes (n)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 38

 Geben Sie die Suchoperation für einen Wert k
bei einer Liste mit Sentinels an.

Wie kann man mit Hilfe zweier Stacks eine Queue

implementieren?

Wie kann man mit Hilfe zweier Queues einen Stack

implementieren?

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 39

 Binäre Bäume

Verkettete Liste

Operation Laufzeit*
Einfügen (1)
Löschen (1)
Suchen (n) Geht das besser?

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 40

Bäume durch verkettete Listen
Jeder Knoten enthält:
[Link] 5 key - Wert
child[]- Array von Zeigern auf Kinder

Knoten 9 12 15 manchmal auch nützlich:

parent - Zeiger auf Elternknoten

23 17 23 23

Baum-Bedingung: Baum ist leer oder… D

es gibt einen Knoten r („Wurzel“), so dass jeder Knoten v von der Wurzel aus
per eindeutiger Sequenz von child-Zeigern erreichbar ist:
v = [Link][i1].child[i2].….child[im]

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 41

Eigenschaften von Bäumen

9 12 15

23 17 23 23

wunzel

Bäume sind „azyklisch“ e o

Für nicht-leeren Baum gibt es
genau #𝐾𝑛𝑜𝑡𝑒𝑛 − 1 viele Einträge
nil über alle Listen child[]
weil e ist Wurfel
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 42
Darstellung als (ungerichteter) Graph später mehr zu Graphen

5 5

9 12 9 12

23 17 23 23 17 23

* Achtung: in beiden Darstellungen ist die Reihenfolge

in child[] quasi durch die Anordnung der Knoten dargestellt

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 43

Darstellung als (ungerichteter) Graph

5 5

als Baum
verschieden

9 12  9 12

17 23 23 23 17 23

Achtung: in beiden Darstellungen ist die Reihenfolge

in child[] quasi durch die Anordnung der Knoten dargestellt

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 44

Begrifflichkeiten (I) Tiefe des Knoten/
node depth
~
Vorfahre von…/ ~
ancestor of … Wurzel/root 0
5

Elternknoten…/ Kind von…/ ~

parent of … - 9 12 child of … 1

Geschwister/ Nachkomme/
23 17 23 ~ 2
siblings of… ~ descendant of …

Blatt/leaf ~

T -
Höhe des Baumes/ tree height
= maximale Tiefe eines Knoten
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 45
Begrifflichkeiten (II) A =
Binärbaum:
jeder Knoten hat maximal zwei Kinder,
left=child[0] und right=child[1]
… oder …
d.h. Ausgangsgrad/outdegree
rechts
⑬
-

Links z 5 jedes Knotens ist ≤ 2

&

markiere Knoten
auch graphisch
Halbblatt 12 als linkes oder
9 -

hat genau ein Kind rechtes Kind

-

23 17 23 Höhe leerer
-

-
Baum hier per
Konvention&-1
(linker) Teilbaum von z (rechter) Teilbaum von z

Höhe (nicht-leerer) Baum = max {=

Höhe aller Teilbäume der Wurzel } +1
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 46
Baum-Höhe
-

Ein
bspw -
krofen Baum :

O
er I
>
↓
----
er =
Höhe
per
der Teilbare
bencention = -1

-
-
1 + 1
Also
gegarthöle = max ( - 1
,
-

13 + 1 = -

= 0

Gesamtbil
-
3-131
+=c,
 linze teilburn-Vater-rechter teilbaum

Trit
Beispielanwendung:
Inorder-Traversieren von Binärbäumen
Serialisierung

..
aga *

23 inorder(x)

D 1 IF x != nil THEN
2 inorder([Link]);
3 print [Link];
17 24 4 inorder([Link]);

I
Bei Bedarf mit „Wrapper“
inorderTree(T)=inorder([Link])

9 23 25
I

inorder([Link]) ergibt
, 17
9 , 23 ,
23 ,
24 25,
r

9 17 23 23 24 25

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 47

Inorder-Traversieren von Binärbäumen: Laufzeit

23 inorder(x)

1 IF x != nil THEN
2 inorder([Link]);
3 print [Link];
17 24 4 inorder([Link]);

𝑇(𝑛) = Laufzeit bei 𝑛 Knoten

9 23 25 Behauptung: 𝑇(𝑛) = 𝑂(𝑛),

genauer 𝑇 𝑛 ≤ 𝑐 + 𝑑 𝑛 + 𝑐
Gilt mit 𝑇(0) = 𝑐 bei leerem Baum
Rekursion mit 𝑘 Knoten im linken Teilbaum und 𝑛 − 𝑘 − 1 im rechten:
𝑇 𝑛 =𝑇 𝑘 +𝑇 𝑛−𝑘−1 +𝑑
≤ 𝑐+𝑑 𝑘+𝑐 + 𝑐+𝑑 𝑛−𝑘−1 +𝑐 +𝑑 ≤ 𝑐+𝑑 𝑛+𝑐
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 48
 noch recherchenen
unbalancierte Baum
Inorder ⇏ Baum T - Stratenkefe)
Wenn die Different
=>
den lavel , me
⑧
einweise kroten einfigen
benn , ist nieut
↑
an
sie ,

S
23 0
-- 17 0 .

Siehe
#
E

17 24 1 vs. 1 9 -
-
23

& 9 23 25 2 2 - - - - 23 - 25

Blatt

-
----- 24
Verschiedene Bäume, aber gleiche Inorder
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 49
 >
- Saga citgi
Pre- und Postorder-Traversieren von Binärbäumen (I)
↓

wi
Sola -
preorder(x)
City ; 23 -

1 IF x != nil THEN
2 print [Link];
3 preorder([Link]);
4 preorder([Link]);
-

17
-
-

&
24 -

3 ,
17
,
9, 23 , 24 25
,

-
9 - -

23 -
&
25 -
Bost
9 23 17 25 24
, ,
, , , 23

preorder([Link]) ergibt
23 17 9 23 24 25

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 50

Pre- und Postorder-Traversieren von Binärbäumen (II)

O
preorder(x)
23
1 IF x != nil THEN
2 print [Link];
3 preorder([Link]);
4 preorder([Link]);
17 24
postorder(x)

1 IF x != nil THEN
9 23 25 2 postorder([Link]);
3 postorder([Link]);
4 print [Link];

Se
a
preorder([Link]) ergibt postorder([Link]) ergibt

O 23 17 9 23 24 25 9 23 17 25 24
⑧
23

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 51

Beispiel Preorder-Traversierung
preorder(x)
+
1 IF x != nil THEN
2 print [Link];
3 preorder([Link]);
4 preorder([Link]);
* 8

6 3

preorder([Link]) ergibt inorder([Link]) ergibt

(+ ( * 6 3) 8) 6 * 3 + 8

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 52

Exer
Preorder-Traversieren für Kopieren
Unterbäume können
in kopierten Knoten
eingefügt werden

(1) Preorder betrachtet zunächst

23 Vater Knoten und legt Kopie an
23

(2) Preorder geht dann in Teilbäume und kopiert diese

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 53

 e -
n - v
Postorder-Traversieren für Löschen

(2) Postorder betrachtet Knoten erst danach und

löscht dann den kompletten Knoten

23
Zeiger auf rechten Teilbaum
noch vorhanden, wenn
linker Teilbaum bereits
gelöscht wurde

(1) Postorder geht zuerst in Teilbäume und löscht diese

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 54

Preorder ⇏ Binärbaum gilt entsprechend auch für Postorder

23 23

17 24 vs. 17

9 22 25 9 24

22 25

Verschiedene Bäume, aber gleiche Preorder

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 55
Preorder + Inorder + eindeutige Werte ⇒ Binärbaum e
23

Preorder = 23 17 9 29 24 25

⑨
17 9 29
a
24 25
-
(1) Identifiziert Wurzel

Pre =O
17 9 29 Pre = 24 25
In = 9 17 29 In = 24 25
Inorder = 9 17 29 23 24 25
Bilde Teilbäume rekursiv
(2) Identifiziert Werte im
linken und rechten Teilbaum
Gilt analog für Postorder - Postomer hat wer zel
als letztes
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 56
Inorder und eindeutige Werte sind notwendig

23 23
Haben gleiche
Pre-, Post- und Inorder
vs.
23 23

23 23
Haben gleiche
Pre- und Postorder
vs.
17 17

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 57

 Zeigen Sie: In einem nicht-leerem Binärbaum mit 𝑛 Knoten
gibt es genau 𝑛 + 1 viele Einträge child[i]=nil.

Geben Sie zu dem linken Baum auf Folie 51

(Preorder⇏Binärbaum) einen anderen Baum
O
mit gleicher Postorder an.
-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 58

 Induktion .

Jamis child [i] nit

O 2 under
=:
,
Basis n= 1

mit wie

2) 1
441

T
-

man
,
Fortschritt manef
Basis
S 2+ 1 will kne ling /

n h +1 Will kinde rechts

2 kofen n -
4 knoten

gescort , n - h + 1 + 2 + 1 = n + 2 will sne

Also be ; net kneten

n+ 2 Will boder glt

Abstrakter Datentyp Baum
new(T) - erzeugt neuen Baum namens T

search(T,k) - gibt Element x in Baum T mit [Link]==k zurück

(bzw. nil)

insert(T,x) - fügt Element x in Baum T hinzu

delete(T,x) - löscht x aus Baum T

oft weitere Baum-Operationen wie Wurzel, Höhe, Traversieren,….

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 59

Suchen Crekursiv) search(x,k)
zuerst woten den

nkv
Inne Teilbaur gelese
rechter Teilbar
-

1 IF x==nil THEN return nil;

2 IF [Link]==k THEN return x;
search([Link],9)
3 y=search([Link],k);
9 4 IF y != nil THEN return y;
5 return search([Link],k);
23

starte mit search([Link],k)

9

17 12

9

9 23 25
⑤
Laufzeit = Θ(𝑛)

Jeder Knoten wird maximal einmal besucht,

im schlechtesten Fall aber auch jeder Knoten
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 60
 herkömmliche
Anfang
List ist linke teilbam

Einfügen um ·
vor zu

insert(T,x) einfügend
Kate
in

8
//[Link]==[Link]==[Link]==nil;wurd
4 [Link] x
1-3
1 IF [Link] != nil THEN
2 [Link]=x;
3 [Link]=[Link];
[Link] 23 4 [Link]=x;

17 12

Laufzeit = Θ(1)
9 23 25

*Achtung: erzeugt-
linkslastigen Baum!!!

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 61

 Sonderfälle beachten:
Löschen

T
Halbblatt ist selbst x oder Wurzel
Idee:
Ersetze x durch Halbblatt ganz rechts

[Link] [Link] 23
23

9
17

23
x
4 12

25 9
25

23
12

Es gibt natürlich auch andere Möglichkeiten

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 62
Löschen: Connect-Algorithmus Laufzeit = Θ(1)

0
connect(T,y,w)
//connects w to [Link]
v loschade
Er
1 v=[Link];
↑ 2 IF y != [Link] THEN // y pretk null
y 3 IF y == [Link] THEN /right child
[Link] 4+10 4 [Link]=w;
5 ELSE "Reft child
6 [Link]=w;
7 ELSE
y w 8 [Link]=w;
8+10
↓

habblatt
9 IF w != nil THEN
eur
10 [Link]=v;
w
(w muss dabei nicht an y hängen)
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 63
 delete(T,x) //assumes x in T
Löschen: Algorithmus
1 y=[Link];
finden 4) -
um zu 2 WHILE [Link]!=nil DO
welchen koten
en
3 y=[Link]; weil
&
2
-

mit lischende brok

soll ren zu
ersetzen
.
wigseht ,

L soll seme
[Link] 4 connect(T,y,[Link]); der nicht
23 left to prent set) learda-
ge y. Stehen
5 IF x != y THEN

57
1-3
6 [Link]=[Link];
7 IF [Link] != nil THEN
12 8 [Link]=y;
17 x
9 [Link]=[Link];
4 10 IF [Link] != nil THEN
11 [Link]=y;
12

9 23 25 12 connect(T,x,y);
y
to X
prent
6-11
y
Laufzeit = Θ(ℎ)
5-11) ist dafür da
, dass von die Kunden

vor zu lishade kote an

y (ersetze
hotel a
hingh ℎ Höhe des Baumes, ℎ = 𝑛 möglich
/
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 64
 Binäre Bäume
Suchbäume

Operation Laufzeit*
Einfügen (1)
Löschen (h)
Suchen (n) Geht das besser?

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 65

Binäre Suchbäume (Binary Search Tree, BST)

23 Wir nehmen wieder totale

Ordnung auf den Werten an
-

17 24
linke teilbaum
kleine
gleich
9 22 25 recht Teilbaum
Größer gleich
Binärer Suchbaum:
Binärbaum, so dass für alle Knoten z gilt:
WennOx Knoten im linken Teilbaum von z, dann [Link] <= [Link]
Wenn y Knoten im rechten Teilbaum von z, dann [Link] >= [Link]
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 66
--
Preorder + eindeutige Werte ⇒ Binärer Suchbaum

23

Li
(1) Identifiziert Wurzel

2
17
--
g 22 -
-

Preorder = 23 17 9 22 24 25
17 9 22 24 25

Pre = 17 9 22 Pre = 24 25
(2) Identifiziert Werte im
-

linken und rechten Teilbaum

Bilde Teilbäume rekursiv -

wurzel
Post
-

order = 92217 252

ht rechte
- ⑪
Gilt analog für Postorder
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 67
Inorder + eindeutige Werte ⇏ Binärer Suchbaum

23 17

vs.

17 24 9 23

9 22 25 22 25

24

Beide Suchbäume haben gleiche Inorder

-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 68

Suchen im Binären Suchbaum
search(x,k) //[Link] x=root
Wurzel ist
Baum her das
search([Link],22) >
-
gesuchte
1 IF x==nil OR [Link]==k THEN
2 return x;
finden de
zu
o
23 3 IF [Link] > k THEN > -

Element bleher
ist

3/4 4 return search([Link],k)

5 ELSE
6 return search([Link],k);

17 24

O
5/6
Laufzeit = 𝑂(ℎ)
A
ℎ Höhe des Baumes
9 22 25

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 69

Iterative Suche im Binären Suchbaum
search(x,k) //[Link] x=root

1 IF x==nil OR [Link]==k THEN

2 return x;
3 IF [Link] > k THEN
4 return search([Link],k)
5 ELSE
6 return search([Link],k);

iterative-search(x,k) //Aufruf x=root

1 WHILE x != nil AND [Link] != k DO

-

2
3 x=[Link]
Ticke
IF [Link] > k THEN linben in Heilbor ,
da be beleve als
X.
Sey ist

4 ELSE
5 x=[Link]; & suche rechten in /bare ,
do 2
guidegleich
6 return x; als
bey
X
ist
-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 70

 insert(T,z)
Einfügen im BST -
//may insert ⑧
z again
insert(T,z) //[Link]==[Link]==nil;
-

1 x=[Link]; px=nil; > -

part
17 1-7
-

2 WHILE x != nil DO
3 px=x;
4 IF [Link] > [Link] THEN
5 x=[Link]
24
6 ELSE
xnil
px24 -
7 x=[Link];
8 [Link]=px;
8-15
9 IF px==nil THEN
-

z 22 25 10 -
[Link]=z
11 ELSE
12 IF [Link] > [Link] THEN
[Link]=z S
Eltern kote
13 als neue
größer
Krefe daher
,

kofe
neve
like Kind ist

14 ELSE
Laufzeit = 𝑂(ℎ) O 15 [Link]=z; Eltern Knote
>
-

neve
kleiner gleich as
brote , deher neue
* Ne ist rechter kind

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 71

 F
:

Löschen im BST (I)* zu löschender Knoten⑧

z hat maximal ein Kind -

Dann dieser Kind

oder Stelle oder
mit in
von z und Z
geht
z weg r

nil r L R

Bedingung an Struktur/Werte
L R ② im BST bleibt erhalten

analog, wenn auch/oder rechtes Kind = nil

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 72
 Fall 2 :

&
Löschen im BST (II) rechtes Kind von Knoten O
z hat kein linkes Kind
Dannnehme diese rechte

oder oder
und alle Seine
kind

Kinder 1 Stufe Hoch.

z ersetze Zu
lischende r
mit den
Kote(2)
and von t
recure

l r l s

… …

nil s BST-Bedingung L R
bleibt erhalten

R (ginge auch, wenn linkes

L
-
Kind von z kein rechtes Kind)
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 73
Löschen im BST (III) -
„kleinster“ Nachfahre vom rechten KindO
von z
kad
immer links S
Ye
on von 7

oder gehe bote oder

eine
bis

keine linze kroten

mehr
hat und an
z y
diese kofe
nehme
und ersetze es
in zu lischender

Kote
M

l r l r

… …

s Y s
y

BST-Bedingung
nil L R L R
Y bleibt erhalten
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 74
Löschen: Transplantation hängt TeilbaumO
v an Elternknoten von u
v zu löschen
um

x
transplant(T,u,v) Hänge
L V an

y parent ve v
,
asn't u leer

1 IF [Link]==nil THEN steht

4-7
z 2 [Link]=v Tinker
3 ELSE -ind ist
u 4 IF u==[Link] THEN
8-9 5 [Link]=v
6 ELSE > U ist rechter Kind
-

v
7 [Link]=v;
8 IF v != nil THEN verbinden

9 [Link]=[Link];( rit Y

elen von

O
Laufzeit = Θ(1)

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 75

Löschen: Algorithmus (I)
delete(T,z) pe*.
hat 1 Kind
boote
Fall 1 : Au loschede hat
& a

J
1
z 1 IF [Link]==nil THEN Fol :

(
1-2 > maximal I -

2 transplant(T,z,[Link]) und
3 ELSE>
- linke orgette wit rahts
leer
-
,

ersetze
↑
8
4 IF [Link]==nil THEN it dieser ~

Kind
nil r 5 transplant(T,z,[Link])
ersetze mit lin
-rechte
her ,
6 ELSE
↓
7 y=[Link];
8 WHILE [Link] != nil DO y=[Link];
… …
9 IF [Link] != z THEN
10 transplant(T,y,[Link]);
11 [Link]=[Link];
12 [Link]=y;
13 transplant(T,z,y);
14 [Link]=[Link];
15 [Link]=y;
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 76
Löschen: Algorithmus (II)
delete(T,z)

1 innes
z
1 IF [Link]==nil THEN

")
7-8 i =

2 transplant(T,z,[Link]) Kind
3 ELSE
4 IF [Link]==nil THEN hat
3
Z
… kein
r 5 transplant(T,z,[Link])
rechtes
6 ELSE
king
7 y=[Link];
8 ⑨
WHILE [Link] != nil DO y=[Link];
finde
… Herste

9 IF [Link] != z THEN Mangele

ve r

y 10 transplant(T,y,[Link]); rechges
Z

11 [Link]=[Link];
9-10
12 [Link]=y;
13 transplant(T,z,y);
nil Y 14 [Link]=[Link];
15 [Link]=y;
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 77
Löschen: Algorithmus (III)
delete(T,z)
z
1 IF [Link]==nil THEN
2 transplant(T,z,[Link])
3 ELSE
… 4 IF [Link]==nil THEN
r 5 transplant(T,z,[Link])
11-12 6 ELSE
7 y=[Link];
8 WHILE [Link] != nil DO y=[Link];

8
…
9 IF =
[Link] != z THEN
19
y 10 transplant(T,y,[Link]);
11 [Link]=[Link];
12 - [Link]=y;
13 transplant(T,z,y);
nil Y 14 [Link]=[Link];
15 [Link]=y;
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 78
Löschen: Algorithmus (IV) Laufzeit = O(ℎ)
13
delete(T,z)
z y
1 IF [Link]==nil THEN
2 transplant(T,z,[Link])
3 ELSE
… 4 IF [Link]==nil THEN
14-15 5 transplant(T,z,[Link])
r
6 ELSE
7 y=[Link];
8 WHILE [Link] != nil DO y=[Link];
…
9 IF [Link] != z THEN
y 10 transplant(T,y,[Link]);
11 [Link]=[Link];
12 [Link]=y;
13 transplant(T,z,y);
nil Y 14 [Link]=[Link];
15 [Link]=y;
Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 79
Höhe Laufzeit

Binärer Suchbaum Verkettete Liste

Operation Laufzeit* Operation Laufzeit*

Einfügen O(h) Einfügen (1)
Löschen O(h) Löschen (1)
Suchen O(h) Suchen (n)

besser, wenn
viele Such-Operationen
und ℎ klein relativ zu 𝑛
-

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 80

Höhe eines &
BST Binary Search tree

Best-Case: Worst-Case:
Laufzeit = 𝑂(log 𝑛) Laufzeit = (𝑛)

ℎ = 𝑂(log 𝑛) 23 9 ℎ =𝑛−1

17

17 34
22

9 22 27 35
35

vollständig: alle Blätter haben gleiche Tiefe degeneriert: lineare Liste

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 81
Durchschnittliche Höhe? Analyse ohne Einfügen und Löschen

randomlyBuiltTree(D) //D data set

1 T=newTree();
2 WHILE D != ∅ DO
3 Pick d uniformly from D;
4 insert(T,newNode(d));
5 remove d from D;
6 return T;

Die erwartete Höhe 𝐸 ℎ des Baumes T

erzeugt durch randomlyBuiltTree(D)
für eine Datenmenge D mit 𝑛 Werten ist
𝐸 ℎ = (log 𝑛).

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 82

Suchbäume als Suchindex SELECT *
FROM MyTable
WHERE ID=27;

23
27 | Victor | CS | …

ID Name Department …
17 34
23 Bob CS …
17 Alice Math …
9 Eve CS …
9 22 27 22 Carol Physics …
34 Peggy Math …
Knoten speichert nur 27 Victor CS …
Primärschlüssel (hier ID)
und Zeiger auf Daten … … … …

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 83

Bereichssuche SELECT *
FROM MyTable
WHERE ID BETWEEN 20 AND 30;

22 | Carol | Physics | …
23
23 | Bob | CS | …
27 | Victor | CS | …

ID Name Department …
17 34
23 Bob CS …
17 Alice Math …
9 Eve CS …
9 22 27 22 Carol Physics …
34 Peggy Math …
27 Victor CS …
… … … …

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 84

Sekundärindizes CREATE INDEX …;
Carol
alphabetische
DROP INDEX …; Sortierung
für schnelle
Suche auf
Bob Peggy Namen

23
Alice Eve Victor

ID Name Department …
17 34
23 Bob CS …
17 Alice Math …
9 Eve CS …
9 22 27 22 Carol Physics …
34 Peggy Math …
27 Victor CS …
Zusätzliche Indizes kosten Speicherplatz,
daher nur sinnvoll, wenn oft gesucht wird … … … …

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 85

 Geben Sie Algorithmen für das Maximum und das-Minimum
im binären Suchbaum an. Welche Laufzeiten haben sie? ne ! =

left
X-right ! EnilDo
-

Max rechts BST

gart
in
> while

-
-

& (h) mox (T)

rot
wie the + = X -

right; 11x = x left

if
=
t
t retun XI
return Troo
X
=
T .
vo

Beschreiben Sie eine Modifikation der Einfüge-Operation,

die keine doppelten Einträge erzeugt.
1 Sucher nach Eintrag R(L)
studen (h)
.

a
ein mehr +
Füge , ver
.
2 ,
-

a(n)

Geben Sie einen Algorithmus an, der für Eingabe 𝑘

alle Werte ≤ 𝑘 eines binären Suchbaumes ausgibt.

Algorithmen und Datenstrukturen | Marc Fischlin | SS 23 | 03 Basic Data Structures | 86