שדה SIZE בשאלה 3

מנהל: TA_Isana

שלח תגובה
eladrai
הודעות: 55
הצטרף: 11:51 06/12/2008

שדה SIZE בשאלה 3

שליחה על ידי eladrai » 23:23 10/06/2009

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

roie
הודעות: 32
הצטרף: 21:35 15/12/2008

שליחה על ידי roie » 09:17 11/06/2009

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

שלח תגובה

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