עץ WAVL

ביצועים

עצי WAVL פותחו על מנת לשלב את התכונות הטובות של עצי AVL ועצים אדומים-שחורים. יתרון אחד שיש לעץ AVL על פני עצים אדומים-שחורים, הוא שעצי AVL מאוזנים יותר: הגובה שלהם חסום ע"י: , כאשר הוא מספר האיברים ו-φ יחס הזהב, בעוד עצים אדומים שחורים חסומים בגובהם על ידי . אם עץ WAVL נוצר על ידי סדרה של הכנסות איברים בלבד וללא מחיקות אז גובהו הוא כמו זה של AVL. מצד שני, לעצים אדומים-שחורים יש יתרון במספר פעולות האיזון הנמוך שהם דרושים לבצע. לעומת עצי AVL - שמבצעים מספר לוגריתמי של פעולות איזון לאחר מחיקה, עצים אדומים שחורים הם בעלי פעולת מחיקה פשוטה יותר - שדורשת מספר קבוע של פעולות איזון. עצי WAVL הם גם בעלי תכונה זו, ואף הקבוע שמתקיים עבורם הוא קטן יותר.

פעולת חיפוש

חיפוש איבר עם מפתח k בעץ WAVL זהה כמעט לחלוטין (אולי למעט התייחסות לעלים חיצוניים) לחיפוש בעץ בינארי רגיל. הפעולה מתחילה בשורש של העץ - בצורה רקורסיבית משווים בין k לבין המפתח בצומת אליו הגענו - אם הם שווים - סיימנו, אחרת, k אותו אנחנו מחפשים נמצא בתת-העץ הימני אם הוא גדול מהמפתח בצומת, או בתת-העץ השמאלי אם קטן ממנו. אם לא נמצא צומת בעל מפתח k, החיפוש מסתיים בעלה חיצוני. משמעות מקרה זה היא ש-k לא נמצא בעץ, והעלה החיצוני בו סיימנו הוא המיקום בעץ אליו k יכנס (אם תבוצע פעולת הכנסה כזו).

ניתוח סיבוכיות

כל פעולת חיפוש, הכנסה או מחיקה בעץ WAVL, מכילה מעבר לגובהו של העץ, וביצוע מספר קבוע של פעולות בכל צומת בדרך. בעץ WAVL עם איברים בעל פעולות הכנסה בלבד, הגובה המקסימלי הוא . עבור עץ שמאפשר גם מחיקות וגם הכנסות, הגובה המקסימלי הוא . לכן בשני המקרים, הסיבוכיות במקרה הגרוע (worst-case) עבור חיפוש, הכנסה או מחיקה היא . יתר על כן, היתרון הגדול של עץ WAVL על מספר עצים בינארים אחרים, הוא שהסיבוכיות של פעולות האיזון בניתוח לשיעורין הוא , כלומר עבור סדרת פעולות, במקרה הגרוע הסיבוכיות ממוצעת לפעולה תהיה קבועה. יתר על כן, בהינתן מצביע לצומת אותו רוצים להכניס או למחוק, כלומר במקרה בו לא צריך לבצע חיפוש, גם פעולות ההכנסה והמחיקה תהיינה בסיבוכיות זו.

מבני נתונים קרובים

עצי WAVL הם בעלי קרבה הדוקה לעצי AVL ולעץ אדום-שחור. כל עץ AVL ניתן להפוך לעץ WAVL ללא שינויי דרגות הצמתים, כלומר הדרישות על הפרשי הדרגות בעץ AVL מחמירות יותר, וכל עץ AVL עונה על הדרישות של עץ WAVL. ההפך לא נכון, כיוון שלא ניתן להפוך עץ שמכיל הפרשי קשתות 2-2 לעץ AVL. באופן דומה, ניתן לצבוע את צמתיו של כל עץ WAVL, ולשנות את דרגותיו, כך שיתקבל עץ אדום שחור תקין. הכיוון השני אינו נכון, כלומר לא כל עץ אדום שחור ניתן להפוך לעץ WAVL.

עץ AVL

עץ AVL הוא עץ חיוש בינארי מאוזן, בו גובהם של שני ילדיו של כל צומת פנימי, נבדלים לכל היותר ב-1. הגובה של צומת חיצוני הוא אפס, וגובהו של כל צומת פנימי הוא אחד ועוד המקסימום של גבהי ילדיו. לכן, פונקציית הגובה של עץ AVL עומדת בדרישות של עץ WAVL, וכך ניתן להפוך כל עץ AVL לעץ WAVL על ידי שימוש בגובהו של כל צומת כדרגה שלו בצורת WAVL. ההבדל המשמעותי בין עץ WAVL לעץ AVL מגיע כאשר לצומת מסוים יש שני בנים בעלי אותו גובה/דרגה. בעץ AVL אם לשני הבנים יש אותו גובה , אז גובהו של הצומת עצמו הוא בדיוק . לעומת זאת, בעץ WAVL אם לצומת , יש שני בנים בעלי דרגה זהה , אז דרגתו של יכול להיות או . הגמישות הגדולה הזו בדרגות מובילה לצורות גמישות יותר של העץ, ולכן בעצי WAVL מסוימים לא ניתן להמיר את הדרגות בגבהים כך שיתקבל עץ AVL תקין - כי הפרש הגבהים בין שני בנים של אותו צומת עלול להיות גדול מ-1.
אם עץ AVL נוצר על ידי פעולות הכנסה בלבד, אז מבנהו יהיה זהה לזה של עץ AVL שנוצר על ידי אותן הפעולות, ודרגותיו יהיו זהות לגבהי ה-AVL. ההבדל נוצר בפעולות המחיקה. בפרט, משמעות הדבר שאם עץ WAVL נוצר על ידי פעולות הכנסה בלבד, אז גובהו הוא לכל היותר (זהו גובהו המקסימלי של עץ AVL).