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

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

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

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

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

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

1. הצומת השמאלי קטן מההורה שלו.
2. הצומת הימני גדול מההורה שלו.
3. תת-העץ השמאלי והימני חייבים להיות עצי חיפוש בינאריים.

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

קָשׁוּר: ספריות מדעי נתונים עבור Python שכל מדען נתונים צריך להשתמש

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

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

1. פעולת חיפוש

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

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

2. פעולת הכנס

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

• מקרה 1: כאשר לא קיים צומת. הצומת שיוכנס יהפוך לצומת השורש.

• מקרה 2: אין ילדים. במקרה זה, הצומת יושווה לצומת השורש. אם הוא גדול יותר, הוא יהפוך לילד הנכון; אחרת, הוא יהפוך לילד השמאלי.

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

3. מחק את הפעולה

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

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

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

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

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

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

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

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

• מעבר בהזמנה מראש: בשיטה זו מבקרים תחילה בצומת השורש, ואחריו תת העץ השמאלי ותת העץ הימני.

• מעבר לאחר הזמנה: מעבר זה כרוך בביקור אחרון בצומת השורש. נתחיל מתת-העץ השמאלי, לאחר מכן תת-העץ הימני, ולאחר מכן צומת השורש.

אפליקציות בעולם האמיתי

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

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

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

עצי חיפוש בינאריים: נקודת ההתחלה המושלמת

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

15 שיטות מערך JavaScript שכדאי לשלוט בהן היום

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

קרא הבא

על הסופר