עצי חיפוש בינרים

[n0b0dy]

עצי חיפוש בינרים

נדרשתי להביא דוגמא נגדית לטענה הבאה : נניח שחיפוש מפתח K בעץ חיפוש בינרי מסתיים בעלה. נתבונן ב- 3 קבוצות : A - המפתחות משמאל למסלול החיפוש ; B - המפתחות במסלול החיפוש ; C - המפתחות מימין למסלול החיפש; נטען כי כל 3 מפתחות a , b, c ששייכות בהתאמה לקבוצות שתיארתי למעלה, מקיימות בהכרח : a <= b <= c אני צריך להביא דוגמא נגדית לטענה של עץ חיפוש בינרי הקטן ביותר האפשרי. תודה לעוזרים!

 

[vinney]

תגדיר עץ חיפוש בינארי

שהבנים הגדולים בו הם השמאליים ולא הימניים, והרי לך דוגמא נגדית.

 

[mEaS]

דוגמא נגדית:

תבחר עץ כך שהערך של השורש שלו הוא, למשל, 12. לשורש יש בן שמאלי עם ערך 10 ואין בן ימני. לבן השמאלי יש בן שמאלי עם ערך 9 וימני עם הערך 11. זהו עץ עם 4 צמתים. אי אפשר למצוא דוגמא נגדית עם עץ בעל 3 צמתים או פחות (תחשוב איך נראה עץ כזה).