שאלה במבני נתונים מה העלות של סכימה של תת עץ.

[b007]

שאלה במבני נתונים מה העלות של סכימה של תת עץ.

שאלה במבני נתונים מה העלות של סכימה של תת עץ שמאלי או ימני בעץ חיפוש מאוזן AVL? נגיד אני רוצה לעשות סכום של כל הערכים שנמצאים משמאלה לשורש. כמה זה עולה? זה גם O של LOGN ?

 

[KarNaF המקורי]

לפי דעתי לא

זה יהיה O כי: יש לך N איברים בעץ ונניח שאתה רוצה לסכום רק את האיברים שנמצאים משמאל לשורש "הקדום" ביותר בעץ אז עדיין תצטרך לבקר ב O(n/2) איברים => O.

 

[b007]

לא ניראה לי אבל.. איך בודקים?

 

[b007]

מישו?

 

[KarNaF המקורי]

...

תראה, יש לך סה"כ N איברים בכל העץ ואתה יודע שהעץ הוא מאוזן.אי לכך, בערך חצי מהאיברים יהיו מימין לשורש וחצי משמאל לשורש...

 

[b007]

אבל הסריקה של העץ ב POST ORDER

עולה גם N?

 

[b007]

אני צריך כזה דבר...

סכום מספרים שקטנים מ K ... בסיבוכיות של LOGN... באיזה מבנה נתונים להחזיק את זה? שיפעל ב LOGN?

 

[KarNaF המקורי]

רעיון לפתרון

צריך להחזיק עץ AVL ובנוסף, להוסיף בכל צומת, שדה של סכום הצמתים בתת עץ השמאלי. כמובן שהדבר ידרוש שינוי בפעולות ההכנסה ומחיקה, אבל השינוי לא יפגע בסיבוכיות שלהם והם יישארו עדיין LOG N. אחרי שהגדרת את המבנה הנתונים החדש, בהנתן מספר K, כל שתדרש זה לחפש אותו בעץ בסיבוכיות LOG N.

 

[b007]

בובה של פתרון תודה איש.