איך מיישמים עץ חיפוש בינארי ב-Java?

2024 מְחַבֵּר: Lynn Donovan | [email protected]. שונה לאחרונה: 2023-12-15 23:47

הטמעת עץ חיפוש בינארי (BST) ב-Java

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

כמו כן, השאלה היא כיצד מיושם חיפוש בינארי בג'אווה?

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

1. class BinarySearchExample1{
2. public static int binarySearch(int arr, int first, int last, int key){
3. if (אחרון>=ראשון){
4. int mid = first + (אחרון - ראשון)/2;
5. if (arr[mid] == key){
6. לחזור באמצע;
7. }

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

רק כך, איך נוצרים עצים בינאריים?

יצירת עץ בינארי באמצעות רקורסיה

1. קרא נתונים ב-x.
2. הקצה זיכרון לצומת חדש ואחסן את הכתובת במצביע p.
3. אחסן את הנתונים x בצומת p.
4. צור באופן רקורסיבי את תת-העץ השמאלי של p והפוך אותו לילד השמאלי של p.
5. צור באופן רקורסיבי את תת-העץ הנכון של p והפוך אותו לילד הנכון של p.

מהי המורכבות של חיפוש בינארי?

חיפוש בינארי פועל בזמן הלוגריתמי הגרוע ביותר, עושה השוואות O(log n), כאשר n הוא מספר האלמנטים במערך, ה-O הוא סימון Big O, ו-log הוא הלוגריתם. חיפוש בינארי לוקח מרחב קבוע (O(1)), כלומר הרווח שלוקח האלגוריתם זהה עבור כל מספר של אלמנטים במערך.