משתמש:Cbelle1234/עץ WAVL
במדעי המחשב, עץ WAVL או עץ AVL חלש הוא עץ חיפוש בינארי המאזן את עצמו. עצי WAVL נקראים על שם עצי AVL - סוג נוסף של עץ המאזן עצמו. שניהם קשורים לעצי AVL נוספים ולעצים אדומים–שחורים, אשר שייכים לקטגוריה עצים מאוזני דרגה. כמו עצי חיפוש בינארי מאוזנים אחרים, עצי WAVL יכולים להתמודד עם פעולות הוספה, מחיקה, וחיפושבזמן (O(log n לכל פעולה. [1][2]
עצי WAVL נועדו לשלב בין המאפיינים הטובים ביותר של שני עצי החיפוש AVL ואדום–שחור. יתרון אחד של עצי AVL על פני עצים אדומים–שחורים הוא שהם מאוזנים יותר - גובהם המירבי נמוך מגובהם המירבי של עצים אדומים–שחורים. אם עץ WAVL נוצר באמצעות הוספות בלבד ובלי מחיקות, אז יש לו את אותה מגבלת גובה כמו עץ AVL. מצד שני, לעצים אדומים–שחורים ישנו יתרוןעל פני עצי AVL בכך שהם מבצעים פחות שינויים בעצים קיימים. בעצי AVL, כל מחיקה עשויה להיות כרוכה במספר לוגריתמי של פעולות סיבוב עץ, בעוד לעצי אדום–שחור יש פעולות מחיקה פשוטות יותר שלרוב דורשות רק מספר קבוע של שינויים בעץ. עצי WAVL, כמו עצי אדום–שחור, נדרשים רק למספר קבוע של שינויים בעץ, והקבוע אף קטן יותר מאשר בעצי אדום–שחור.[1][2]
עצי WAVL הוצגו על ידי הופלר, סן וטריאן ב-2015. אותם המחברים סיפקו הצגה כללית של עצי WAVL, עצי AVL ועצים אדומים–שחורים, כמו גם הצגתם כעצים מאוזני דרגה.