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

[The Grey Matter]

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

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

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

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

[kikkler]

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

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

[The Grey Matter]

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

[Spirit Crusher]

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

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

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

[The Grey Matter]

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

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

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

[Holy]

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

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

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

[Ghosthunter]

זה רק רעיון

הוא ברקורסיה

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

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