שדה SIZE בשאלה 3

מנהל: TA_Isana

שדה SIZE בשאלה 3

הודעהעל ידי eladrai » 22:23 10/06/2009

שלום,
השאלה שלי נובעת מיישום אפשרי לשאלה 3.
ישלי עץ AVL שכל איבר בו הוא למשל בעל 2 שדות, מפתח שעל פיו ממיינים ושדה SIZE שמשמעותו גודל העץ (גודל תת עץ ימני בנוסף לגודל תת עץ שמאלי ועוד 1)
מה קורה עם השדה הזה בזמן פעולת INSERT\DELETE אחרי פעולת רוטציה העץ יראה אחרת
ושדה הSIZE שלי יפגע, אני אצטרף לעבור כל הכנסה \הוצאה על אבריי העץ ולעדכן את SIZE?
נכון נשמע לא הגיוני ולא כל כך לוג של אן....
מופנה למתרגלים\שאר הסטודנטים...
בברכה ,
אחד שעייף.
eladrai
 
הודעות: 55
הצטרף: 11:51 06/12/2008

הודעהעל ידי roie » 08:17 11/06/2009

עדכון של size בעץ AVL לוקח logn , בכמט הראה את זה אתמול בשיעור.
קצת קשה להסביר פה למה אבל,תצייר לך את הרוטציות אחרי הכנסה והוצאה ותראה שצריך לעדכן את ה sizeרק במספר קטן של צמתים.
roie
 
הודעות: 32
הצטרף: 21:35 15/12/2008


חזור אל - מבני נתונים

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד

cron