עמוד 1 מתוך 1

בנייה של עץ AVL

הודעהפורסם: 13:59 16/07/2010
על ידי Brk
זמן בנייה של עץ AVL ממערך בן n איברים לא ממוינים הוא nlogn נכון?
אין מצב לחסם יותר נמוך מכך?

Re: בנייה של עץ AVL

הודעהפורסם: 14:12 16/07/2010
על ידי eliorar
אם אין לך שום הנחה על הקלט, אז זהו החסם הנמוך ביותר

Re: בנייה של עץ AVL

הודעהפורסם: 14:15 16/07/2010
על ידי Brk
eliorar כתב:אם אין לך שום הנחה על הקלט, אז זהו החסם הנמוך ביותר

אוקי תודה :)
וזמן בנייה סטנדרטי של skiplist זה גם כך או פחות?

Re: בנייה של עץ AVL

הודעהפורסם: 14:25 16/07/2010
על ידי eliorar
פעולת הכנסה של skipList היא O(logn) בממוצע לכן, הכנסת n איברים לרשימת דילוגים תיקח O(nlogn) בממוצע

Re: בנייה של עץ AVL

הודעהפורסם: 14:32 16/07/2010
על ידי Brk
eliorar כתב:פעולת הכנסה של skipList היא O(logn) בממוצע לכן, הכנסת n איברים לרשימת דילוגים תיקח O(nlogn) בממוצע


אוקי תודה שאלה נוספת זה ממבחן 2004
שאלה 3 (25%)
שאלה זו עוסקת בעצי-B
א) (7 נק') שרטט עץ-B בו t=2 (עץ 1,2,3) אשר מכיל את המפתחות A,B,C,D,G,H,K,,M,R,W,Z
ב) (8 נק') שרטט את העץ המתקבל לאחר הוצאה של האיבר G ואחריו M מהעץ.
ג) (5 נק')מהו ערך t במערכת בה גודל מצביע שווה לגודל איבר שווה ל 2 בייט וגודל בלוק הוא 1000 בייט.
ד) (5 נק') במחשב BGU-13 שיכנס לשוק בשנת 2009, מהירות גישה לדיסק תהיה מהירה מאוד (פי 10 איטית יותר מגישה לזיכרון). כיצד תשפיע כניסה זו על שכיחות השימוש בעצי-.B

איך עונים על סעיף ד?
ממה שזכור לי עץ B-tree מקצר זמני גישה לדיסק,אז זה אומר שהשימוש בעצי B-tree יפחת בעקבות השיפור במהירות בזיכרון.

Re: בנייה של עץ AVL

הודעהפורסם: 14:41 16/07/2010
על ידי eliorar
אני חושב כמוך.. השימוש יפחת.

אגב, באותו מבחן איך הוכחת בשאלה 3 (הראשונה חח) זאת עם העץ פורש, את סעיף א'?

Re: בנייה של עץ AVL

הודעהפורסם: 14:55 16/07/2010
על ידי Brk
eliorar כתב:אני חושב כמוך.. השימוש יפחת.

אגב, באותו מבחן איך הוכחת בשאלה 3 (הראשונה חח) זאת עם העץ פורש, את סעיף א'?

בשאלה 3 ששם מציגים לך את האלגוריתם של קרוסקל למציאת MST
דילגתי על זה,לא נראה לי שנצטרך להוכיח נכונות של אלגוריתם במבחן. פעם דרשו מהם הוכחות היום זה יותר תכלס אז זה נראה לי מוזר להתעקב על זה,מה שגם לא זכור לי שהוכיחו לנו את הנכונות של האלגוריתם הזה.

Re: בנייה של עץ AVL

הודעהפורסם: 15:13 16/07/2010
על ידי Brk
שאלה נוספת (יש הרבה היום :))
מישהוא יודע מה זמן הבנייה של עץ B-tree ?

Re: בנייה של עץ AVL

הודעהפורסם: 15:25 16/07/2010
על ידי eliorar
אני מצטט מקורמן:
Inserting a key into a B-tree in a single pass down the tree:
We insert a key k into a B-tree T of height h in a single pass down the tree, requiring O(h) disk accesses.
The CPU time required is O(th) = O(t logt n). The B-TREE-INSERT procedure uses B-TREE-SPLIT-CHILD to guarantee that the recursion never descends to a full node.


כלומר עבור n איברים זמן הריצה הוא: (O(n•th) = O(n•t log(tn) - לא סגור על זה ב100%, אשמח אם מישהו מהמתרגלים יאשר את זה..