עץ חיפוש

[מספר6]

עץ חיפוש

נתונים n איברים שצריך לסדר בעץ חיפוש בינארי. ידוע לנו מראש באיזו שכיחות ניגשים לכל איבר. יש לבנות עץ שנותן זמן גישה מינימלי בתוחלת. מצאו אלגוריתם יעיל עד כמה שאפשר.

 

[עריסטו]

../images/Emo58.gif

huffman

 

[מספר6]

זה פותר רק חצי מהבעיה

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

 

[עריסטו]

אז תוסיף לכל איבר עוד שדה ../images/Emo3.gif

 

[מספר6]

כלומר?

שהעץ יהיה עץ חיפוש ביחס לשדה הנוסף? אבל אני רוצה לחפש לפי הערך המקורי של האיבר. וחוץ מזה, עץ הופמן לא נותן זמן גישה אופטימלי, בגלל שהוא מחייב לשים את כל האיברים בעלים. לדוגמה, נניח שיש שני איברים A ו-B, ונניח ש-50% מהשאילתות הן על A ו-50% על B. אם נסדר אותם בעץ הופמן (ראה ציור), אז אורך המסלול לכל איבר יהיה 1. לעומת זאת, אם נשים את A בשורש ואת B בבן הימני, אורך המסלול הממוצע יהיה 1/2.