TechCodeview

לפני שמבינים את עץ אדום-שחור ועץ AVL הבדלים, עלינו לדעת על העץ האדום-שחור ועץ ה-AVL בנפרד.

מהו עץ אדום-שחור?

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

נכסים

להלן המאפיינים המשויכים לעץ אדום-שחור:

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

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

בואו נבין את הנכס הזה באמצעות דוגמה.

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

xd xd משמעות

אם העץ אינו מציית לאף אחד משלושת המאפיינים הנ'ל, אז זה לא עץ אדום-שחור.

גובה של עץ אדום-שחור

ראה h כגובה העץ בעל n צמתים. מה יהיה הערך הקטן ביותר של n?. הערך של n הוא הקטן ביותר כאשר כל הצמתים שחורים. אם העץ מכיל את כל הצמתים השחורים, אז העץ יהיה עץ בינארי שלם. אם הגובה של עץ בינארי שלם הוא h, אז מספר הצמתים בעץ הוא:

n = 2h -1

hashtable לעומת hashmap

מה יהיה הערך הגדול ביותר של n?

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

n = 2*2h-1

מהו עץ AVL?

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

בעץ לעיל, מורכבות הזמן הגרועה ביותר לחיפוש אלמנט היא O(h), כלומר, גובה העץ. במקרה שלעיל, מספר ההשוואות שבוצעו לחיפוש אלמנט 17 הוא 4, וגם גובה העץ הוא 4.

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

בעץ המעוות הימני למעלה, מספר ההשוואות לחיפוש אלמנט 17 הוא 5, ומספר האלמנטים הקיימים בעץ הוא גם 5. לכן, אנו יכולים לומר שאם העץ הוא עץ בינארי מוטה אזי מורכבות הזמן יהיה O(n).

כעת, עלינו לאזן את העצים המעוותים הללו כך שתהיה להם מורכבות הזמן O(h). יש מונח המכונה א גורם איזון , המשמש לאיזון עצמי של עץ החיפוש הבינארי. ניתן לחשב את גורם האיזון כך:

הערך של גורם האיזון יכול להיות 1, 0 או -1. אם לכל צומת בעץ הבינארי יש ערך של 1, 0 או -1, אזי העץ הזה הוא מאוזן עץ בינארי או עץ AVL.

מה זה f5 במקלדת

העץ ידוע כעץ מאוזן לחלוטין אם גורם האיזון של כל צומת הוא 0. עץ AVL הוא עץ כמעט מאוזן מכיוון שלכל צומת בעץ יש את הערך של גורם איזון 1, 0 או -1.

הבדלים בין העץ האדום-שחור לעץ AVL.

להלן ההבדלים בין העץ האדום-שחור לעץ AVL:

עץ חיפוש בינארי

העץ האדום-שחור הוא עץ חיפוש בינארי, ועץ ה-AVL הוא גם עץ חיפוש בינארי.

כללים

הכללים הבאים מיושמים בעץ אדום-שחור:

localdatetime java

1. הצומת בעץ אדום-שחור הוא בצבע אדום או שחור.
2. צבע צומת השורש צריך להיות שחור.
3. הצמתים הסמוכים לא צריכים להיות אדומים. במילים אחרות, אנו יכולים לומר שלצומת האדום לא יכולים להיות ילדים אדומים, אבל לצומת השחור יכולים להיות ילדים שחורים.
4. צריך להיות אותו מספר של צמתים שחורים בכל נתיב; לאחר מכן, רק עץ יכול להיחשב כעץ אדום-שחור.
5. הצמתים החיצוניים הם הצמתים האפסיים, שצבעם תמיד שחור.

כלל עץ ה-AVL:

לכל צומת צריך להיות מקדם האיזון כ-1, 0 או 1.

דוגמא

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

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

איך העץ יכול להיחשב כעץ מאוזן או לא?

במקרה של עץ אדום-שחור, אם מתקיימים כל הכללים הנ'ל, בתנאי שעץ הוא עץ חיפוש בינארי, אזי העץ הוא עץ אדום-שחור.

במקרה של עץ AVL, אם גורם האיזון הוא -1, 0 או 1, אזי העץ הנ'ל הוא עץ AVL.

כלים המשמשים לאיזון

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

צביעה מחדש רוֹטַציָה

אם העץ אינו מאוזן, אזי נעשה שימוש בכלי אחד לאיזון העץ בעץ AVL:

קו תחתון באמצעות css

רוֹטַציָה

יעיל לאיזה פעולה

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

במקרה של עץ AVL, פעולת החיפוש יעילה שכן היא דורשת רק כלי אחד כדי לאזן את העץ.

מורכבות הזמן

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

במקרה של עץ AVL, מורכבות הזמן עבור כל הפעולות, כלומר, הכנסה, מחיקה וחיפוש היא O(logn).

בואו נבין את ההבדלים בצורת הטבלה.