כיצד לקבוע אם עץ בינארי מאוזן בג'אווה
1. סקירה כללית
עצים הם אחד ממבני הנתונים החשובים ביותר במדעי המחשב. בדרך כלל אנו מעוניינים בעץ מאוזן בגלל תכונותיו החשובות. המבנה שלהם מאפשר ביצוע פעולות כמו שאילתות, הכנסות, מחיקות בזמן לוגריתמי.
במדריך זה נלמד כיצד לקבוע אם עץ בינארי מאוזן.
2. הגדרות
ראשית, בואו ונציג כמה הגדרות על מנת לוודא שאנחנו באותו עמוד:
- עץ בינארי - מעין עץ שבו לכל צומת יש אפס, ילד אחד או שניים
- גובה של עץ - מרחק מרבי משורש לעלה (זהה לעומק העלה העמוק ביותר)
- עץ מאוזן - מעין עץ שבו עבור כל עץ משנה המרחק המרבי מהשורש לכל עלה גדול לכל היותר אחד מהמרחק המינימלי מהשורש לכל עלה
אנו יכולים למצוא דוגמה לעץ בינארי מאוזן למטה. שלושה קצוות ירוקים הם הדמיה פשוטה של אופן קביעת הגובה, בעוד המספרים מציינים את הרמה.
3. אובייקטים מתחום
אז בואו נתחיל בשיעור לעץ שלנו:
Tree class {עץ ערך פרטי פרטי; עץ פרטי נותר; עץ פרטי מימין; עץ ציבורי (ערך int, עץ שמאל, עץ ימינה) {this.value = value; this.left = שמאל; this.right = ימין; }} למען הפשטות, נגיד לכל צומת יש ערך שלם. ציין זאת אם שמאל וימין עצים ריק, אז זה אומר שהצומת שלנו הוא עלה.
לפני שנציג את השיטה העיקרית שלנו נראה מה היא צריכה להחזיר:
כיתה פרטית תוצאה {בוליאני פרטי הוא מאוזן; גובה פרטי פרטי; תוצאה פרטית (בוליאנית isBalanced, int גובה) {this.isBalanced = isBalanced; this.height = גובה; }}כך עבור כל שיחה אחת, יהיה לנו מידע על גובה ושיווי משקל.
4. אלגוריתם
לאחר הגדרה של עץ מאוזן, נוכל להמציא אלגוריתם. מה שאנחנו צריכים לעשות זה לבדוק את המאפיין הרצוי לכל צומת. ניתן להשיג זאת בקלות באמצעות מעבר חוזר של רקע עומק ראשון.
כעת, השיטה הרקורסיבית שלנו תופעל עבור כל צומת. בנוסף, זה יהיה לעקוב אחר העומק הנוכחי. כל שיחה תחזיר מידע על גובה ושיווי משקל.
עכשיו, בואו נסתכל על שיטת העומק הראשונה שלנו:
תוצאה פרטית isBalancedRecursive (עץ עץ, עומק int) {אם (עץ == null) {להחזיר תוצאה חדשה (נכון, -1); } תוצאה leftSubtreeResult = isBalancedRecursive (tree.left (), עומק + 1); תוצאה rightSubtreeResult = isBalancedRecursive (tree.right (), עומק + 1); בוליאני isBalanced = Math.abs (leftSubtreeResult.height - rightSubtreeResult.height) <= 1; תת עצים בוליאנייםAreBalanced = leftSubtreeResult.isBalanced && rightSubtreeResult.isBalanced; גובה int = Math.max (leftSubtreeResult.height, rightSubtreeResult.height) + 1; להחזיר תוצאה חדשה (isBalanced && subtreesAreBalanced, גובה); }ראשית, עלינו לשקול את המקרה אם הצומת שלנו הוא ריק: נחזור נָכוֹן (כלומר העץ מאוזן) ו- -1 כגובה.
לאחר מכן, אנו מבצעים שתי שיחות רקורסיביות לעץ המשנה הימני והשמאלי, תוך שמירה על העומק מעודכן.
בשלב זה ערכנו חישובים לילדים של צומת הנוכחי. כעת, יש לנו את כל הנתונים הנדרשים לבדיקת האיזון:
- ה isBalanced משתנה בודק את הגובה לילדים, ו
- substreesAreBalanced מציין אם גם עצי המשנה מאוזנים
לבסוף, אנו יכולים להחזיר מידע על שיווי משקל וגובה. זה יכול להיות גם רעיון טוב לפשט את השיחה הרקורסיבית הראשונה בשיטת חזית:
ציבורי בוליאני isBalanced (עץ עץ) {return isBalancedRecursive (עץ, -1) .isBalanced; }5. סיכום
במאמר זה דנו כיצד לקבוע אם עץ בינארי מאוזן. הסברנו על גישת חיפוש עומק ראשונה.
כרגיל, קוד המקור עם הבדיקות זמין ב- GitHub.
