דף 1 מתוך 1

עבודה 6 שאלה 2 א - פתרון

נשלח: 13:10 25/07/2009
על ידי ayeletd
בוקר טוב לכולם,

מישהו יכול להבהיר למה הכוונה בשימוש עץ AVL במקום במערך C במיון המבוסס על מיון מניה?
במיון מניה משתמשים במערך C למניית מספר המופעים של כל איבר במערך הקלט, איך הדבר בא לידי ביטוי בעץ AVL?

תודה מראש, שבת שלום

Re: עבודה 6 שאלה 2 א - פתרון

נשלח: 17:20 25/07/2009
על ידי TA_Ariel
במקום להשתמש במערך משתמשים בעץ AVL, מכניסים את כל האיברים לעץ ,
בעץ הזה יהיו רק logn מפתחות שונים לכן הגובה שלו יהיה Loglogn
לאחר מכן פשוט עוברים על העץ (inorder) ןמדפיסים את המפתחות .

Re: עבודה 6 שאלה 2 א - פתרון

נשלח: 18:33 25/07/2009
על ידי alonseg
אז למה זה מיון יציב בעצם?
מה קורה בעץ AVL כאשר מכניסים מפתח שכבר קיים?
חשבתי על לשים תור בכל קודקוד כדי לשמור על היציבות,
זה פיתרון קביל?

Re: עבודה 6 שאלה 2 א - פתרון

נשלח: 18:40 25/07/2009
על ידי TA_Ariel
כן