1 of 101

רקורסיות

מבנה נתונים

סיכום

צביקה ברגר

בס"ד

2 of 101

הגדרות

​

​

בס"ד

  • Big 0:��
  • Big Ω:�
  • Big θ:

​

​

3 of 101

שיטת האב

​

​

  • כדי לחשב זמן ריצה של פונקציה רקורסיבית נשתמש בשיטת האב.
    • נפתח נוסחא שמתארת את הפונקציה מהצורה:

​

​

​

​

​

בס"ד

4 of 101

סיבוכיות - שיטת האב

​

​

  • נסתכל על הפונקציה :

​

​

בס"ד

5 of 101

מיונים

בס"ד

6 of 101

מיון

בס"ד

1

3

8

4

2

9

6

7

5

7 of 101

מיון

בס"ד

1

3

8

4

2

9

6

7

5

9

8

7

6

5

4

3

2

1

8 of 101

מיונים מוכרים

​

  • Bubble sort
  • Merge sort
  • Quick sort
  • Insertion sort
  • Heap sort

בס"ד

9 of 101

Bubble sort

​

    • בכל איטרציה נעבור על המערך עם "חלון" בגודל 2.

​

    • נבדוק אם יש צורך לבצע החלפה מקומית, ונבצע את ההחלפה.
      • השוואה והחלפה הם הכלים הבסיסיים של האלגוריתם הזה.

​

    • בסיום כל איטרציה המקסימום "ביעבע" לסוף המערך.
      • בתחילת איטרציה i מובטח לנו שיש i איברים שלא צריך לבדוק בסוף המערך.

​

    • מספר האיטרציות הכולל צריך להיות size-1.
      • כי באיטרציה הזו אנו מסדרים גם את האיבר המינימלי.

​

בס"ד

10 of 101

Bubble sort

בס"ד

1

3

8

4

2

9

6

7

5

מספר האיטרציה (i)

0

11 of 101

Bubble sort

בס"ד

1

3

8

4

2

9

6

7

5

מספר האיטרציה (i)

0

1

3

8

4

2

9

6

7

5

מספר האיטרציה (i)

0

מיקום במערך (j)

0

12 of 101

Bubble sort

בס"ד

1

3

8

4

2

9

6

7

5

מספר האיטרציה (i)

0

מיקום במערך (j)

1

13 of 101

Bubble sort

בס"ד

1

3

8

4

2

9

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

1

14 of 101

Bubble sort

בס"ד

1

3

8

4

2

9

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

2

15 of 101

Bubble sort

בס"ד

1

3

8

4

2

9

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

3

16 of 101

Bubble sort

בס"ד

1

3

8

4

9

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

3

17 of 101

Bubble sort

בס"ד

1

3

8

4

9

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

4

18 of 101

Bubble sort

בס"ד

1

3

8

9

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

4

19 of 101

Bubble sort

בס"ד

1

3

8

9

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

5

20 of 101

Bubble sort

בס"ד

1

3

9

8

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

5

21 of 101

Bubble sort

בס"ד

1

3

9

8

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

6

22 of 101

Bubble sort

בס"ד

1

9

3

8

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

6

23 of 101

Bubble sort

בס"ד

1

9

3

8

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

7

24 of 101

Bubble sort

בס"ד

9

1

3

8

4

2

7

6

5

מספר האיטרציה (i)

0

מיקום במערך (j)

7

נדאג לא לגלוש מגבולות המערך

for (int j = 0; j < size-1; j++)

25 of 101

Bubble sort

בס"ד

9

1

3

8

4

2

7

6

5

מספר האיטרציה (i)

1

26 of 101

Bubble sort

בס"ד

9

1

3

8

4

2

7

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

0

27 of 101

Bubble sort

בס"ד

9

1

3

8

4

2

7

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

1

28 of 101

Bubble sort

בס"ד

9

1

3

8

4

2

7

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

2

29 of 101

Bubble sort

בס"ד

9

1

3

8

4

7

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

2

30 of 101

Bubble sort

בס"ד

9

1

3

8

4

7

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

3

31 of 101

Bubble sort

בס"ד

9

1

3

8

7

4

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

3

32 of 101

Bubble sort

בס"ד

9

1

3

8

7

4

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

4

33 of 101

Bubble sort

בס"ד

9

1

3

8

7

4

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

5

34 of 101

Bubble sort

בס"ד

9

1

8

3

7

4

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

5

35 of 101

Bubble sort

בס"ד

9

1

8

3

7

4

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

6

36 of 101

Bubble sort

בס"ד

9

8

1

3

7

4

2

6

5

מספר האיטרציה (i)

1

מיקום במערך (j)

6

נשפר את התנאי

for (int j = 0; j < size-1-i; j++)

37 of 101

Bubble sort

בס"ד

9

8

1

3

7

4

2

6

5

מספר האיטרציה (i)

2

38 of 101

Bubble sort

בס"ד

9

8

1

3

7

4

2

6

5

מספר האיטרציה (i)

2

39 of 101

Bubble sort

בס"ד

9

8

7

1

3

6

4

2

5

מספר האיטרציה (i)

3

40 of 101

Bubble sort

בס"ד

9

8

7

1

3

6

4

2

5

מספר האיטרציה (i)

3

41 of 101

Bubble sort

בס"ד

9

8

7

6

1

3

5

4

2

מספר האיטרציה (i)

4

42 of 101

Bubble sort

בס"ד

9

8

7

6

1

3

5

4

2

מספר האיטרציה (i)

4

43 of 101

Bubble sort

בס"ד

9

8

7

6

5

1

3

4

2

מספר האיטרציה (i)

5

44 of 101

Bubble sort

בס"ד

9

8

7

6

5

1

3

4

2

מספר האיטרציה (i)

5

45 of 101

Bubble sort

בס"ד

9

8

7

6

5

4

1

3

2

מספר האיטרציה (i)

6

46 of 101

Bubble sort

בס"ד

9

8

7

6

5

4

1

3

2

מספר האיטרציה (i)

6

מיקום במערך (j)

0

47 of 101

Bubble sort

בס"ד

9

8

7

6

5

4

1

3

2

מספר האיטרציה (i)

6

מיקום במערך (j)

1

48 of 101

Bubble sort

בס"ד

9

8

7

6

5

4

3

1

2

מספר האיטרציה (i)

6

מיקום במערך (j)

1

49 of 101

Bubble sort

בס"ד

9

8

7

6

5

4

3

1

2

מספר האיטרציה (i)

7

50 of 101

Bubble sort

בס"ד

9

8

7

6

5

4

3

1

2

מספר האיטרציה (i)

7

מיקום במערך (j)

0

51 of 101

Bubble sort

בס"ד

9

8

7

6

5

4

3

2

1

מספר האיטרציה (i)

7

מיקום במערך (j)

0

52 of 101

Bubble sort

בס"ד

9

8

7

6

5

4

3

2

1

מספר האיטרציה (i)

8

אין צורך לבצע

נגדיר את מספר האיטרציות

for (int i = 0; i < size-1; i++)

53 of 101

Bubble sort

בס"ד

9

8

7

6

5

4

3

2

1

for (int i = 0; i < size-1; i++)

for (int j = 0; j < size-1-i; j++)

if (should_swap(j, j+1))

swap(j, j+1)

54 of 101

Bubble sort

בס"ד

9

8

7

6

5

4

3

2

1

for (int i = 0; i < size-1; i++)

for (int j = 0; j < size-1-i; j++)

if (should_swap(j, j+1))

swap(j, j+1)

 

55 of 101

Merge Sort

בס"ד

56 of 101

Quick sort

בס"ד

1

4

2

0

5

6

9

8

1

7

2

//determining the pivot

swap(vec, left, (left+right)/2);

57 of 101

Quick sort

בס"ד

//determining the pivot

swap(vec, left, (left+right)/2);

6

4

2

0

5

1

9

8

1

7

2

k

58 of 101

Quick sort

בס"ד

6

4

2

0

5

1

9

8

1

7

2

last

i

left

right

last

i

last

i

last

i

last

i

last

i

i

i

//moving all the smaller element

for (i=left+1; i<=right; i++)

if (vec[i] < vec[left])

swap(vec, ++last, i);

59 of 101

Quick sort

בס"ד

6

4

2

0

5

1

1

8

9

7

2

k

last

i

last

i

left

right

//moving all the smaller element

for (i=left+1; i<=right; i++)

if (vec[i] < vec[left])

swap(vec, ++last, i);

60 of 101

Quick sort

בס"ד

6

4

2

0

5

1

1

8

9

7

2

k

last

i

left

right

//moving all the smaller element

for (i=left+1; i<=right; i++)

if (vec[i] < vec[left])

swap(vec, ++last, i);

61 of 101

Quick sort

בס"ד

6

4

2

0

5

1

1

2

9

7

8

k

last

i

left

right

//moving all the smaller element

for (i=left+1; i<=right; i++)

if (vec[i] < vec[left])

swap(vec, ++last, i);

62 of 101

Quick sort

בס"ד

2

4

2

0

5

1

1

6

9

7

8

last

i

left

right

//moving the pivot to its place

swap(vec,left,last);

63 of 101

Quick sort

בס"ד

2

4

2

0

5

1

1

left

right

left

right

9

7

8

//continue sorting both sides

qsort(vec, left, last-1);

qsort(vec, last+1, right);

6

64 of 101

מיונים מוכרים

​

  • Bubble sort -
  • Merge sort -
  • Quick sort -
  • Insertion sort -
  • Heap sort -

בס"ד

 

 

 

 

 

65 of 101

עצים

בס"ד

66 of 101

עצים

בס"ד

67 of 101

עצים

בס"ד

68 of 101

מבני נתונים לינאריים

בס"ד

69 of 101

בס"ד

70 of 101

בס"ד

71 of 101

בס"ד

72 of 101

עצים בינאריים

בס"ד

73 of 101

הגדרות בסיסיות

  • שורש
  • עלה – קודקוד ללא בנים.
  • עומק קודקוד – אורך המסלול (הפשוט) מהשורש לקודקוד.
  • רמה – קבוצת קודקודים בעומק מסוים בעץ.
  • גובה העץ – עומק העלה העמוק ביותר.

​

73

0

1

2

3

74 of 101

הוכחות בעצים

  •  

74

75 of 101

אינדוקציה על מבנה העץ

  •  

75

 

 

 

 

 

76 of 101

סריקות בעצים בינאריים

  • שלוש סריקות DFS לעצים בינאריים:
    • תחילית– pre-order
    • תוכית – in-order
    • סופית – post-order

​

  • סריקת BFS

76

 

 

1

2

3

1

2

3

1

2

3

Depth First Search – חיפוש לעומק

Breadth First Search – חיפוש לרוחב

77 of 101

Pre-order

77

  1. Check if the current node is empty or null.
  2. Display the data part of the root (or current node).
  3. Traverse the left subtree by recursively calling the pre-order function.
  4. Traverse the right subtree by recursively calling the pre-order function

78 of 101

In-order

78

  1. Check if the current node is empty or null.
  2. Traverse the left subtree by recursively calling the in-order function.
  3. Display the data part of the root (or current node).
  4. Traverse the right subtree by recursively calling the in-order function.

79 of 101

Post-order

79

  1. Check if the current node is empty or null.
  2. Traverse the left subtree by recursively calling the post-order function.
  3. Traverse the right subtree by recursively calling the post-order function.
  4. Display the data part of the root (or current node).

80 of 101

hash

בס"ד

81 of 101

גיבוב

  • נרצה ליצור מילון שיהיו בו זוגות של {מפתח, ערך}.

בס"ד

82 of 101

בס"ד

83 of 101

מזג חפש

בס"ד

84 of 101

Union find

בס"ד

85 of 101

דוגמא שימוש

  • דוגמא לשימוש ב-union find היא חישוב רכיבי קשירות תחת הוספת קשתות לגרף.

הגרף מתחיל בלי קשתות (וכל קדקוד הוא רכיב קשירות).

בכל פעם שמוסיפים קשת ייתכן ששני רכיבי קשירות יתמזגו ונרצה לאחד אותם.

​

בס"ד

86 of 101

עצים

בס"ד

87 of 101

מימוש עם רשימות מקושרות

בס"ד

88 of 101

ייעול 1

בס"ד

89 of 101

ייעול 1

בס"ד

90 of 101

ייעול 2

בס"ד

91 of 101

ייעול 2

בס"ד

92 of 101

ייעול 2

בס"ד

93 of 101

עצים

בס"ד

94 of 101

מימוש על ידי יער

בס"ד

95 of 101

כיווץ מסלולים

בס"ד

96 of 101

כיווץ מסלולים

בס"ד

97 of 101

Heap

בס"ד

98 of 101

פעולות נדרשות�תור עדיפויות - Priority Queue

  • נרצה מבנה נתונים התומך בפעולות:
    • (בנייה)
    • הכנסה עם עדיפות
    • הוצאת מינימום
    • החזרת המינימום ללא הוצאה (״הצצה״)

​

​

בס"ד

99 of 101

ערימה בינארית

בס"ד

80

45

20

8

15

12

5

70

21

33

7

90

100 of 101

ערימה בינארית

בס"ד

101 of 101

עצים

בס"ד