1 of 65

Data Structures – Recitation 5

Shay Golan

1

2 of 65

עץ בינארי מאוזן

2

3 of 65

עץ חיפוש מאוזן

3

4 of 65

עצי AVL

4

5 of 65

עצי AVL

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

5

6 of 65

למה

6

7 of 65

עדכונים

שומרים בכל קודקוד את ״מקדם האיזון״ האם שני תתי העצים באותו גובה, או מי מהם גבוה מהשני /,|,\ או פשוט -1,0,1.

7

8 of 65

רוטציות

הפעולה הבסיסית:

8

9 of 65

רוטציות

הפעולה הבסיסית:

9

10 of 65

רוטציות

הפעולה הבסיסית:

10

11 of 65

הכנסה לעץ AVL

שני שלבים:

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

11

12 of 65

הפרות איזון

שני מקרים:

״המקרה החיצוני״
״המקרה הפנימי״

12

13 of 65

הפרות איזון – המקרה החיצוני

מקרה א׳, ״המקרה החיצוני״
LL או RR

13

2

1/0

14 of 65

הפרות איזון – המקרה החיצוני

מקרה א׳, ״המקרה החיצוני״
LL או RR

14

1/0

0/-1

15 of 65

הפרות איזון – המקרה הפנימי

מקרה ב׳, ״המקרה הפנימי״

15

2

-1

16 of 65

הפרות איזון – המקרה הפנימי

מקרה ב׳, ״המקרה הפנימי״

16

1

-2

17 of 65

הפרות איזון – המקרה הפנימי

מקרה ב׳, ״המקרה הפנימי״

סיבוב אחד לא מספיק

17

2

-1

18 of 65

הפרות איזון – המקרה הפנימי

18

2

1

19 of 65

הפרות איזון – המקרה הפנימי

19

20 of 65

מחיקת ערך

גם כן בשני שלבים:

מחיקה מעץ חיפוש בינארי
תיקון הפרות איזון

20

21 of 65

מחיקה מעץ חיפוש בינארי

עלה – מוחקים
קודקוד עם בן יחיד, ״מדלגים״ על הקודקוד הנמחק ומוחקים.
קודקוד עם שני בנים: מוצאים את המקסימלי בתת העץ השמאלי, מחליפים עם הקודקוד הנמחק, ואז מוחקים. מובטח שאין לו שני בנים.

הפרות האיזון נפתרות בדומה להכנסה.

21

22 of 65

סיכום המקרים

https://visualgo.net/en/bst

22

23 of 65

23

24 of 65

24

25 of 65

25

26 of 65

26

27 of 65

27

28 of 65

28

29 of 65

"מרחק רוטציות"

29

30 of 65

שאלה - רוטציות

30

31 of 65

שאלה - רוטציות

31

32 of 65

שאלה - רוטציות

32

33 of 65

שאלה - רוטציות

33

34 of 65

34

35 of 65

שאלה - עץ AVL ממערך ממוין

35

36 of 65

שאלה - עץ AVL ממערך ממוין

נרצה להשתמש בעובדה שהמערך ממוין לצורך שיפור זמן הריצה.
הרעיון – נבנה את העץ על פי המערך, ונוכיח שהתוצאה היא עץ AVL חוקי.
נבחר לשורש את החציון, ונבנה באופן רקורסיבי על שני החצאים.
אם אורך (תת-)המערך הוא זוגי, נבחר את החציון העליון ונבנה באופן רקורסיבי על שני החצאים.

36

37 of 65

שאלה - עץ AVL ממערך ממוין

37

1

3

4

6

7

12

15

17

20

25

31

33

37

40

42

46

52

58

63

64

65

80

85

38 of 65

שאלה - עץ AVL ממערך ממוין

38

1

3

4

6

7

12

15

17

20

25

31

33

37

40

42

46

52

58

63

64

65

80

85

39 of 65

שאלה - עץ AVL ממערך ממוין

39

1

3

4

6

7

12

15

17

20

25

31

33

37

40

42

46

52

58

63

64

65

80

85

40 of 65

שאלה - עץ AVL ממערך ממוין

40

1

3

4

6

7

12

15

17

20

25

31

33

37

40

42

46

52

58

63

64

65

80

85

41 of 65

שאלה - עץ AVL ממערך ממוין

41

1

3

4

6

7

12

15

17

20

25

31

33

37

40

42

46

52

58

63

64

65

80

85

42 of 65

שאלה - עץ AVL ממערך ממוין

42

43 of 65

שאלה - עץ AVL ממערך ממוין

43

1

3

4

6

7

12

15

17

20

25

31

33

37

40

42

46

52

58

63

64

65

80

85

44 of 65

שאלה - עץ AVL ממערך ממוין

44

45 of 65

שאלה - עץ AVL ממערך ממוין

45

46 of 65

שאלה - עץ AVL ממערך ממוין

46

47 of 65

שאלה - עץ AVL ממערך ממוין

47

48 of 65

שאלה - עץ AVL ממערך ממוין

48

49 of 65

שאלה - עץ AVL ממערך ממוין

49

50 of 65

מיון בעזרת עץ AVL

50

51 of 65

מיון בעזרת AVL

51

52 of 65

מיון בעזרת AVL

52

53 of 65

מיון בעזרת AVL

53

54 of 65

מיזוג שני עצי AVL

54

55 of 65

מיזוג שני עצי AVL כלליים

55

56 of 65

מיזוג שני עצי AVL כלליים

56

57 of 65

מיזוג עצי AVL מופרדים

57

58 of 65

מיזוג שני עצי AVL מופרדים

58

59 of 65

מיזוג שני עצי AVL מופרדים

59

60 of 65

מיזוג שני עצי AVL מופרדים

60

61 of 65

מיזוג שני עצי AVL מופרדים

61

בכל עץ בינארי

62 of 65

מיזוג שני עצי AVL מופרדים

הגובה של תת-העץ המושרש בקודקוד הימני ביותר – 0 או 1.
הגובה של תת-העץ המושרש באביו גדול ב1 או ב2.
ההפרש בגבהים בין העצים המושרשים בכל שני קודקודים סמוכים על המסלול הוא 1 או 2.
מקבלים סדרת גבהים עם הפרש� 1 או 2 בין כל קודקוד לאביו

62

63 of 65

מיזוג שני עצי AVL מופרדים

63

s

64 of 65

מיזוג שני עצי AVL מופרדים

64

s

65 of 65

מיזוג שני עצי AVL מופרדים

65