הבדל מפתח – עץ בינארי לעומת עץ חיפוש בינארי
מבנה נתונים הוא דרך שיטתית לארגן נתונים כדי להשתמש בהם ביעילות. סידור הנתונים באמצעות מבנה הנתונים אמור להפחית את זמן הריצה או את זמן הביצוע. כמו כן, מבנה הנתונים צריך לדרוש כמות מינימלית של זיכרון. לפעמים ניתן לסדר את הנתונים במבנה עץ. עץ מייצג צומת המחובר בקצוות. הצומת העליון הוא השורש. לכל צומת יכולים להיות לכל היותר שני צמתים. הם ידועים בתור צמתים ילדים. הצומת משמאל לצומת האב הוא הצומת הצאצא השמאלי ואילו הצומת מימין לצומת האב הוא הצומת הימני.העץ הבינארי ועץ החיפוש הבינארי הם שני מבני נתוני עצים. עץ בינארי הוא סוג של מבנה נתונים שבו לכל צומת אב יכולים להיות לכל היותר שני צמתים צאצאים. עץ החיפוש הבינארי הוא עץ בינארי שבו הילד השמאלי מכיל רק צמתים עם ערכים שווים או נמוכים לצומת האב, וכאשר הילד הימני מכיל רק צמתים בעלי ערכים גדולים יותר מאשר לצומת האב. זה ההבדל העיקרי. בניגוד למבני נתונים כגון מערכים, לעץ הבינארי ולעץ החיפוש הבינארי אין גבול עליון לאחסון נתונים.
מהו עץ בינארי?
כאשר מסדרים את הנתונים במבנה עץ, הצומת בראש העץ ידוע כצומת השורש. יכול להיות רק שורש אחד לכל העץ. לכל צומת מלבד צומת השורש יש קצה אחד כלפי מעלה לצומת. זה נקרא צומת האב. הצומת מתחת לקוד האב נקרא צומת הילד שלו. לכל צומת אב יכולים להיות לכל היותר שני צמתים צאצאים. הם מכונים כצומת ילד שמאלי וצומת ילד ימני.צומת ללא שום צומת צאצא נקרא צומת עלה. אין דרך ספציפית לסדר נתונים בעץ הבינארי. יש נתיב מצומת שורש לכל צומת.
איור 01: דוגמה לעץ בינארי
למעלה היא דוגמה לעץ בינארי. האלמנט 2, בראש העץ, הוא השורש. לכל צומת יש שני צמתים לכל היותר. אם עץ מכיל לולאות כלשהן או אם צומת אחד מכיל יותר משני צמתים, לא ניתן לסווג אותו כעץ בינארי. כדי לעבור מצומת אחד לשני, תמיד יש נתיב אחד. הצמתים הצאצאים של צומת שורש 2 הם 7 ו-5.ייתכן גם שלצומת אין צמתים. אבל כל צומת לא יכול לכלול יותר משני צמתים. האלמנט הימני של השורש הוא 5. אלמנט 5 זה הוא צומת האב עבור צומת צאצא 9. לצומת 4 ו-11 אין אלמנטים צאצאים. לכן, הם צמתים עלים.
העץ הבינארי משמש לאחסון נתונים בסדר היררכי. זה דומה למבנה הקבצים של המחשב. מבנה הנתונים כמו מערך יכול לאחסן כמות מסוימת של נתונים. אבל בעץ בינארי, אין גבול עליון למספר הצמתים.
מהו עץ חיפוש בינארי?
עץ חיפוש בינארי הוא מבנה נתוני עץ בינארי. בדומה לעץ בינארי, גם לעץ החיפוש הבינארי יכולים להיות שני צמתים. לכל צומת מלבד צומת השורש יש קצה אחד כלפי מעלה לצומת. זה נקרא צומת האב. הצומת מתחת לנתון המחובר בקצה שלו כלפי מטה נקרא צומת הילד שלו. צומת ללא שום צומת צאצא נקרא צומת עלה. לכל צומת אב יכולים להיות שני צמתים לכל היותר.ישנם צמתים צאצאים המפנים לצומת צאצא שמאלי ולצומת צאצא ימני. האלמנט העליון נקרא צומת השורש. הצאצא השמאלי מכיל רק צמתים עם ערכים הנמוכים או שווים לצומת האב. הצאצא הימני מכיל רק צמתים עם ערכים גדולים או שווים לצומת האב.
איור 02: דוגמה לעץ חיפוש בינארי
האלמנט 8 הוא האלמנט העליון ביותר. לכן, זהו צומת השורש. אם 3 הוא צומת אב, אז 1 ו-6 הם צומת צאצא. ה-1 הוא צומת הילד השמאלי בעוד 6 הוא צומת הילד הימני.הילד השמאלי מכיל ערכים הנמוכים או שווים לצומת האב. כאשר 3 הוא צומת האב, בצד שמאל צריך להיות אלמנט הקטן או שווה ל-3. בדוגמה זו, הוא 1. הילד הימני מכיל רק צמתים עם ערכים גדולים מהצומת האב. כאשר 3 הוא צומת האב, הצומת הצאצא הימני צריך להיות בעל ערך גבוה מ-3. בדוגמה זו הוא 6. כמו כן, יש סדר מסוים כדי לסדר כל רכיב נתונים בעץ חיפוש בינארי. זהו מבנה נתונים המספק דרך יעילה לבצע מיון, אחזור וחיפוש נתונים.
מהם הדמיון בין עץ בינארי לעץ חיפוש בינארי?
- שני העץ הבינארי וגם עץ החיפוש הבינארי הם מבני נתונים היררכיים.
- גם לעץ הבינארי וגם לעץ החיפוש הבינארי יש שורש.
- גם לעץ הבינארי וגם לעץ החיפוש הבינארי יכולים להיות לכל היותר שני צמתים צאצאים.
מה ההבדל בין עץ בינארי לעץ חיפוש בינארי?
עץ בינארי לעומת עץ חיפוש בינארי |
|
| עץ בינארי הוא סוג של מבנה נתונים שבו לכל צומת אב יכולים להיות לכל היותר שני צמתים צאצאים. | עץ החיפוש הבינארי הוא עץ בינארי שבו הילד השמאלי מכיל רק צמתים עם ערכים שווים או נמוכים לצומת האב, והילד הימני מכיל רק צמתים עם ערכים גדולים יותר מהצומת האב. |
| סדר סידור נתונים | |
| לעץ בינארי אין סדר ספציפי לסידור רכיבי הנתונים. | לעץ חיפוש בינארי יש סדר ספציפי לסידור רכיבי הנתונים. |
| שימוש | |
| עץ בינארי משמש כחיפוש יעיל של נתונים ומידע במבנה עץ. | עץ חיפוש בינארי משמש להוספה, מחיקה וחיפוש של הנתונים. |
סיכום – עץ בינארי לעומת עץ חיפוש בינארי
מבנה נתונים הוא דרך לארגן נתונים. לפעמים ניתן לסדר את הנתונים במבנה עץ. שניים מהם הם עץ בינארי ועץ החיפוש הבינארי. מאמר זה דן בהבדל בין עץ בינארי לעץ החיפוש הבינארי. עץ בינארי הוא סוג של מבנה נתונים שבו לכל צומת אב יכולים להיות לכל היותר שני צמתים צאצאים. עץ החיפוש הבינארי הוא עץ בינארי שבו הילד השמאלי מכיל רק צמתים עם ערכים שווים או נמוכים לצומת האב, וכאשר הילד הימני מכיל רק צמתים עם ערכים גדולים יותר מהצומת האב.
הורד את ה-PDF של Binary Tree vs Binary Search Tree
ניתן להוריד את גרסת ה-PDF של מאמר זה ולהשתמש בה למטרות לא מקוונות לפי הערת ציטוט. אנא הורד את גרסת ה-PDF כאן: ההבדל בין עץ בינארי לעץ חיפוש בינארי
