"
"
"
 n
 O(1)
n O(n)
O(1)
+ n + 1
= O(1) + O(n) + O(1) = O(n)
n-1
n - 1
O(n)
TAB:
[1] [2] [3] [4] [5]
Ś N I E G
TAB:
[1] [2] [3] [4] [5]
Ś N I E G
Odczyt: TAB[2] ?
TAB:
[1] [2] [3] [4] [5]
Ś N I E G
Odczyt: TAB[2] = N
TAB:
[1] [2] [3] [4] [5]
Ś N I E G
Wyszukanie: TAB[i] = N ?
TAB:
[1] [2] [3] [4] [5]
Ś N I E G
Wyszukanie: TAB[i] = N ?
TAB:
[1] [2] [3] [4] [5]
Ś N I E G
Wyszukanie: TAB[i] = N ?
TAB:
[1] [2] [3] [4] [5]
Ś N I E G
Wyszukanie: TAB[i] = N ? i = 2.
TAB:
[1] [2] [3] [4] [5]
Ś N I E G
Usuwanie: TAB[2]
TAB:
[1] [2] [3] [4] [5]
Ś I E G
Usuwanie: TAB[2]
TAB:
[1] [2] [3] [4] [5]
Ś I E G
Usuwanie: TAB[2]
TAB:
[1] [2] [3] [4] [5]
Ś I E G
Usuwanie: TAB[2]
TAB:
[1] [2] [3] [4]
Ś I E G
Usuwanie: TAB[2]
TAB:
[1] [2] [3] [4]
Ś I E G
Wstawianie: TAB[2] = C
TAB:
[1] [2] [3] [4] [5]
Ś I E G
Wstawianie: TAB[2] = C
TAB:
[1] [2] [3] [4] [5]
Ś I E G
Wstawianie: TAB[2] = C
TAB:
[1] [2] [3] [4] [5]
Ś I E G
Wstawianie: TAB[2] = C
TAB:
[1] [2] [3] [4] [5]
Ś I E G
Wstawianie: TAB[2] = C
TAB:
[1] [2] [3] [4] [5]
Ś C I E G
Wstawianie: TAB[2] = C
 n - 1
O(n)
O(n)
O(1)
O(1) O(1)
O(1)
O(1)
O(n)
O(1) O(n)
LST:
T U J A
LST:
T U J A
LST:
T U J A
Odczyt: LST[3] ?
LST:
T U J A
Odczyt: LST[3] ?
LST:
T U J A
Odczyt: LST[3] ?
LST:
T U J A
Odczyt: LST[3] ?
LST:
T U J A
Odczyt: LST[3] = J
LST:
T U J A
Wyszukanie: LST[i] = J ?
LST:
T U J A
Wyszukanie: LST[i] = J ?
LST:
T U J A
Wyszukanie: LST[i] = J ?
LST:
T U J A
Wyszukanie: LST[i] = J ? i = 3.
LST:
T U J A
Usuwanie: LST[3]
LST:
T U J A
Usuwanie: LST[3]
LST:
T U J A
Usuwanie: LST[3]
LST:
T U J A
Usuwanie: LST[3]
LST:
T U J A
Usuwanie: LST[3]
LST:
T U A
Usuwanie: LST[3]
LST:
T U A
Wstawianie: LST[1] = B
LST:
T U A
B
Wstawianie: LST[1] = B
LST:
T U A
B
Wstawianie: LST[1] = B
LST:
T U A
B
Wstawianie: LST[1] = B
LST:
B T U A
Wstawianie: LST[1] = B
O(n/2) = O(n)
Lista dwukierunkowa:
K O T
Lista dwukierunkowa cykliczna:
K O T
 O(1)
O(1)
O(n)
O(1) O(n)
Realizacja listy za pomocą tablicy:
[1] [2] [3] [4] [5] [6]
Ś N I E Ć
6 4 5 1
2
 O(1)
O(n)
 O(1)
O(n)
Kolejka:
WE WY
5 11 9 3 9 0
Stos:
WE
5 11 9 3 9 0
WY
 O(1) O(n)
O(n)
 e" 0
Drzewo
korzeń
rodzic węzła x
x
potomek węzła x
liście
 k
"
"
Drzewo binarne pełne
[1]
[2]
[3]
k = 4 poziomy
[7]
[5]
[5]
[6]
[6]
[4]
[4]
[12] [13] [14] [15]
[11]
[8] [9] [10]
n = 15 elementów
20 + 21 + 22 + . . . + 2k-1 = n.
1 - qn
a0 + a0q + a0q2 + . . . + a0qn-1 = a0 ,
1 - q
a0 = 1 q = 2
2k - 1 = n.
k = log2(n + 1),
k = O(log n)
 n/2
Kopiec zbudowany z n = 10 elementów: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
[1]
element maksymalny
12
[2]
[3]
8 e" max {1, 2}
8
9
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
7 1 2
[8] [9] [10]
3 6 4
element �łn/2�ł
 O(1)
O(log n)
O(log n)
n
n
O(n log n)
Usunięcie elementu z kopca:
[1]
12
[2]
[3]
8
9
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
7 1 2
[8] [9] [10]
3 6 4
Usunięcie elementu z kopca:
[1]
12
[2]
[3]
8
9
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
7 1 2
[8] [9] [10]
3 6 4
Usunięcie elementu z kopca:
[1]
[2]
[3]
8
9
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
7 1 2
[8] [9] [10]
3 6 4
Usunięcie elementu z kopca:
[1]
4
[2]
[3]
8
9
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
7 1 2
[8] [9]
3 6
Usunięcie elementu z kopca:
[1]
4
[2]
[3]
8
9
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
7 1 2
[8] [9]
3 6
Usunięcie elementu z kopca:
[1]
9
[2]
[3]
8
4
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
7 1 2
[8] [9]
3 6
Usunięcie elementu z kopca:
[1]
9
[2]
[3]
8
4
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
7 1 2
[8] [9]
3 6
Usunięcie elementu z kopca:
[1]
9
[2]
[3]
8
7
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
4 1 2
[8] [9]
3 6
Usunięcie elementu z kopca:
[1]
9
[2]
[3]
8
7
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
4 1 2
[8] [9]
3 6
Usunięcie elementu z kopca:
[1]
9
[2]
[3]
8
7
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
6 1 2
[8] [9]
3 4
Usunięcie elementu z kopca:
[1]
9
[2]
[3]
8
7
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
6 1 2
[8] [9]
3 4
Wstawianie nowego elementu do kopca:
8
[1]
9
[2]
[3]
8
7
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
6 1 2
[8] [9]
3 4
Wstawianie nowego elementu do kopca:
8
[1]
9
[2]
[3]
8
7
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
6 1 2
[8] [9] [10]
3 4 8
Wstawianie nowego elementu do kopca:
8
[1]
9
[2]
[3]
8
7
[7]
[5]
[5]
[6]
[6]
[4]
[4]
5
6 1 2
[8] [9] [10]
3 4 8
Wstawianie nowego elementu do kopca:
8
[1]
9
[2]
[3]
8
7
[7]
[5]
[5]
[6]
[6]
[4]
[4]
8
6 1 2
[8] [9] [10]
3 4 5
Wstawianie nowego elementu do kopca:
8
[1]
9
[2]
[3]
8
7
[7]
[5]
[5]
[6]
[6]
[4]
[4]
8
6 1 2
[8] [9] [10]
3 4 5
Wstawianie nowego elementu do kopca:
8
[1]
9
[2]
[3]
8
8
[7]
[5]
[5]
[6]
[6]
[4]
[4]
7
6 1 2
[8] [9] [10]
3 4 5
Wstawianie nowego elementu do kopca:
8
[1]
9
[2]
[3]
8
8
[7]
[5]
[5]
[6]
[6]
[4]
[4]
7
6 1 2
[8] [9] [10]
3 4 5
Wstawianie nowego elementu do kopca:
8
[1]
9
[2]
[3]
8
8
[7]
[5]
[5]
[6]
[6]
[4]
[4]
7
6 1 2
[8] [9] [10]
3 4 5
 O(1) O(n) O(n) O(n)
O(n) O(n) O(1) O(n)
O(1) O(n) O(1) O(n)
O(1) O(n) O(1) O(n)
O(1) O(n log n) O(log n) O(log n)
"
"
"
 x
x x
x
Przykłady drzew BST dla danych: {8, 3, 1, 5, 6, 9, 2, 12, 7, 4}
3
7
9
4
3 1
k = 4
2 5
5
1 8 12
6
k = 7
2
4 6
9
8
12
7
 k log n n
k
O(log n)
O(k)
O(k)
"
"
"
O(log n)
Przykład drzewa czerwono-czarnego
7
9
3
12
8
5
1
NIL NIL
NIL NIL
NIL
2
4 6
NIL NIL
NIL NIL NIL NIL
 n
m
m d" n
h(k)
k [0, m - 1]
k
 h(k) = j j
0 d" j < m
O(1)
h(k) = k mod m.
m
Przykładowa tablica haszująca
16 40 36 100
0
5
1
38 14
2
95 99
3
m = 4; n = 9