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

[ayeletd]

בוקר טוב לכולם,

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

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

[TA_Ariel]

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

[alonseg]

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

[TA_Ariel]

כן