2 שאלות במבנה נתונים:
שאלה 1: It is possible to convert any binary search tree with n nodes to any other BST with n nodes using rotations. The number of rotations required for this in the worst case is i. 0(log n) ii. 0
iii. 0(n log n) אני יודע בוודאות שחסם מלמטה הוא חסם לינארי השאלה היא אם הוא גם החסם העליון. הסיבה שאני חושב שזה nlogn היא משום שכל כל איבר בעץ אפשר לבצע logn רוטציות מקסימום (להעלות אותו מלמטה למעלה או להוריד אותו מהשורש למטה ומכיוון שיש לנו n איברים זה נראה כמו nlogn אולי אני טועה ודברים מתקזזים. הערה: השאלה שואלת מהו החסם ההדוק על מספר הרוטציות ולא עלות הרוטציות (שהיא גם ככה קבועה). שאלה 2: (a) (10 pt) Describe a data structure that supports the following operations, with the above running time constraints: insert(key) O(log) delete(key) O(log) getMax(), getMin() O(1) extractMax(), extractMin() O(log) Build(ArrayA) O אוקי פה אני תקוע כי רציתי להשתמש בתור קדימיות שהוא סוג של היפ אבל הבעיה היא שבהיפ אי אפשר לאתר איבר בזמן של logn למען הסר ספק המתודות extractMax(), extractMin() פשוט מוציאות את האיבר המקסימלי/מינימלי לעומת האלה שמעליהן שרק מחזירות את הערך המסימלי.מינימלי המתודה Build(ArrayA) מקבלת מערך של איברים ובונה ממנו את טיפוס הנתונים. תודה לכל העונים...
שאלה 1: It is possible to convert any binary search tree with n nodes to any other BST with n nodes using rotations. The number of rotations required for this in the worst case is i. 0(log n) ii. 0
iii. 0(n log n) אני יודע בוודאות שחסם מלמטה הוא חסם לינארי השאלה היא אם הוא גם החסם העליון. הסיבה שאני חושב שזה nlogn היא משום שכל כל איבר בעץ אפשר לבצע logn רוטציות מקסימום (להעלות אותו מלמטה למעלה או להוריד אותו מהשורש למטה ומכיוון שיש לנו n איברים זה נראה כמו nlogn אולי אני טועה ודברים מתקזזים. הערה: השאלה שואלת מהו החסם ההדוק על מספר הרוטציות ולא עלות הרוטציות (שהיא גם ככה קבועה). שאלה 2: (a) (10 pt) Describe a data structure that supports the following operations, with the above running time constraints: insert(key) O(log) delete(key) O(log) getMax(), getMin() O(1) extractMax(), extractMin() O(log) Build(ArrayA) O אוקי פה אני תקוע כי רציתי להשתמש בתור קדימיות שהוא סוג של היפ אבל הבעיה היא שבהיפ אי אפשר לאתר איבר בזמן של logn למען הסר ספק המתודות extractMax(), extractMin() פשוט מוציאות את האיבר המקסימלי/מינימלי לעומת האלה שמעליהן שרק מחזירות את הערך המסימלי.מינימלי המתודה Build(ArrayA) מקבלת מערך של איברים ובונה ממנו את טיפוס הנתונים. תודה לכל העונים...