עצים בתכנות מוסברים בפשטות - Trees¶
עץ בתכנות הוא אחד המבנים שברגע שרואים אותו מצויר, הכל נהיה ברור תוך שנייה. הבעיה היא שהרבה קורסים מסבירים אותו עם מונחים כמו "שורש", "עלה" ו"עומק" בלי לעצור לרגע ולהראות למה בכלל טרחו להמציא את זה. אז בואו נתחיל מהסוף - למה, ורק אחר כך איך.
עץ זה בעצם משפחתון¶
תזכרו איך נראה עץ משפחה. יש אב קדמון אחד למעלה, ממנו יורדים ילדים, מכל ילד יורדים נכדים, וכן הלאה. אין מעגלים, אין קפיצות אקראיות - כל אחד מחובר בדיוק להורה אחד מעליו, וזה נמשך למטה כמה שצריך.
זה בדיוק עץ בתכנות, רק הפוך - השורש נמצא למעלה, וההסתעפויות יורדות ממנו:
- שורש - root - הצומת העליון, נקודת ההתחלה.
- צומת - node - כל "תיבה" בעץ שמחזיקה ערך.
- ילד - child - צומת שיורד מצומת אחר.
- עלה - leaf - צומת בלי ילדים, קצה הענף.
בגלל שכל צומת מצביע לילדים שלו, ומהם אפשר להגיע לנכדים, קיבלנו מבנה היררכי טבעי - בדיוק כמו תיקיות ותתי-תיקיות במחשב שלכם, שגם הן בעצם עץ.
למה לא פשוט להשתמש ברשימה?¶
זו השאלה הנכונה לשאול. התשובה היא שהרבה מידע בעולם האמיתי הוא לא שטוח, הוא היררכי. מבנה התיקיות במחשב שלכם, עץ ה-DOM שמרכיב כל דף אינטרנט, ארגון עובדים בחברה עם מנהלים ותתי-מנהלים - כל אלה נראים איומים אם תנסו לדחוס אותם לרשימה פשוטה, ופשוטים להפליא כשמייצגים אותם כעץ.
היתרון הגדול השני של עצים הוא חיפוש מהיר, וכאן נכנס סוג מיוחד שנקרא עץ חיפוש בינארי - Binary Search Tree.
עץ חיפוש בינארי - הכוכב של המשפחה¶
בעץ חיפוש בינארי, יש כלל ברזל: לכל צומת יש לכל היותר שני ילדים, כל הערכים בענף השמאלי קטנים ממנו, וכל הערכים בענף הימני גדולים ממנו. הכלל הפשוט הזה הוא בעצם קסם.
תחשבו מה זה אומר לחיפוש. במקום לעבור איבר-איבר על כל הרשימה כמו בלש שמחפש חשוד בעיר שלמה, אתם מגיעים לשורש, שואלים "הערך שאני מחפש קטן או גדול מזה", ולפי התשובה יורדים ימינה או שמאלה - וכל פעם חוצים חצי מהאפשרויות שנשארו. זה בדיוק אותו רעיון שעומד מאחורי חיפוש בינארי, רק שבעץ הוא "מובנה" בתוך המבנה עצמו.
איפה עצים מופיעים בפועל, כל יום¶
- דפדפן האינטרנט מייצג כל עמוד HTML כעץ, שנקרא DOM, וזה מה שמאפשר לג'אווהסקריפט לשנות חלקים ספציפיים בעמוד.
- מסדי נתונים משתמשים בעצים כדי לאנדקס מידע ולחפש בו במהירות בטירוף, גם כשיש מיליוני שורות.
- מערכת הקבצים במחשב שלכם היא עץ, כאשר כל תיקייה היא צומת עם תתי-תיקיות כילדים.
- קבלת החלטות במשחקי מחשב, כמו שחמט, מיוצגת לרוב כעץ של מהלכים אפשריים.
ברגע שתראו כמה שכיח המבנה הזה, יהיה קשה להתעלם ממנו - הוא פשוט נמצא בכל מקום שיש בו היררכיה טבעית.
איך מתרגלים עצים בלי להתבלבל¶
הטעות הכי נפוצה היא לנסות להבין את כל סוגי העצים בבת אחת. תתחילו רק עם עץ חיפוש בינארי. תבנו קלאס לצומת עם ערך, ילד שמאלי וילד ימני, תכתבו פונקציה שמוסיפה ערכים לעץ, ואחר כך פונקציה שמחפשת ערך בעץ. רק אחרי שזה מרגיש טבעי, תעברו לרעיונות מתקדמים יותר כמו מעברים על העץ.
בקורס התכנות הבסיסי שלנו בונים את היסודות האלה שלב אחר שלב, כך שכשתגיעו לעצים, כבר יהיה לכם את כל הכלים כדי להבין אותם באמת ולא רק לשנן.
תתחילו את קורס התכנות הבסיסי כאן
לסיכום¶
עץ הוא פשוט דרך לייצג היררכיה - שורש אחד למעלה, ענפים שיורדים ממנו. עץ חיפוש בינארי מוסיף לזה כלל סדר פשוט שהופך חיפוש למהיר להפליא. ברגע שראיתם את זה מצויר פעם אחת, קשה לשכוח.
יש לכם שאלות בדרך? בואו לדיסקורד שלנו ותשאלו בלי בושה, כל השאלות שם לגיטימיות.