ABA
יומן פעילות לוח שנה מבזקי חדשות תקנון RSS כותרות כותרות לפי תגובה ניקוי קוקיז IP להורדת אפליקציה
eBay AliExpress GearBest Amazon Booking Kiwi SkyScanner Trip Advisor


"שאלה קטנה בקשר לעצי AVL(קשור לקורס מבני נתונים).."
גירסת הדפסה        
קבוצות דיון לימודים, מדע ותרבות נושא #15537 מנהל    סגן המנהל    מפקח   Winner    צל"ש   מומחה  
אשכול מספר 15537
VeNom  לחץ כאן להצגת דירוג המשתמש
חבר מתאריך 7.6.02
7922 הודעות, 1 פידבק		   19:15   16.09.09   
אל הפורום  
  שאלה קטנה בקשר לעצי AVL(קשור לקורס מבני נתונים)..  
 
   ערכתי לאחרונה בתאריך 16.09.09 בשעה 19:22 בברכה, VeNom
 
האם יש דרך לבנות עץ AVL מתוך מערך ממויין!! של n או 2n איברים בזמן של טטה של n?

כי מצד אחד הגובה של עץ AVL הוא טטה של log n...והכנסת 2n איברים תהיה


O( nlogn ).

מצד שני החסם התחתון כאן הוא

omega (n)

כי כדי להכניס
2n איברים
חייבים לעבור על כולם..

יש סימולציה של הכנסה מיוחדת שעושה את זה בטטה של n?


                                שתף        
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

  האשכול     מחבר     תאריך כתיבה     מספר  
  כן. Deuce  16.09.09 19:58 1
     רעיון טוב.. VeNom  16.09.09 20:33 2
         כן, זה בסדר הרעיו ןשלי. Deuce  16.09.09 23:16 3
             אוקיי תודה רבה.. VeNom  16.09.09 23:22 4

       
Deuce 
חבר מתאריך 1.9.08
6225 הודעות		   19:58   16.09.09   
אל הפורום  
  1. כן.  
בתגובה להודעה מספר 0
 
אני יכול לתת לך רעיון אפשרי ...
פשוט תעשה עץ ממש מלא (או כמעט מלא).
כל פעם קח את החציון ומצד שמאל שים חציון של תת מערך שמאלי ומצד ימין חציון של תת מערך ימיני ותמשיך כך רקורסיבית.






                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
VeNom  לחץ כאן להצגת דירוג המשתמש
חבר מתאריך 7.6.02
7922 הודעות, 1 פידבק		   20:33   16.09.09   
אל הפורום  
  2. רעיון טוב..  
בתגובה להודעה מספר 1
 
   הקטע הוא שאני לא משתמש ב insert המקורי שיש לעץ avl נכון?
כי אחרת יש השוואות->חסם תחתון של מודל ההשוואות הוא nlogn..
אני בעקרון קובע middle ומכניס אותו לעץ..ואז מארגן אינדקסים ובעצם מחלק את המערך ל 2 תתי מערכים ממוייונים..ושולח כל תת מערך כזה רקורסיבית-ואז הוא שולח את ה Middle של כל אחד מהם לעץ?
זאת הכוונה שלך? כי הרעיון של לשלוח חציון כל פעם נראה נכון..


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
Deuce 
חבר מתאריך 1.9.08
6225 הודעות		   23:16   16.09.09   
אל הפורום  
  3. כן, זה בסדר הרעיו ןשלי.  
בתגובה להודעה מספר 2
 
ערכתי לאחרונה בתאריך 16.09.09 בשעה 23:21 בברכה, Deuce
 
ברגע שאתה קובע חציון אז אתה מחלק את זה כך שבצד שמאל יהיו בידיוק חצי מהאיברים וכנ"ל בצד שמאל (עד כדי +- 1), אתה צריך קצת לפקח על זה ולדאוג שכל פעם יהיה איזון של +-1.
לגבי מודל ההשוואות - ההוכחה לא נכונה כי ברגע שהמערך ממויין יש פרמוטציה אחת אז אין צורך להשוות כלום, צריך רק להכניס בצורה חכמה. אין לי מושג האמת מה יקרה אם פשוט תעשה Insert לכל איבר לפי הסדר לתוך ה-AVL (לא זוכר בע"פ את המקרים). עבור עץ אדום שחור אני חושב שזה היה לוקח nlog n.

בכל אופן, הבנת את הבנייה






                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד
VeNom  לחץ כאן להצגת דירוג המשתמש
חבר מתאריך 7.6.02
7922 הודעות, 1 פידבק		   23:22   16.09.09   
אל הפורום  
  4. אוקיי תודה רבה..  
בתגובה להודעה מספר 3
 
  


                                                         (ניהול: מחק תגובה)
מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

תגובה מהירה  למכתב מספר: 
 
___________________________________________________________________

___________________________________________________________________
למנהלים:  נעל | תייק בארכיון | מחק | העבר לפורום אחר | מחק תגובות | עגן אשכול
       



© כל הזכויות שמורות ל-רוטר.נט בע"מ rotter.net