מדריך למתחילים לעצים בינאריים

אם למדת קורס מבני נתונים בתואר במדעי המחשב שלך, או אם אתה מתכנת אוטודידקט, רוב הסיכויים שנתקלת במונח "עצים בינאריים". למרות שהם עשויים להישמע מעט סוחפים ומורכבים, הרעיון של עץ בינארי הוא די פשוט.

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

מהם עצים בינאריים?

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

הצומת הראשון בעץ בינארי נקרא "השורש". צמתים ברמה האחרונה בעץ נקראים עלים.

כל צומת מכיל פריט נתונים ושתי מצביעי צומת. עץ בינארי ריק מיוצג על ידי מצביע null. כפי שכבר הבנתם, לעצים בינאריים יכולים להיות שני ילדים בלבד (ומכאן השם).

סוגי מבני עץ בינארי

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

קָשׁוּר: הדרכים הטובות ביותר ללמוד כיצד לבצע קוד בחינם

לעץ בינארי שלם יש צמתים מלאים בכל רמה, למעט הרמה האחרונה. בעצים בינריים שלמים, הצמתים מרוכזים בצד השמאלי של השורש. מבנה נפוץ נוסף הוא עץ בינארי מאוזן; במבנה זה הגבהים של תת העץ הימני והשמאלי חייבים להיות שונים לכל היותר באחד. כמו כן, נדרש כי גם תת העצים השמאלי והימני חייבים להיות מאוזנים.

חשוב לציין כי גובה העץ הבינארי המאוזן הוא O (logn), כאשר n הוא מספר הצמתים בעץ.

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

מהם עצי חיפוש בינארי?

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

המאפיין BST חייב להיות נכון עבור כל צומת אב עוקבת בעץ.

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

היתרונות של עצים בינאריים

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

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

עצים בינאריים הם מבני נתונים חשובים

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

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

TreeViz: דרך פשוטה לדמיין מבני נתונים

קרא הבא

על הסופר