שאלה טכנית על עצים
אז ככה.
נתון לי עץ מסוג zz BB[a] zz, ורוצים להכניס לו איבר. (בתוך הקודקודים רשומים המפתחות ומעל הקודקודים רשום את הגודל של תת העץ המושרש).
ההכנסה גורמת לחוסר איזון, ולכן לאחריה יש לאזן את העץ.
הבעיה היא שלא בדיוק ברור לי איך מאזנים עץ מסוג זה. לפי מה שהבנתי, האלגוריתם אומר שמחפשים את הצומת הגבוה ביותר שעשינו במסלול החיפוש (מסלול החיפוש היה בשביל להכניס את המספר 3, כמו בעץ חיפוש בינארי רגיל) שאינו a מאוזן. במקרה הזה מדובר בצומת עם המספר 8.
לאחר שמצאנו אותו, נהפוך את תת העץ המושרש בו לעץ מאוזן על אותם קודקודים- ואת זה לא בדיוק הבנתי איך מבצעים.
אני חושב שהמטרה כאן היא ליצור עץ שהוא כמה שיותר קרוב לעץ מושלם, אבל לא ברור לי מה הדרך המדויקת לכך.
איך ניתן לבצע זאת?
אז ככה.
נתון לי עץ מסוג zz BB[a] zz, ורוצים להכניס לו איבר. (בתוך הקודקודים רשומים המפתחות ומעל הקודקודים רשום את הגודל של תת העץ המושרש).
ההכנסה גורמת לחוסר איזון, ולכן לאחריה יש לאזן את העץ.
הבעיה היא שלא בדיוק ברור לי איך מאזנים עץ מסוג זה. לפי מה שהבנתי, האלגוריתם אומר שמחפשים את הצומת הגבוה ביותר שעשינו במסלול החיפוש (מסלול החיפוש היה בשביל להכניס את המספר 3, כמו בעץ חיפוש בינארי רגיל) שאינו a מאוזן. במקרה הזה מדובר בצומת עם המספר 8.
לאחר שמצאנו אותו, נהפוך את תת העץ המושרש בו לעץ מאוזן על אותם קודקודים- ואת זה לא בדיוק הבנתי איך מבצעים.
אני חושב שהמטרה כאן היא ליצור עץ שהוא כמה שיותר קרוב לעץ מושלם, אבל לא ברור לי מה הדרך המדויקת לכך.
איך ניתן לבצע זאת?