TechCodeview

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

מהו עץ חיפוש בינארי?

ה עץ חיפוש בינארי הוא עֵץ עץ בינארי . כידוע, לעץ זה יכול להיות מספר 'n' של ילדים, ואילו; העץ הבינארי יכול להכיל את שני הילדים המירביים. אז, האילוץ של עץ בינארי מלווה גם בעץ החיפוש הבינארי. לכל צומת בעץ חיפוש בינארי צריכים להיות שני ילדים לכל היותר; במילים אחרות, אנו יכולים לומר שעץ החיפוש הבינארי הוא גרסה של העץ הבינארי.

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

ב-Binary Search Tree, האלמנט האמצעי הופך לצומת השורש, החלק הימני הופך לעץ המשנה הימני, והחלק השמאלי הופך לעץ המשנה השמאלי. לכן, אנו יכולים לומר שעץ החיפוש הבינארי הוא שילוב של a עץ בינארי ו חיפוש בינארי .

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

מורכבות זמן בעץ החיפוש הבינארי

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

הגדרת נתיב פיתון

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

מהו עץ AVL?

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

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

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

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

ג'אווה פרטית מול ציבורית

נניח שאנחנו רוצים להכניס 10, 20, 30 בעץ AVL.

להלן הדרכים להכנסת 10, 20, 30 בעץ AVL:

אם סדר ההכנסה הוא 30, 20, 10.

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

שלב 2: באיור לעיל, אנו יכולים לראות שהעץ אינו מאוזן מכיוון שמקדם האיזון של צומת 30 הוא 2. על מנת להפוך אותו לעץ AVL, עלינו לבצע כמה סיבובים. אם נבצע את הסיבוב הימני בצומת 20 אז הצומת 30 יזוז כלפי מטה, ואילו הצומת 20 יזוז כלפי מעלה, כפי שמוצג להלן:

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

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

אם סדר ההכנסה הוא 10, 20, 30.

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

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

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

אם סדר ההכנסה הוא 30, 10, 20

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

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

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

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

אם סדר ההכנסה הוא 10, 30, 20

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

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

ערך של מחרוזת

ובכל זאת, העץ לעיל אינו מאוזן, ולכן עלינו לבצע סיבוב שמאלה על הצומת. לאחר ביצוע הסיבוב השמאלי, הצומת 20 יזוז כלפי מעלה, והצומת 10 יזוז כלפי מטה כפי שמוצג להלן:

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

הבדלים בין עץ החיפוש הבינארי לעץ AVL