בנייה של עץ AVL

מנהל: TA_Isana

בנייה של עץ AVL

הודעהעל ידי Brk » 13:59 16/07/2010

זמן בנייה של עץ AVL ממערך בן n איברים לא ממוינים הוא nlogn נכון?
אין מצב לחסם יותר נמוך מכך?
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

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

הודעהעל ידי eliorar » 14:12 16/07/2010

אם אין לך שום הנחה על הקלט, אז זהו החסם הנמוך ביותר
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009

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

הודעהעל ידי Brk » 14:15 16/07/2010

eliorar כתב:אם אין לך שום הנחה על הקלט, אז זהו החסם הנמוך ביותר

אוקי תודה :)
וזמן בנייה סטנדרטי של skiplist זה גם כך או פחות?
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

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

הודעהעל ידי eliorar » 14:25 16/07/2010

פעולת הכנסה של skipList היא O(logn) בממוצע לכן, הכנסת n איברים לרשימת דילוגים תיקח O(nlogn) בממוצע
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009

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

הודעהעל ידי Brk » 14:32 16/07/2010

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 יפחת בעקבות השיפור במהירות בזיכרון.
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

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

הודעהעל ידי eliorar » 14:41 16/07/2010

אני חושב כמוך.. השימוש יפחת.

אגב, באותו מבחן איך הוכחת בשאלה 3 (הראשונה חח) זאת עם העץ פורש, את סעיף א'?
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009

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

הודעהעל ידי Brk » 14:55 16/07/2010

eliorar כתב:אני חושב כמוך.. השימוש יפחת.

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

בשאלה 3 ששם מציגים לך את האלגוריתם של קרוסקל למציאת MST
דילגתי על זה,לא נראה לי שנצטרך להוכיח נכונות של אלגוריתם במבחן. פעם דרשו מהם הוכחות היום זה יותר תכלס אז זה נראה לי מוזר להתעקב על זה,מה שגם לא זכור לי שהוכיחו לנו את הנכונות של האלגוריתם הזה.
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

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

הודעהעל ידי Brk » 15:13 16/07/2010

שאלה נוספת (יש הרבה היום :))
מישהוא יודע מה זמן הבנייה של עץ B-tree ?
Brk
 
הודעות: 87
הצטרף: 17:58 25/10/2009

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

הודעהעל ידי eliorar » 15:25 16/07/2010

אני מצטט מקורמן:
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%, אשמח אם מישהו מהמתרגלים יאשר את זה..
eliorar
 
הודעות: 35
הצטרף: 19:43 11/11/2009


חזור אל - מבני נתונים 2010

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ואורח אחד