עבור לתוכן

מחפש אלגוריתם לאיזון עץ בינארי

Featured Replies

פורסם

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

1) האלגוריתם צריך לסדר את העץ רק פעם אחת ולא לשמור עליו מסודר.

2) האיזון לא חייב להיות מושלם.

3) האלגוריתם צריך להיות פשוט ככל הניתן.

פורסם

סרוק את העץ למערך.

יש לך ערימה חוקית מבחינת מבנה אבל לא מבחינת יחסי אב-בן, וזה עץ מאוזן

פורסם
  • מחבר

הלוואי וזה היה כל כך פשוט, שכחתי לציין שאסור להשתמש במערך שכן מדובר במבנה נתונים עם זכרון רציף. ושימוש ברשימות במיוחד לכך נראה מטופש.

פורסם

למרות שלא נראה לי שאני אמצא את האלגוריתם

אתה יכול להסביר מזתמרת איזון? ומזתמרת לסדר רק פעם אחת ולא לשמור עליו מסודר?

סתם מתעניין ...

פורסם
  • מחבר

הכוונה בעץ מאוזן היא כמובן שגובה העץ הוא לכל היותר o(logn), כלומר אין מסלול מסויים מראש העץ לתחתיתו שארוף ביותר מ 1 ממסלול אחר.

הכוונה בלסדר פעם אחת היא שלאחר הסידור אני "לא אהרוס אותו" על ידי הכנסה או הוצאה של איברים.

אגב לבינתיים מצאתי פתרון לא רע בצורת אלגוריתם Tree To Vine balancing.

פורסם

השינויים חייבים להיות בעץ הנתון או שאתה יכול לעשות עותק חדש שלו ובו לעשות את השינויים?

יש דרישות סוביוכיות?

יש לי אלגוריתם ממש פשוט אם מותר לך לעשות עותק ואין לך ממש דרישות סיבוכיות.

פורסם

זה רק רעיון

הוא ברקורסיה

כל שלב ברקורסיה אומר לך - תמצא את האיבר האמצעי(מספר האיברים בעץ חלקי 2), ותסובב את העץ עד שתגיע אליו.

תעשה אותו דבר לתת עץ שמאלי ולתת עץ ימיני

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים