אנו קוראים את מבני הנתונים הליניאריים כמו מערך, רשימה מקושרת, מחסנית ותור שבהם כל האלמנטים מסודרים באופן רציף. מבני הנתונים השונים משמשים לסוגים שונים של נתונים.
כמה גורמים נלקחים בחשבון לבחירת מבנה הנתונים:
עץ הוא גם אחד ממבני הנתונים המייצגים נתונים היררכיים. נניח שאנו רוצים להציג את העובדים ואת עמדותיהם בצורה ההיררכית, אז ניתן לייצג את זה כפי שמוצג להלן:
העץ לעיל מציג את היררכיית ארגון של חברה כלשהי. במבנה הנ'ל, ג'ון האם ה מנכ'ל של החברה, ולג'ון יש שני דוחות ישירים בשם סטיב ו רוהן . לסטיב יש שלושה דיווחים ישירים לי, בוב, אלה איפה סטיב הוא מנהל. לבוב יש שני דוחות ישירים בשם יהיה ו אמה . אמה יש שני דוחות ישירים בשם טום ו ראג' . לטום יש דו'ח ישיר אחד בשם שטר כסף . המבנה הלוגי המסוים הזה ידוע בשם א עֵץ . המבנה שלו דומה לעץ האמיתי, ולכן הוא נקרא א עֵץ . במבנה זה, ה שורש נמצא בראש, וענפיו נעים בכיוון מטה. לכן, אנו יכולים לומר שמבנה הנתונים של העץ הוא דרך יעילה לאחסון הנתונים בצורה היררכית.
בואו נבין כמה נקודות מפתח של מבנה הנתונים של העץ.
- מבנה נתוני עץ מוגדר כאוסף של אובייקטים או ישויות הידועים כצמתים המקושרים יחד כדי לייצג או לדמות היררכיה.
- מבנה נתוני עץ הוא מבנה נתונים לא ליניארי מכיוון שהוא אינו מאחסן באופן רציף. זהו מבנה היררכי שכן אלמנטים בעץ מסודרים במספר רמות.
- במבנה נתוני העץ, הצומת העליון ידוע כצומת שורש. כל צומת מכיל נתונים מסוימים, ונתונים יכולים להיות מכל סוג. במבנה העץ לעיל, הצומת מכיל את שם העובד, כך שסוג הנתונים יהיה מחרוזת.
- כל צומת מכיל נתונים מסוימים ואת הקישור או הפניה של צמתים אחרים שניתן לקרוא להם ילדים.
כמה מונחים בסיסיים המשמשים במבנה הנתונים של עץ.
מיתר יצוק ל-int
הבה נבחן את מבנה העץ, המוצג להלן:
במבנה לעיל, כל צומת מסומן במספר כלשהו. כל חץ המוצג באיור שלמעלה ידוע בשם a קישור בין שני הצמתים.
מאפייני מבנה הנתונים של עץ
בהתבסס על המאפיינים של מבנה הנתונים של העץ, עצים מסווגים לקטגוריות שונות.
יישום עץ
ניתן ליצור את מבנה נתוני העץ על ידי יצירת הצמתים באופן דינמי בעזרת המצביעים. ניתן לייצג את העץ בזיכרון כפי שמוצג להלן:
מחרוזת לתוך מערך java
האיור שלמעלה מציג את הייצוג של מבנה נתוני העץ בזיכרון. במבנה הנ'ל, הצומת מכיל שלושה שדות. השדה השני מאחסן את הנתונים; השדה הראשון מאחסן את הכתובת של הילד השמאלי, והשדה השלישי מאחסן את הכתובת של הילד הימני.
בתכנות, ניתן להגדיר את המבנה של צומת כך:
struct node { int data; struct node *left; struct node *right; } ניתן להגדיר את המבנה לעיל רק עבור העצים הבינאריים מכיוון שלעץ הבינארי יכולים להיות שני ילדים לכל היותר, ולעצים גנריים יכולים להיות יותר משני ילדים. מבנה הצומת עבור עצים גנריים יהיה שונה בהשוואה לעץ הבינארי.
יישומים של עצים
להלן היישומים של עצים:
סוגי מבנה נתוני עץ
להלן הסוגים של מבנה נתוני עץ:
יכול להיות נ מספר תת-עצים בעץ כללי. בעץ הכללי, תתי העצים אינם מסודרים מכיוון שלא ניתן לסדר את הצמתים בתת העץ.
לכל עץ לא ריק יש קצה כלפי מטה, והקצוות הללו מחוברים לצמתים המכונים צמתים של ילדים . צומת השורש מסומן ברמה 0. הצמתים שיש להם אותו הורה ידועים בשם אחים .
כדי לדעת יותר על העץ הבינארי, לחץ על הקישור המופיע למטה:
https://www.javatpoint.com/binary-tree
כל צומת בתת-עץ השמאלי חייב להכיל ערך הנמוך מערכו של צומת השורש, והערך של כל צומת בתת-העץ הימני חייב להיות גדול מהערך של צומת השורש.
ניתן ליצור צומת בעזרת סוג נתונים המוגדר על ידי המשתמש הידוע בשם מבנה, כפי שמוצג מטה:
struct node { int data; struct node *left; struct node *right; } האמור לעיל הוא מבנה הצומת עם שלושה שדות: שדה נתונים, השדה השני הוא המצביע השמאלי של סוג הצומת, והשדה השלישי הוא המצביע הימני של סוג הצומת.
כדי לדעת יותר על עץ החיפוש הבינארי, לחץ על הקישור המופיע למטה:
https://www.javatpoint.com/binary-search-tree
אוספים בג'אווה
זהו אחד מסוגי העץ הבינארי, או שאנו יכולים לומר שהוא גרסה של עץ החיפוש הבינארי. עץ AVL מספק את הרכוש של עץ בינארי כמו גם של עץ חיפוש בינארי . זהו עץ חיפוש בינארי המאזן את עצמו שהומצא על ידי אדלסון ולסקי לינדאס . כאן, איזון עצמי פירושו איזון גבהים של תת-עץ שמאלי ותת-עץ ימני. איזון זה נמדד במונחים של גורם איזון .
אנו יכולים להתייחס לעץ כעץ AVL אם העץ מציית לעץ החיפוש הבינארי וכן לגורם מאזן. ניתן להגדיר את גורם האיזון כ- ההבדל בין גובה תת-העץ השמאלי לגובה תת-העץ הימני . הערך של גורם האיזון חייב להיות 0, -1 או 1; לכן, לכל צומת בעץ ה-AVL צריך להיות הערך של גורם האיזון כ-0, -1 או 1.
כדי לדעת יותר על עץ AVL, לחץ על הקישור המופיע למטה:
https://www.javatpoint.com/avl-tree
העץ האדום-שחור הוא עץ החיפוש הבינארי. התנאי המקדים של העץ האדום-שחור הוא שנדע על עץ החיפוש הבינארי. בעץ חיפוש בינארי, הערך של תת-העץ השמאלי צריך להיות קטן מהערך של אותו צומת, והערך של תת-העץ הימני צריך להיות גדול מהערך של אותו צומת. כפי שאנו יודעים שמורכבות הזמן של חיפוש בינארי במקרה הממוצע היא יומן2n, המקרה הטוב ביותר הוא O(1), והמקרה הגרוע ביותר הוא O(n).
כאשר מבצעים כל פעולה בעץ, אנו רוצים שהעץ שלנו יהיה מאוזן כך שכל הפעולות כמו חיפוש, הכנסת, מחיקה וכו', ייקח פחות זמן, ולכל הפעולות הללו תהיה מורכבות זמן של עֵץ2נ.
10 מ"ל לאונקים
העץ האדום-שחור הוא עץ חיפוש בינארי המאזן את עצמו. עץ AVL הוא גם עץ חיפוש בינארי מאזן גובה למה אנחנו צריכים עץ אדום-שחור . בעץ AVL לא יודעים כמה סיבובים יידרשו לאיזון העץ, אבל בעץ אדום-שחור נדרשות מקסימום 2 סיבובים לאיזון העץ. הוא מכיל ביט נוסף אחד המייצג את הצבע האדום או השחור של צומת כדי להבטיח את האיזון של העץ.
מבנה הנתונים של עץ ה-splay הוא גם עץ חיפוש בינארי שבו אלמנט שניגש אליו לאחרונה ממוקם במיקום השורש של העץ על ידי ביצוע כמה פעולות סיבוב. כאן, מתפזרים פירושו הצומת שהגישה אליו לאחרונה. זה איזון עצמי עץ חיפוש בינארי ללא תנאי איזון מפורש כמו AVL עֵץ.
ייתכן שהגובה של עץ הספליי אינו מאוזן, כלומר, הגובה של תת-העץ השמאלי והימני עשוי להיות שונה, אך הפעולות ב-splay tree מקבלות סדר של לְהַרְגִיעַ זמן איפה נ הוא מספר הצמתים.
עץ ספליי הוא עץ מאוזן אך אינו יכול להיחשב כעץ מאוזן גובה כי לאחר כל פעולה מתבצע סיבוב שמוביל לעץ מאוזן.
git rebase
מבנה הנתונים של Treap הגיע ממבנה הנתונים Tree and Heap. אז הוא כולל את המאפיינים של מבני נתונים של Tree וגם של Heap. בעץ החיפוש הבינארי, כל צומת בתת העץ השמאלי חייב להיות שווה או קטן מערכו של צומת השורש וכל צומת בתת העץ הימני חייב להיות שווה או גדול מערכו של צומת השורש. במבנה נתונים ערימה, תתי-עץ ימני ושמאלי גם יחד מכילים מפתחות גדולים יותר מהשורש; לכן, אנו יכולים לומר שצומת השורש מכיל את הערך הנמוך ביותר.
במבנה הנתונים של טרפ, לכל צומת יש את שניהם מַפְתֵחַ ו עדיפות כאשר המפתח נגזר מעץ החיפוש הבינארי והעדיפות נגזרת ממבנה הנתונים הערימה.
ה טפש מבנה הנתונים עוקב אחר שני מאפיינים המובאים להלן:
- בן ימין של צומת>=צומת נוכחי וצאצא שמאלי של צומת<=current node (binary tree)< li>
- ילדים של כל תת-עץ חייבים להיות גדולים מהצומת (ערימה)
B-tree הוא מאוזן m-way עץ איפה M מגדיר את סדר העץ. עד עכשיו, קראנו שהצומת מכיל רק מפתח אחד אבל b-tree יכול להיות יותר ממפתח אחד, ויותר מ-2 ילדים. זה תמיד שומר על הנתונים הממוינים. בעץ בינארי, ייתכן שצמתים עלים יכולים להיות ברמות שונות, אבל ב-b-tree, כל צמתי העלים חייבים להיות באותה רמה.
אם הסדר הוא m, לצומת יש את המאפיינים הבאים:
- לכל צומת בעץ b יכול להיות מקסימום M יְלָדִים
- עבור ילדים מינימליים, לצומת עלה יש 0 ילדים, לצומת שורש יש מינימום 2 ילדים ולצומת פנימי יש תקרה מינימלית של m/2 ילדים. לדוגמה, הערך של m הוא 5 מה שאומר שלצומת יכולים להיות 5 ילדים וצמתים פנימיים יכולים להכיל מקסימום 3 ילדים.
- לכל צומת יש מפתחות מקסימום (m-1).
צומת השורש חייב להכיל מפתח אחד לפחות וכל שאר הצמתים חייבים להכיל לפחות תקרה של m/2 מינוס 1 מפתחות.