הצגת המקור של הדף "עץ WAVL"

{{מבנה נתונים
| שם = עץ WAVL
| תמונה = [[קובץ:Wavl tree.png|250px]]
| תאריך המצאה = 2009
| חיפוש ממוצע = ( O(log n
| חיפוש במקרה הגרוע = ( O(log n
| הכנסה ממוצע = ( O(1 בניתוח לשיעורין
| הכנסה במקרה הגרוע = ( O(log n
| הוצאה ממוצע = ( O(1 בניתוח לשיעורין
| הוצאה במקרה הגרוע = ( O(log n
}}
'''עץ WAVL''' (ב[[אנגלית]]: '''WAVL tree''' או '''weak AVL tree''') הוא [[מבנה נתונים]] ב[[מדעי המחשב]]. זהו [[עץ חיפוש|עץ חיפוש בינארי]] ששומר על איזון באופן דינאמי ועצמאי. הוא קרוי על שם מבנה הנתונים [[עץ AVL|AVL]] ופועל בצורה דומה למבנה זה ו[[עץ אדום שחור|לעץ אדום-שחור]]. בדומה ליתר עצי החיפוש המאוזנים, עץ WAVL תומך בפעולות [[אלגוריתם חיפוש|חיפוש]], הכנסה ומחיקה ב[[סיבוכיות זמן]] <math>O(\log n)</math>.{{הערה|שם=הערה מספר 20190119100850:0|{{צ-ספר|שם="4.4 Weak AVL Trees", Algorithm Design and Applications, Wiley, pp. 130–138.|מו"ל=Goodrich Michal T.; Tamssia, Roberto|שנת הוצאה=2015}}}}{{הערה|שם=הערה מספר 20190119100850:1|{{קישור כללי|כתובת=http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf|הכותב=Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E.|כותרת=ACM Transactions on Algorithms, 11 (4): Art. 30, 26, Ranked balanced trees,|אתר=|תאריך=}}}} עצי WAVL הוצגו על ידי חוקרי האלגוריתמים Haeupler, Sen &Tarjan בשנת 2009.{{הערה|שם=הערה מספר 20190119100850:1}}

==ביצועים==
עצי WAVL פותחו על מנת לשלב את התכונות הטובות של עצי AVL ועצים אדומים-שחורים. יתרון אחד שיש לעץ AVL על פני עצים אדומים-שחורים, הוא שעצי AVL מאוזנים יותר: הגובה שלהם חסום ע"י: <math>{\displaystyle \log _{\varphi }n\approx 1.44\log _{2}n} </math>, כאשר <math>n</math> הוא מספר האיברים ו-φ [[יחס הזהב]], בעוד עצים אדומים שחורים חסומים בגובהם על ידי <math>2\log_2 n</math>. אם עץ WAVL נוצר על ידי סדרה של הכנסות איברים בלבד וללא מחיקות אז גובהו הוא כמו זה של AVL. מצד שני, לעצים אדומים-שחורים יש יתרון במספר פעולות האיזון הנמוך שהם דרושים לבצע. לעומת עצי AVL – שמבצעים מספר [[לוגריתם|לוגריתמי]] של פעולות איזון לאחר מחיקה, עצים אדומים-שחורים הם בעלי פעולת מחיקה פשוטה יותר – שדורשת מספר קבוע של פעולות איזון. עצי WAVL הם גם בעלי תכונה זו, ואף הקבוע שמתקיים עבורם הוא קטן יותר.

==דרך פעולת העץ==
כמו עצים בינאריים כלליים, עץ WAVL שומר את איברים כאוסף צמתים משני סוגים – פנימיים וחיצוניים. לכל צומת פנימי יש מפתח, והוא מאחסן פריט מידע מסוים. בנוסף לצומת פנימי יש שלושה מצביעים לצמתים אחרים – להורה שלו, לבנו הימני ולבנו השמאלי. שורש העץ הוא יוצא דופן במקרה זה שכן אין לו הורה. לצמתים חיצוניים אין פריטי מידע, ויש להם מצביע אחד להוריהם שבעץ – הם בעצם משמשים כעלים של העץ.{{הערה|{{צ-מאמר|מחבר=(Goodrich & Tamassia (2015|שם=Chapter 3 Binary Search Trees, pp. 89–114|כתב עת=}}}} בדומה לעץ בינארי, פריטי המידע מסודרים בעץ כך שאם נסרוק אותו ב[[עץ חיפוש|סדר תוכי]] (in-order traversal) תניב רשימה ממוינת של המפתחות.{{הערה|{{צ-מאמר|מחבר=Goodrich & Tamassia (2015)|שם=Chapter 3 Binary Search Trees, pp. 89–114.|כתב עת=}}}}

מה שמייחד עצי WAVL מעץ בינארי רגיל הוא השימוש בדרגות (ranks). דרגה של צומת, היא מספר שמאחסן כל צומת, והיא נותנת אומדן למרחק בינו ובין הצאצא הכי רחוק שלו. בעץ WAVL תקין הדרגות של כל הצמתים עונות לדרישות הבאות{{הערה|שם=הערה מספר 20190119100850:1}}{{הערה|שם=הערה מספר 20190119100850:0}}:
* לכל עלה חיצוני יש דרגה 0.{{הערה|In this we follow Goodrich & Tamassia (2015). In the version described by Haeupler, Sen & Tarjan (2015), the external nodes have rank −1. This variation makes very little difference in the operations of WAVL trees, but it causes some minor changes to the formula for converting WAVL trees to red–black trees.|כיוון=שמאל}}
* לכל צומת שאינו השורש ודרגתו <math>r</math>, הדרגה של ההורה שלו היא <math>r+1</math>או <math>r+2</math>.
* לכל צומת פנימי ששני בניו הם חיצוניים יש דרגה 1 בדיוק. (ניתן לאפיין צומת זה כ"עלה פנימי").

===פעולת חיפוש===
חיפוש איבר עם מפתח k בעץ WAVL זהה כמעט לחלוטין (אולי למעט התייחסות לעלים חיצוניים) לחיפוש בעץ בינארי רגיל. הפעולה מתחילה בשורש של העץ – בצורה [[רקורסיה|רקורסיבית]] משווים בין k לבין המפתח בצומת אליו הגענו – אם הם שווים – סיימנו, אחרת, k אותו אנחנו מחפשים נמצא בתת-העץ הימני אם הוא גדול מהמפתח בצומת, או בתת-העץ השמאלי אם קטן ממנו. אם לא נמצא צומת בעל מפתח k, החיפוש מסתיים בעלה חיצוני. משמעות מקרה זה היא ש-k לא נמצא בעץ, והעלה החיצוני בו סיימנו הוא המיקום בעץ אליו k יכנס (אם תבוצע פעולת הכנסה כזו).{{הערה|Goodrich & Tamassia (2015), Section 3.1.2 Searching in a Binary Search Tree, pp. 95–96.|כיוון=שמאל}}

===פעולת הכנסה===
הכנסת המפתח k לעץ WAVL מבוצעת באופן הבא:
* על ידי חיפוש המיקום בו k צריך להיכנס – חיפוש זה יחזיר עלה חיצוני.
* החלפת איבר זה בצומת פנימי עם מפתח k, ששני בניו הם עלים חיצוניים.
* איזון (rebalancing) העץ.

איזון העץ לאחר ההכנסה יכול להתבצע מלמעלה למטה (up-down rebalancing) או מלמטה למעלה (down-up rebalancing). השיטה השנייה דומה יותר לאיזון עצי AVL.{{הערה|שם=הערה מספר 20190119100850:0}}{{הערה|שם=הערה מספר 20190119100850:1}} הפעולה הראשונה באיזון העץ לאחר ההכנסה, היא השמת דרגת הצומת החדש, שנכנס כ"עלה פנימי", כ-1, ולאחר מכן עלייה לאורך הדרך בין כל צומת לאביו, ובמקרה הצורך – אם לצומת ולאביו אותה דרגה – הגדלת הדרגה של האב ב-1 (קידום), עד שנגיע לאחד מתנאי העצירה הבאים:
* אם הגענו לשורש – פעולת האיזון הסתיימה.
* אם הגענו לצומת שהפרש הדרגות מאביו הוא 2 (כלומר הפרש דרגות 1 אחרי קידום הבן) – פעולת האיזון הסתיימה.
* אם האלגוריתם מקדם את הצומת <math>x
</math>, כך שדרגתו תהיה שווה לזו של אביו <math>y</math>, אך לבן השני של <math>y</math> יש דרגה שקטנה ב-2 מזו של <math>y</math>, ולכן לא ניתן לקדם את <math>y</math>, ונאלץ לעצור את פעולת האיזון. במקרה זה ביצוע שני גלגולים לכל היותר יאפשר ארגון של צמתי העץ שליד <math>x</math> ו-<math>y</math>, כך שדרגות הצמתים יקיימו את האילוצים על הפרשי הדרגות בעץ WAVL, וללא שינוי הדרגה של שורש תת-העץ בו בוצעו הגלגולים (גם אם השורש עצמו השתנה, הדרגה נשארה זהה) ולכן העץ תקין.

לכן בסה"כ, פעולת ההכנסה מורכבת מחיפוש, יצירת צומת חדש, מספר לוגריתמי של שינויי דרגות, ומספר קבוע של גלגולים.{{הערה|שם=הערה מספר 20190119100850:0}}{{הערה|שם=הערה מספר 20190119100850:1}}

===פעולת מחיקה===
כמו בעצים בינאריים אחרים, פעולות מחיקה על צומת <math>x</math> שבן אחד או שניים שלו הם עלים חיצוניים יכולות להתבצע ישירות על ידי הסרת <math>x</math> מהעץ, וחיבור מחדש בנו (אם קיים כזה) להורה של <math>x</math>. אם שני הבנים של <math>x</math>הם צמתים פנימיים, נשים במקום <math>x</math> את העוקב שלו בעץ (האיבר בעל המפתח העוקב – successor), ונמחק את העוקב. פעולה זו תצליח כיוון שבנו השמאלי של העוקב <math>y</math> הוא עלה חיצוני (אם היה לו בן שמאלי פנימי אז הבן היה העוקב).{{הערה|Goodrich & Tamassia (2015), Section 3.1.4 Deletion in a Binary Search Tree, pp. 98–99.|כיוון=שמאל}}

לאחר כל אחד משני המקרים שלעיל, מכיוון ששינינו את מבנהו של העץ, יש לבצע איזון מחדש שלו. כמו במקרה של הכנסה, ניתן לבצע זאת על ידי עלייה לאורך העץ והורדה ב-1 של הדרגות לאורך הדרך, עד שמגיעים לאחד משלושת המצבים האפשריים הבאים:
* מגיעים לשורש ולכן העץ מאוזן.
* מגיעים לצומת שהפרש הדרגות מהבן שלו תקינה ולכן שוב העץ מאוזן.
* מגיעים לצומת שלא ניתן לשנות את דרגתו – כיוון שזה יפר את תנאי הפרש הדרגות עם הבן האחר שלו. במקרה זה מספר קבוע של גלגולים משלים את שלב האיזון.{{הערה|שם=הערה מספר 20190119100850:0}}{{הערה|שם=הערה מספר 20190119100850:1}}

כלומר בסה"כ, בצורה דומה להכנסה, פעולת המחיקה מהעץ מורכבת מחיפוש (ואולי המשך של חיפוש העוקב), הסרה של הצומת מהעץ, מספר לוגריתמי של שינויי דרגות, ומספר קבוע של גלגולים. באופן שונה מעץ AVL, פעולות איזון בצורת גלגול הן סופיות, ולכן עבור שני עצים זהים, אחד מהם AVL והשני WAVL, השני עשוי לאזן את עצמו הרבה יותר מהר.{{הערה|שם=הערה מספר 20190119100850:0}}{{הערה|שם=הערה מספר 20190119100850:1}}
===ניתוח סיבוכיות===
כל פעולת חיפוש, הכנסה או מחיקה בעץ WAVL, מכילה מעבר לגובהו של העץ, וביצוע מספר קבוע של פעולות בכל צומת בדרך. בעץ WAVL עם <math>n</math> איברים בעל פעולות הכנסה בלבד, הגובה המקסימלי הוא <math>\log_{\varphi} n\approx 1.44\log_2 n</math>. עבור עץ שמאפשר גם מחיקות וגם הכנסות, הגובה המקסימלי הוא <math>2\log_2 n</math>. לכן בשני המקרים, הסיבוכיות במקרה הגרוע (worst-case) עבור חיפוש, הכנסה או מחיקה היא <math>O(\log n)</math>. יתר על כן, היתרון הגדול של עץ WAVL על מספר עצים בינאריים אחרים, הוא שהסיבוכיות של פעולות האיזון ב[[ניתוח לשיעורין]] הוא <math>O(1)</math>, כלומר עבור סדרת פעולות, במקרה הגרוע הסיבוכיות ממוצעת לפעולה תהיה קבועה. יתר על כן, בהינתן מצביע לצומת אותו רוצים להכניס או למחוק, כלומר במקרה בו לא צריך לבצע חיפוש, גם פעולות ההכנסה והמחיקה תהיינה בסיבוכיות זו.{{הערה|שם=הערה מספר 20190119100850:1}}
===מבני נתונים קרובים===
עצי WAVL הם בעלי קרבה הדוקה לעצי AVL ולעץ אדום-שחור. כל עץ AVL ניתן להפוך לעץ WAVL ללא שינויי דרגות הצמתים, כלומר הדרישות על הפרשי הדרגות בעץ AVL מחמירות יותר, וכל עץ AVL עונה על הדרישות של עץ WAVL. ההפך לא נכון, כיוון שלא ניתן להפוך עץ שמכיל הפרשי קשתות 2-2 לעץ AVL. באופן דומה, ניתן לצבוע את צמתיו של כל עץ WAVL, ולשנות את דרגותיו, כך שיתקבל עץ אדום-שחור תקין. הכיוון השני אינו נכון, כלומר לא כל עץ אדום-שחור ניתן להפוך לעץ WAVL.
====עץ AVL====
עץ AVL הוא עץ חיפוש בינארי מאוזן, בו גובהם של שני ילדיו של כל צומת פנימי, נבדלים לכל היותר ב-1.{{הערה|Goodrich & Tamassia (2015), Section 4.2 AVL Trees, pp. 120–125.|כיוון=שמאל}} הגובה של צומת חיצוני הוא אפס, וגובהו של כל צומת פנימי הוא אחד ועוד המקסימום של גבהי ילדיו. לכן, [[פונקציה|פונקציית]] הגובה של עץ AVL עומדת בדרישות של עץ WAVL, וכך ניתן להפוך כל עץ AVL לעץ WAVL על ידי שימוש בגובהו של כל צומת כדרגה שלו בצורת WAVL.{{הערה|שם=הערה מספר 20190119100850:0}}{{הערה|שם=הערה מספר 20190119100850:1}} ההבדל המשמעותי בין עץ WAVL לעץ AVL מגיע כאשר לצומת מסוים יש שני בנים בעלי אותו גובה/דרגה. בעץ AVL אם לשני הבנים יש אותו גובה <math>h</math>, אז גובהו של הצומת עצמו הוא בדיוק <math>h+1</math>. לעומת זאת, בעץ WAVL אם לצומת <math>x</math>, יש שני בנים בעלי דרגה זהה <math>r</math>, אז דרגתו של <math>x</math> יכולה להיות <math>r+1</math> או <math>r+2</math>. הגמישות הגדולה הזו בדרגות מובילה לצורות גמישות יותר של העץ, ולכן בעצי WAVL מסוימים לא ניתן להמיר את הדרגות בגבהים כך שיתקבל עץ AVL תקין – כי הפרש הגבהים בין שני בנים של אותו צומת עלול להיות גדול מ-1.{{הערה|שם=הערה מספר 20190119100850:1}}

אם עץ AVL נוצר על ידי פעולות הכנסה בלבד, אז מבנהו יהיה זהה לזה של עץ AVL שנוצר על ידי אותן הפעולות, ודרגותיו יהיו זהות לגבהי ה-AVL. ההבדל נוצר בפעולות המחיקה. בפרט, משמעות הדבר שאם עץ WAVL נוצר על ידי פעולות הכנסה בלבד, אז גובהו הוא לכל היותר <math> {\displaystyle \log _{\varphi }n\approx 1.44\log _{2}n}</math> (זהו גובהו המקסימלי של עץ AVL).{{הערה|שם=הערה מספר 20190119100850:1}}

====עץ אדום-שחור====
עץ אדום-שחור הוא עץ בינארי מאוזן בו לכל צומת יש צבע (אדום או שחור), שעונה על התנאים:
* צמתים חיצוניים צבועים בשחור.
* אם צומת פנימי הוא אדום, אז שני ילדיו שחורים.
* כל הדרכים מהשורש עד לצומת חיצוני בעץ הן בעלי מספר זהה של צמתים שחורים.

ניתן להגדיר עצים אדומים-שחורים בצורה שקולה במונחי דרגות של הצמתים, כך שהדרגות יענו על הדרישות הבאות:
* הדרגה של צומת חיצוני היא תמיד 0, והדרגה של אביו היא תמיד 1.
* הדרגה של כל צומת שאינו שורש שווה לדרגה של אביו, או לדרגה של אביו פחות 1.
* אין שתי קשתות רצופות בדרך בין השורש לעלה עם הפרש דרגות 0.

ניתן לראות את השקילות בין הגדרת הצבעים להגדרת הדרגות על ידי צביעת כל צומת בשחור אם דרגתו קטנה מזו של אביו, ובאדום אחרת. בכיוון השני, ניתן להמיר צבעים בדרגות על ידי הגדרת הדרגה של צומת שחור כמספר הצמתים השחורים בדרך לצומת חיצוני, והדרגה של צמתים אדומים כדרגה של הוריהם.{{הערה|Goodrich & Tamassia (2015), Section 4.3 Red–black Trees, pp. 126–129.|כיוון=שמאל}}

ניתן להמיר דרגות צמתי WAVL כך שיתאימו לדרישות עץ אדום-שחור, על ידי חלוקת כל דרגה ב-2 ועיגול כלפי מעלה.{{הערה|In Haeupler, Sen & Tarjan (2015) the conversion is done by rounding down, because the ranks of external nodes are −1 rather than 0. Goodrich & Tamassia (2015) give a formula that also rounds down, but because they use rank 0 for external nodes their formula incorrectly assigns red–black rank 0 to internal nodes with WAVL rank 1.}} לכן, עבור כל עץ WAVL קיים עץ אדום-שחור תקין בעל אותו מבנה. מכיוון שגובהם המקסימלי של עצים אדומים-שחורים הוא <math> {\displaystyle 2\log _{2}n}</math>, עובדה זו נכונה גם לגבי עצי WAVL. עם זאת, קיימים עצים אדומים-שחורים שאת דרגתם לא ניתן להמיר לדרגות WAVL.

למרות העובדה שעצי WAVL הם מקרה פרטי של עצים אדומים-שחורים, פעולות האיזון של הם שונות. גלגולי העץ שמבוצעים באיזון עצי WAVL עשויים לגרור שינויים שיפרו את איזונו של עץ אדום-שחור, כיוון שהם יגרמו למעשה לשינוי הצבעים בתת-עץ גדול של העץ במקום על מסלול יחיד. עובדה זו מאפשרת לעצי WAVL לבצע פחות פעולות איזון במקרה הגרוע מאשר עץ אדום-שחור.{{הערה|שם=הערה מספר 20190119100850:0}}{{הערה|שם=הערה מספר 20190119100850:1}}

==ראו גם==
* [[רשימה מקושרת]]
* [[עץ B+]]
* [[ערימה]]

==לקריאה נוספת==
* [http://www.cs.tau.ac.il/~zwick/Data-Structures-2018/WAVL.pptx עצי AVL ו-WAVL], אונ' תל אביב

==קישורים חיצוניים==
<div class="mw-content-ltr">
* [http://sidsen.azurewebsites.net/papers/rb-trees-talg.pdf "Ranked balanced trees"] (PDF), Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2015)/ [https://dl.acm.org/citation.cfm?doid=2756876.2689412 10.1145/2689412]
<div class="mw-content-rtl">

==הערות שוליים==
{{הערות שוליים|יישור=שמאל}}

{{מבני נתונים}}

[[קטגוריה:עצי חיפוש]]