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

מהו עץ בינארי?

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

העץ הבינארי יכול להיות מיוצג כך:

באיור לעיל, אנו יכולים לראות שכל צומת מכיל 2 ילדים לכל היותר. אם צומת כלשהו אינו מכיל ילד שמאלי או ימני אז הערך של המצביע ביחס לאותו ילד יהיה NULL.

מינוחים בסיסיים המשמשים בעץ בינארי הם:

צומת שורש:צומת השורש הוא הצומת הראשון או העליון בעץ בינארי.צומת אב:כאשר צומת מחובר לצומת אחר דרך קצוות, אז הצומת הזה ידוע כצומת אב. בעץ בינארי, לצומת אב יכולים להיות לכל היותר 2 ילדים.צומת ילד:אם לצומת יש את קודמו, אז הצומת הזה ידוע בתור a צומת ילד .צומת עלה:הצומת שאינו מכיל כל ילד המכונה a צומת עלה .צומת פנימי:הצומת שיש לו לפחות 2 ילדים המכונה an צומת פנימי .עומק של צומת:המרחק מצומת השורש לצומת הנתון ידוע בתור a עומק של צומת . אנו מספקים תוויות לכל הצמתים כמו שצומת שורש מסומן ב-0 מכיוון שאין לו עומק, ילדים של צמתים שורש מסומנים ב-1, ילדים של צאצא שורש מסומנים ב-2.גוֹבַה:המרחק הארוך ביותר מצומת השורש לצומת העלה הוא גובה הצומת .

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

n = 2^m+1-1

כאשר n הוא מספר הצמתים, m הוא עומק הצומת.

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

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

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

באיור לעיל, אנו יכולים לראות שהערך של צומת השורש הוא 15, שהוא גדול מהערך של כל הצמתים בתת-העץ השמאלי. הערך של צומת שורש קטן מהערכים של כל הצמתים בתת-עץ ימני. כעת, אנו עוברים לילד השמאלי של צומת השורש. 10 גדול מ-8 וקטן מ-12; הוא גם מספק את המאפיין של עץ החיפוש הבינארי. כעת, אנו עוברים לילד הימני של צומת השורש; הערך 20 גדול מ-17 וקטן מ-25; זה גם עונה על המאפיין של עץ החיפוש הבינארי. לכן, אנו יכולים לומר שהעץ המוצג לעיל הוא עץ החיפוש הבינארי.

כעת, אם נשנה את הערך של 12 ל-16 בעץ הבינארי לעיל, עלינו למצוא אם הוא עדיין עץ חיפוש בינארי או לא.

הערך של צומת השורש הוא 15 שהוא גדול מ-10 אך קטן מ-16, כך שהוא אינו עונה על המאפיין של עץ החיפוש הבינארי. לכן, זה לא עץ חיפוש בינארי.

פעולות על עץ חיפוש בינארי

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

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

ראשית, נחשב את האלמנט האמצעי ונשווה את האלמנט האמצעי לאלמנט שאותו יש לחפש. האלמנט האמצעי מחושב באמצעות n/2. הערך של n הוא 7; לכן, האלמנט האמצעי הוא 15. האלמנט האמצעי אינו שווה לאלמנט המחפש, כלומר 10.

הערה: אם האלמנט שמחפשים הוא קטן מהאלמנט האמצעי, החיפוש יתבצע בחצי השמאלי; אחרת, החיפוש יתבצע בחצי הימני. במקרה של שוויון נמצא היסוד.

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

האלמנט האמצעי במערך השמאלי הוא 10, השווה לאלמנט המחפש.

מורכבות הזמן

בחיפוש בינארי, ישנם n אלמנטים. אם האלמנט האמצעי אינו שווה לאלמנט המחפש, אז מרחב החיפוש מצטמצם ל-n/2, ונמשיך להקטין את מרחב החיפוש ב-n/2 עד שנמצא את האלמנט. בכל ההפחתה, אם נעבור מ-n ל-n/2 ל-n/4 וכן הלאה, אז זה ייקח לוג₂n צעדים.

הבדלים בין עץ בינארי לעץ חיפוש בינארי