ההבדל בין עץ לתרשים
תוֹכֶן
עץ וגרף נכנסים לקטגוריה של מבנה נתונים לא ליניארי בו עץ מציע דרך שימושית מאוד לייצג קשר בין הצמתים במבנה היררכי וגרף עוקב אחר מודל רשת. העץ והגרף נבדלים זה מזה בכך שיש לחבר מבנה עץ ולעולם לא יכולים להיות לו לולאות כאשר בתרשים אין מגבלות כאלה.
מבנה נתונים לא ליניארי מורכב מאוסף האלמנטים המופצים על מטוס כלומר אין רצף כזה בין האלמנטים כפי שהוא קיים במבנה נתונים ליניארי.
-
- טבלת השוואה
- הגדרה
- הבדלים עיקריים
- סיכום
טבלת השוואה
| בסיס להשוואה | עץ | גרף |
|---|---|---|
| נתיב | רק אחד בין שני קודקודים. | יותר מדרך אחת מותרת. |
| צומת שורש | יש לו צומת שורש אחד בדיוק. | לתרשים אין צומת שורש. |
| לולאות | אין לולאות מותרות. | בתרשים יכולים להיות לולאות. |
| מורכבות | פחות מורכב | יחסית מורכב יחסית |
| טכניקות מעבר | הזמנה מראש, בהזמנה ובהזמנה מראש. | חיפוש רוחב ראשון וחיפוש עומק ראשון. |
| מספר הקצוות | n-1 (כאשר n הוא מספר הצמתים) | לא מוגדר |
| סוג הדגם | היררכי | רשת |
הגדרת עץ
א עץ הוא אוסף סופי של פריטי נתונים המכונים בדרך כלל צמתים. כפי שהוזכר לעיל, עץ הוא מבנה נתונים לא ליניארי המסדר פריטי נתונים בסדר ממוין. הוא משמש להצגת מבנה היררכי בין מרכיבי הנתונים השונים ומארגן את הנתונים לסניפים הקשורים למידע. תוספת של קצה חדש בעץ מביאה להיווצרות לולאה או מעגל.
ישנם מספר סוגים של עצים כמו עץ בינארי, עץ חיפוש בינארי, AVL עץ, עץ בינארי מושחל, עץ B וכו '. דחיסת נתונים, אחסון קבצים, מניפולציה של הביטוי האריתמטי ועצי משחק הם חלק מהיישום של העץ. מבנה נתונים.
מאפייני העץ:
- בחלקו העליון של העץ נקרא צומת המכונה שורש העץ.
- פריטי הנתונים הנותרים מחולקים לקבוצות משנה לא צמודות המכונות תת-משנה.
- העץ מורחב בגובהו לכיוון התחתית.
- עץ חייב להיות מחובר שפירושו שיש מסלול משורש אחד לכל הצמתים האחרים.
- הוא אינו מכיל לולאות.
- לעץ יש קצוות N-1.
ישנם מונחים שונים הקשורים לעצים כגון צומת מסוף, קצה, מפלס, דרגה, עומק, יער וכו '. בין אותם מונחים, חלקם מתוארים להלן.
- קצה - קו המחבר בין שני צמתים.
- רמה - עץ מחולק למפלסים כך שצומת השורש הוא ברמה 0. לאחר מכן, ילדיו המיידים נמצאים ברמה 1, וילדיו המיידיים הם ברמה 2 וכן הלאה עד למסוף או לצומת העלים.
- תואר - זהו מספר תת העץ של צומת בעץ נתון.
- עומק - זוהי הרמה המקסימאלית של כל צומת בעץ נתון ומכונה גם גובה.
- צומת מסוף - הצומת ברמה הגבוהה ביותר הוא צומת מסוף ואילו צמתים אחרים פרט לצומת מסוף ושורש ידועים כצמתים לא סופניים.
הגדרת הגרף
א גרף הוא גם מבנה נתונים לא-לינארי מתמטי שיכול לייצג סוגים שונים של מבנה פיזי. זה מורכב מקבוצה של קודקודים (או צמתים) ומערכת קצוות המחברים בין שני הקודקודים. קודקודים בתרשים מיוצגים כנקודה או עיגולים ושוליים מוצגים כקשתות או קטעי קו. קצה מיוצג על ידי E (v, w) כאשר v ו- w הם זוג הקודקודים. הסרת קצה ממעגל או גרף מחובר יוצרת תת-גרף שהוא עץ.
הגרפים מסווגים לקטגוריות שונות כמו בימוי, לא מכוון, מחובר, לא מחובר, פשוט ורב גרף. רשת מחשבים, מערכת תחבורה, גרף רשת חברתית, מעגלי חשמל ותכנון פרויקטים הם חלק מהיישומים של מבנה נתוני הגרפים. זה משמש גם בטכניקת ניהול הנקראת PERT (הערכת תוכנית וטכניקת סקירה) מחיר לאלף הופעות (שיטת נתיב קריטי) בה מנותח מבנה הגרף.
מאפייני גרף:
- קודקוד בתרשים ניתן לחבר לכל מספר קודקודים אחרים באמצעות קצוות.
- ניתן לכוון קצה או לכוון אותו.
- ניתן לשקלל קצה.
גם בתרשים אנו משתמשים במונחים שונים כמו קודקודים סמוכים, נתיב, מחזור, דרגה, גרף מחובר, גרף מלא, גרף משוקלל וכו '. בואו נבין כמה ממונחים אלה.
- קודקודים סמוכים - קודקוד a צמוד לקודקוד b אם יש קצה (a, b) או (b, a).
- נתיב - נתיב מקודקוד w הוא רצף קודקודים סמוך.
- מחזור - זהו מסלול בו הקודקודים הראשונים והאחרונים זהים.
- תואר - זהו מספר קצוות המתרחשים בקודקוד.
- גרף מחובר - אם קיים מסלול מקודקוד אקראי לכל קודקוד אחר, הגרף הזה ידוע כגרף מחובר.
- בעץ קיים נתיב אחד בלבד בין שני קודקודים ואילו לתרשים יכולים להיות נתיבים חד כיווניים ודו כיווניים בין הצמתים.
- בעץ יש בדיוק צומת שורש אחת, וכל ילד יכול להיות רק הורה אחד. לעומת זאת, בתרשים, אין מושג של צומת השורש.
- עץ לא יכול להיות בעל לולאות ולולאות עצמיות בעוד שבגרף יכולות להיות לולאות ולולאות עצמיות.
- גרפים מורכבים יותר מכיוון שיכולים להיות לולאות ולולאות עצמיות. לעומת זאת, עצים פשוטים בהשוואה לתרשים.
- העץ חוצה בטכניקות של הזמנה מראש, בהזמנה ובהמשך. מצד שני, למעבר גרפים, אנו משתמשים ב- BFS (חיפוש הראשון ברוחב) וב- DFS (עומק ראשון חיפוש).
- לעץ יכולות להיות קצוות N-1. להפך, בתרשים, אין מספר מוגדר מראש של קצוות, וזה תלוי בתרשים.
- לעץ מבנה היררכי ואילו לתרשים יש מודל רשת.
סיכום
גרף ועץ הם מבנה הנתונים הלא לינארי המשמש לפיתרון בעיות מורכבות שונות. גרף הוא קבוצה של קודקודים וקצוות שבהם קצה מחבר בין זוג קודקודים ואילו עץ נחשב כגרף מחובר מינימלי אשר חייב להיות מחובר ונקי מלולאות.
