רוטר - תרגיל במבנה נתונים שאלה קטנה

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"תרגיל במבנה נתונים שאלה קטנה"

גירסת הדפסה

קבוצות דיון לימודים, מדע ותרבות נושא #21080	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 21080

Crazy Lion

חבר מתאריך 1.7.02
19328 הודעות, 9 פידבק

12:04 04.01.15

תרגיל במבנה נתונים שאלה קטנה

פרופסור וולדמורט חושב שהוא מצא מאפיין מאד מעניין של עצי חיפוש בינאריים. נניח כי חיפוש אחר מפתח k מהשורש למטה מסתיים בעלה עם הערך k. כעת נגדיר שלוש קבוצות: A המפתחות שמשמאלו של מסלול החיפוש, B המפתחות במסלול החיפוש עצמו, C המפתחות שמימין למסלול החיפוש. פרופסור וולדמורט טוען שעבור כל a∈A,b∈B,c∈C חייב להתקיים a≤b≤c. הוכח את טענת הפרופסור או הפרך באמצעות דוגמה.
אני מוצא רק שזה נכון .. השאלה אם אני צודק או יש דוגמא נגדית שמפריכה?
אני חושב שמעצם חוקי עץ חיפוש בינארי זה תמיד יהיה נכון כי משמאל למסלול החיפוש תמיד יהיה ערכים יותר קטנים ומימין למסלול זה תמיד יהיה גדול

מה דעתכם?
תודה מראש

מילוי סקרים בתשלום למי שמעונין ,
משלם בזמן וקל להגיע ליעד :
https://goo.gl/EJh6V2

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
נראה לי מצאתי פתרון שזה סתירה:	Crazy Lion	04.01.15 12:13	1
מעתיקן חח	ShocKi	04.01.15 12:15	3
הפרכה באמצעות העץ של ויקיפדיה	ShocKi	04.01.15 12:15	2
זה לא נכון:	ohadeytan	04.01.15 12:25	4
הקדימו אותי :(	ohadeytan	04.01.15 12:26	5
אלופים... חחח תודה רבה.. חיפשתי דוגמאות לבד לא מצאתי אז נאלצתי להעתיק חחח	Crazy Lion	04.01.15 12:31	6
זה עוד בסדר, תשאל על שאלות 5 ו-6 :)	jon snow	08.01.15 13:14	7

Crazy Lion

חבר מתאריך 1.7.02
19328 הודעות, 9 פידבק

12:13 04.01.15

1. נראה לי מצאתי פתרון שזה סתירה:
בתגובה להודעה מספר 0

http://rotter.name/User_files/nor/54a9124432f59cef.jpg
FIND 7 ואז יש סתירה יש איבר ב A 4 שגדול מאיבר ב B

מילוי סקרים בתשלום למי שמעונין ,
משלם בזמן וקל להגיע ליעד :
https://goo.gl/EJh6V2

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ShocKi

חבר מתאריך 19.3.02
20171 הודעות, 10 פידבק

12:15 04.01.15

3. מעתיקן חח
בתגובה להודעה מספר 1

קאש-באק ישראלי: https://www.cashback.co.il/?uref=33330
קאשבק לAsos ואמזון דרך Ebates: https://goo.gl/MX87Y7 - מקבלים 10$ לאחר שימוש ראשון.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ShocKi

חבר מתאריך 19.3.02
20171 הודעות, 10 פידבק

12:15 04.01.15

2. הפרכה באמצעות העץ של ויקיפדיה
בתגובה להודעה מספר 0

http://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/250px-Binary_search_tree.svg.png
K=7
לכן:
A=1,4
B=8,3,6,7
C=10,14,13
נסתכל על:

a∈A,b∈B,c∈C הבאים: a=4, b=3,c=10
לא מתקיים a≤b≤c

קאש-באק ישראלי: https://www.cashback.co.il/?uref=33330
קאשבק לAsos ואמזון דרך Ebates: https://goo.gl/MX87Y7 - מקבלים 10$ לאחר שימוש ראשון.

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ohadeytan

חבר מתאריך 7.8.06
617 הודעות, 3 פידבק

12:25 04.01.15

4. זה לא נכון:
בתגובה להודעה מספר 0

נניח בעץ החיפוש הזה אתה מחפש את 49:
http://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/pix/insertEx.bmp
אז 17 שייך ל A ואילו 11 שייך ל B אבל 11 קטן מ-17

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

ohadeytan

חבר מתאריך 7.8.06
617 הודעות, 3 פידבק

12:26 04.01.15

5. הקדימו אותי :(
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Crazy Lion

חבר מתאריך 1.7.02
19328 הודעות, 9 פידבק

12:31 04.01.15

6. אלופים... חחח תודה רבה.. חיפשתי דוגמאות לבד לא מצאתי אז נאלצתי להעתיק חחח
בתגובה להודעה מספר 0

נשתמש בדוגמא של עודד
באמת תודה רבה על העזרה המהירה.

מילוי סקרים בתשלום למי שמעונין ,
משלם בזמן וקל להגיע ליעד :
https://goo.gl/EJh6V2

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

jon snow

חבר מתאריך 18.7.13
655 הודעות, 1 פידבק

13:14 08.01.15

7. זה עוד בסדר, תשאל על שאלות 5 ו-6 :)
בתגובה להודעה מספר 6

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד