שאלה לגבי תכונות אסימפטוטיות של בעצים
שלום,
אני צריך את עזרתכם בשאלה הבאה...השאלה מורכבת מכמה סעיפים. אתחיל בראשון..אני חושש שיש לי איזשהו חוסר הבנה של המושג "אסימפטוטיקה".
זו השאלה:
משפחה של עצים תיקרא "מאוזנת" אם כל עץ הוא בעל גובה (O(logn , כאשר n הוא מספר הצמתים בעץ. לכל תכונה בהמשך, קבע האם משפחה של עצים המקיימים את התכונה היא מאוזנת. אם התשובה היא "לא", תן דוגמה נגדית. אם התשובה היא "כן", הצג הוכחה (בדרך כלל ע"י אינדוקציה). זכור שהתכונה היא אסימפטוטית, ולכן הדוגמה הנגדית צריכה להכיל סדרה אינסופית של עצים במשפחה, ולא רק עץ יחיד.
המשפט האחרון לא ממש מובן לי. אציג את הסעיף הראשון (תכונה שמתקיימת במשפחת עצים. וכאמור, צריך להוכיח האם המשפחה של העצים שמקיימים את התכונה בסעיף זה, היא משפחה "מאוזנת".
א'. כל צומת בעץ הוא או עלה, או שיש לו שניי בנים.
תשובה:
משפחה של עצים בעלת התכונה שכל צומת בעץ הוא או עלה או שיש לו שניי בנים, איננה מאוזנת.
למשל אם לוקחים עץ שהוא שרוך ימני כשלכל צומת בשרוך הוספנו בן שמאלי (כלומר: שורש, בן ימני, בן ימני, בן ימני, בן ימני...כשלכל בן ימני, יש בן שמאלי).
אז מספר הרמות הוא n/2.
התשובה הזו לא ברורה לי...אם למשל אני מסתכל על העץ הבא:
שורש שאקרא לו 1. לשורש יש בן ימני שערכו 2. לקדקד עם הערך 2 יש בן שמאלי עם הערך 3, ובן ימני עם הערך 4. לקדקד עם הערך 4, יש בן שמאלי שערכו 5 ובן ימני שערכו 6. לקדקד שערכו 6, יש בן שמאלי שערכו 7 ובן ימני שערכו 8. (כמובן לא מדובר על עצי חיפוש, אלא סתם עצים בינאריים).
העץ שהצגתי כאן, הוא שרוך שלכל צומת בו יש בן שמאלי.
לפי התשובה שנתנו לשאלה (שהיא אגב נכונה...רק שאני לא מבין אותה), מספר הרמות הוא n/2. כלומר במקרה של העץ שהצגתי כאן - שמספר קדקדיו הוא n=8, מתקיים
שמספר הרמות שלו הוא 8 חלקי 2, שזה 4, ובאמת יש לו 4 רמות.
מצד שני, אם אני מנסה להראות שהוא מאוזן, אני צריך להראות שגובהו קטן שווה מ - c*logn , עבור כל n שגדול מ-no כלשהו.
גובה העץ שלי הוא 4 (יש בו 4 רמות). מספר הקדקדים בו הוא n=8.
zz 4 < clog8 = 3c ==> 4 < 3c zz קבלתי ש-4 קטן מ-3c. אם אבחר למשל c=2, מתקיים באמת ש 4<6. כמו כן, ה-n נעלם...ככה שאין כאן בכלל no שצריך לבחור.
כלמר הראיתי שגובה העץ הוא O(logn), כאשר במקרה שלי n=8.
לכן הוא מאוזן. אבל מצד שני מספר הרמות הוא n/2.
כנראה שאני לא מבין בכלל מה אני עושה.
מישהו מוכן להסביר לי איך פותרים את השאלה הזו, ומה השיגאות שלי???
תודה רבה למי שעונה!
שלום,
אני צריך את עזרתכם בשאלה הבאה...השאלה מורכבת מכמה סעיפים. אתחיל בראשון..אני חושש שיש לי איזשהו חוסר הבנה של המושג "אסימפטוטיקה".
זו השאלה:
משפחה של עצים תיקרא "מאוזנת" אם כל עץ הוא בעל גובה (O(logn , כאשר n הוא מספר הצמתים בעץ. לכל תכונה בהמשך, קבע האם משפחה של עצים המקיימים את התכונה היא מאוזנת. אם התשובה היא "לא", תן דוגמה נגדית. אם התשובה היא "כן", הצג הוכחה (בדרך כלל ע"י אינדוקציה). זכור שהתכונה היא אסימפטוטית, ולכן הדוגמה הנגדית צריכה להכיל סדרה אינסופית של עצים במשפחה, ולא רק עץ יחיד.
המשפט האחרון לא ממש מובן לי. אציג את הסעיף הראשון (תכונה שמתקיימת במשפחת עצים. וכאמור, צריך להוכיח האם המשפחה של העצים שמקיימים את התכונה בסעיף זה, היא משפחה "מאוזנת".
א'. כל צומת בעץ הוא או עלה, או שיש לו שניי בנים.
תשובה:
משפחה של עצים בעלת התכונה שכל צומת בעץ הוא או עלה או שיש לו שניי בנים, איננה מאוזנת.
למשל אם לוקחים עץ שהוא שרוך ימני כשלכל צומת בשרוך הוספנו בן שמאלי (כלומר: שורש, בן ימני, בן ימני, בן ימני, בן ימני...כשלכל בן ימני, יש בן שמאלי).
אז מספר הרמות הוא n/2.
התשובה הזו לא ברורה לי...אם למשל אני מסתכל על העץ הבא:
שורש שאקרא לו 1. לשורש יש בן ימני שערכו 2. לקדקד עם הערך 2 יש בן שמאלי עם הערך 3, ובן ימני עם הערך 4. לקדקד עם הערך 4, יש בן שמאלי שערכו 5 ובן ימני שערכו 6. לקדקד שערכו 6, יש בן שמאלי שערכו 7 ובן ימני שערכו 8. (כמובן לא מדובר על עצי חיפוש, אלא סתם עצים בינאריים).
העץ שהצגתי כאן, הוא שרוך שלכל צומת בו יש בן שמאלי.
לפי התשובה שנתנו לשאלה (שהיא אגב נכונה...רק שאני לא מבין אותה), מספר הרמות הוא n/2. כלומר במקרה של העץ שהצגתי כאן - שמספר קדקדיו הוא n=8, מתקיים
שמספר הרמות שלו הוא 8 חלקי 2, שזה 4, ובאמת יש לו 4 רמות.
מצד שני, אם אני מנסה להראות שהוא מאוזן, אני צריך להראות שגובהו קטן שווה מ - c*logn , עבור כל n שגדול מ-no כלשהו.
גובה העץ שלי הוא 4 (יש בו 4 רמות). מספר הקדקדים בו הוא n=8.
zz 4 < clog8 = 3c ==> 4 < 3c zz קבלתי ש-4 קטן מ-3c. אם אבחר למשל c=2, מתקיים באמת ש 4<6. כמו כן, ה-n נעלם...ככה שאין כאן בכלל no שצריך לבחור.
כלמר הראיתי שגובה העץ הוא O(logn), כאשר במקרה שלי n=8.
לכן הוא מאוזן. אבל מצד שני מספר הרמות הוא n/2.
כנראה שאני לא מבין בכלל מה אני עושה.
מישהו מוכן להסביר לי איך פותרים את השאלה הזו, ומה השיגאות שלי???
תודה רבה למי שעונה!