עץ WAVL

עץ WAVL
	wavl tree
יצירה
הומצא ב:	2009
סיבוכיות מקום וזמן
ממוצע	במקרה הגרוע
( O(log n	( O(log n
( O(1 בניתוח לשיעורין	( O(log n
( O(1 בניתוח לשיעורין	( O(log n

עץ WAVL (אנגלית - WAVL tree או weak AVL tree) הוא מבנה הנתונים במדעי המחשב. זהו עץ חיפוש בינארי ששומר על איזון באופן דינאמי ועצמאי. הוא קרוי על שם מבנה הנתונים AVL ופועל בצורה דומה למבנה זה ולעץ אדום-שחור. בדומה ליתר עצי החיפוש המאוזנים, עץ WAVL תומך בפעולות חיפוש, הכנסה ומחיקה בסיבוכיות זמן $O(\log n)$ .^[1]^[2] עצי WAVL הוצגו על ידי חוקרי האלגוריתמים Haeupler, Sen &Tarjan בשנת 2009.^[2]

ביצועים

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

דרך פעולת העץ

כמו עצים בינארים כלליים, עץ WAVL שומר את איברים כאוסף צמתים משני סוגים - פנימיים וחיצוניים. לכל צומת פנימי יש מפתח, והוא מאחסן פריט מידע מסוים. בנוסף לצומת פנימי יש שלושה מצביעים לצמתים אחרים - להורה שלו, לבנו הימני ולבנו השמאלי. שורש העץ הוא יוצא דופן במקרה זה שכן אין לו הורה. לצמתים חיצוניים אין פריטי מידע, ויש להם מצביע אחד להוריהם שבעץ - הם בעצם משמשים כעלים של העץ.^[3] בדומה לעץ בינארי, פריטי המידע מסודרים בעץ כך שאם נסרוק אותו בסדר תוכי (in-order traversal) תניב רשימה ממוינת של המפתחות.^[4]

מה שמייחד עצי WAVL מעץ בינארי רגיל הוא השימוש בדרגות (ranks). דרגה של צומת, היא מספר שמאחסן כל צומת, והיא נותנת אומדן למרחק בינו ובין הצאצא הכי רחוק שלו. בעץ WAVL תקין הדרגות של כל הצמתים עונות לדרישות הבאות^[2]^[1]:

לכל עלה חיצוני יש דרגה 0^[5]
לכל צומת שאינו השורש ודרגתו $r$ , הדרגה של ההורה שלו היא $r+1$ או $r+2$ .
לכל צומת פנימי ששני בניו הם חיצוניים יש דרגה 1 בדיוק. (ניתן לאפיין צומת זה כ"עלה פנימי").

פעולת חיפוש

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

פעולת הכנסה

הכנסת המפתח k לעץ WAVL מבוצעת באופן הבא:

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

איזון העץ לאחר ההכנסה יכול להתבצע מלמעלה למטה (up-down rebalancing) או מלמטה למעלה (down-up rebalancing). השיטה השנייה דומה יותר לאיזון עצי AVL.^[2]^[1] הפעולה הראשונה באיזון העץ לאחר ההכנסה, היא השמת דרגת הצומת החדש, שנכנס כ"עלה פנימ", כ-1, ולאחר מכן עלייה לאורך הדרך בין כל צומת לאביו, ובמקרה הצורך - אם לצומת ולאביו אותה דרגה - הגדלת הדרגה של האב ב-1 (קידום), עד שנגיע לאחד מתנאי העצירה הבאים:

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

לכן בסה"כ, פעולת ההכנסה מורכבת מחיפוש, יצירת צומת חדש, מספר לוגריתמי של שינויי דרגות, ומספר קבוע של גלגולים.^[2]^[1]

פעולת מחיקה

כמו בעצים בינארים אחרים, פעולות מחיקה על צומת $x$ שבן אחד או שניים שלו הם עלים חיצוניים יכולות להתבצע ישירות על ידי הסרת $x$ מהעץ, וחיבור מחדש בנו (אם קיים כזה) להורה של $x$ . אם שני הבנים של $x$ הם צמתים פנימיים, נשים במקום $x$ את העוקב שלו בעץ (האיבר בעל המפתח העוקב - successor), ונמחק את העוקב. פעולה זו תצליח כיוון שבנו השמאלי של העוקב $y$ הוא עלה חיצוני (אם היה לו בן שמאלי פנימי אז הבן היה העוקב).^[7]

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

מגיעים לשורש ולכן העץ מאוזן.
מגיעים לצומת שהפרש הדרגות מהבן שלו תקינה ולכן שוב העץ מאוזן.
מגיעים לצומת שלא ניתן לשנות את דרגתו - כיוון שזה יפר את תנאי הפרש הדרגות עם הבן האחר שלו. במקרה זה מספר קבוע של גלגלולים משלים את שלב האיזון.^[2]^[1]

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

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

כל פעולת חיפוש, הכנסה או מחיקה בעץ WAVL, מכילה מעבר לגובהו של העץ, וביצוע מספר קבוע של פעולות בכל צומת בדרך. בעץ WAVL עם $n$ איברים בעל פעולות הכנסה בלבד, הגובה המקסימלי הוא $\log _{\varphi }n\approx 1.44\log _{2}n$ . עבור עץ שמאפשר גם מחיקות וגם הכנסות, הגובה המקסימלי הוא $2\log _{2}n$ . לכן בשני המקרים, הסיבוכויות במקרה הגרוע (worst-case) עבור חיפוש, הכנסה או מחיקה היא $O(\log n)$ . יתר על כן, היתרון הגדול של עץ WAVL על מספר עצים בינארים אחרים, הוא שהסיבוכיות של פעולות האיזון בניתוח לשיעורין הוא $O(1)$ , כלומר עבור סדרת פעולות, במקרה הגרוע הסיבוכיות ממוצעת לפעולה תהיה קבועה. יתר על כן, בהינתן מצביע לצומת אותו רוצים להכניס או למחוק, כלומר במקרה בו לא צריך לבצע חיפוש, גם פעולות ההכנסה והמחיקה תהיינה בסיבוכיות זו.^[2]

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

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

עץ AVL

עץ AVL הוא עץ חיוש בינארי מאוזן, בו גובהם של שני ילדיו של כל צומת פנימי, נבדלים לכל היותר ב-1.^[8] הגובה של צומת חיצוני הוא אפס, וגובהו של כל צומת פנימי הוא אחד ועוד המקסימום של גבהי ילדיו. לכן, פונקציית הגובה של עץ AVL עומדת בדרישות של עץ WAVL, וכך ניתן להפוך כל עץ AVL לעץ WAVL על ידי שימוש בגובהו של כל צומת כדרגה שלו בצורת WAVL.^[2]^[1] ההבדל המשמעותי בין עץ WAVL לעץ AVL מגיע כאשר לצומת מסוים יש שני בנים בעלי אותו גובה/דרגה. בעץ AVL אם לשני הבנים יש אותו גובה $h$ , אז גובהו של הצומת עצמו הוא בדיוק $h+1$ . לעומת זאת, בעץ WAVL אם לצומת $x$ , יש שני בנים בעלי דרגה זהה $r$ , אז דרגתו של $x$ יכול להיות $r+1$ או $r+2$ . הגמישות הגדולה הזו בדרגות מובילה לצורות גמישות יותר של העץ, ולכן בעצי WAVL מסוימים לא ניתן להמיר את הדרגות בגבהים כך שיתקבל עץ AVL תקין - כי הפרש הגבהים בין שני בנים של אותו צומת עלול להיות גדול מ-1.^[2]

אם עץ AVL נוצר על ידי פעולות הכנסה בלבד, אז מבנהו יהיה זהה לזה של עץ AVL שנוצר על ידי אותן הפעולות, ודרגותיו יהיו זהות לגבהי ה-AVL. ההבדל נוצר בפעולות המחיקה. בפרט, משמעות הדבר שאם עץ WAVL נוצר על ידי פעולות הכנסה בלבד, אז גובהו הוא לכל היותר ${\displaystyle \log _{\varphi }n\approx 1.44\log _{2}n}$ (זהו גובהו המקסימלי של עץ AVL).^[2]

עץ אדום שחור

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

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

ניתן להגדיר עצים אדומים שחורים בצורה שקולה במונחי דרגות של הצמתים, כך שהדרגות יענו על הדרישות הבאות:

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

ניתן לראות את השקילות בין הגדרת הצבעים להגדרת הדרגות על ידי צביעת כל צומת בשחור אם דרגתו קטנה מזו של אביו, ובאדום אחרת. בכיוון השני, ניתן להמיר צבעים בדרגות על ידי הגדרת הדרגה של צומת שחור כמספר הצמתים השחורים בדרך לצומת חיצוני, והדרגה של צמתים אדומים כדרגה של הוריהם.^[9]

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

${\displaystyle 2\log _{2}n}$ , עובדה זו נכונה גם לגבי עצי WAVL. עם זאת, קיימים עצים אדומים שחורים שאת דרגתם לא ניתן להמיר לדרגות WAVL.

למרות העובדה שעצי WAVL הם מקרה פרטי של עצים אדומים שחורים, פעולות האיזון של הם שונות. גלגולי העץ שמבוצעים באיזון עצי WAVL עשויים לגרור שינויים שיפרו את איזונו של עץ אדום שחור, כיוון שהם יגרמו למעשה לשינוי הצבעים בתת-עץ גדול של העץ במקום על מסלול יחיד. עובדה זו מאפשרת לעצי WAVL לבצע פחות פעולות איזון במקרה הגרוע מאשר עץ אדום שחור.^[2]^[1]

ראו גם

לקריאה נוספת

עצי AVL ו-WAVL, אונ' תל אביב
עצי WAVL ב-ויקיויזואלי

קישורים חיצוניים

"Ranked balanced trees" (PDF), Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (2015)/ 10.1145/2689412

הערות שוליים

^ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 "4.4 Weak AVL Trees", Algorithm Design and Applications, Wiley, pp. 130–138., Goodrich Michal T.; Tamssia, Roberto, 2015
^ ^2.00 ^2.01 ^2.02 ^2.03 ^2.04 ^2.05 ^2.06 ^2.07 ^2.08 ^2.09 ^2.10 ^2.11 Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E., ACM Transactions on Algorithms, 11 (4): Art. 30, 26, Ranked balanced trees,
^ (Goodrich & Tamassia (2015, Chapter 3 Binary Search Trees, pp. 89–114
^ Goodrich & Tamassia (2015), Chapter 3 Binary Search Trees, pp. 89–114.
^ 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.
^ Goodrich & Tamassia (2015), Section 3.1.2 Searching in a Binary Search Tree, pp. 95–96.
^ Goodrich & Tamassia (2015), Section 3.1.4 Deletion in a Binary Search Tree, pp. 98–99.
^ Goodrich & Tamassia (2015), Section 4.2 AVL Trees, pp. 120–125.
^ Goodrich & Tamassia (2015), Section 4.3 Red–black Trees, pp. 126–129.
^ 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.

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

24999294עץ WAVL

[הערה_מספר_20190119100850:0-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 ^1.7 "4.4 Weak AVL Trees", Algorithm Design and Applications, Wiley, pp. 130–138., Goodrich Michal T.; Tamssia, Roberto, 2015

[הערה_מספר_20190119100850:1-2] 2.00 ^2.01 ^2.02 ^2.03 ^2.04 ^2.05 ^2.06 ^2.07 ^2.08 ^2.09 ^2.10 ^2.11 Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E., ACM Transactions on Algorithms, 11 (4): Art. 30, 26, Ranked balanced trees,

[3] (Goodrich & Tamassia (2015, Chapter 3 Binary Search Trees, pp. 89–114

[4] Goodrich & Tamassia (2015), Chapter 3 Binary Search Trees, pp. 89–114.

[5] 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.

[6] Goodrich & Tamassia (2015), Section 3.1.2 Searching in a Binary Search Tree, pp. 95–96.

[7] Goodrich & Tamassia (2015), Section 3.1.4 Deletion in a Binary Search Tree, pp. 98–99.

[8] Goodrich & Tamassia (2015), Section 4.2 AVL Trees, pp. 120–125.

[9] Goodrich & Tamassia (2015), Section 4.3 Red–black Trees, pp. 126–129.

[10] 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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]