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

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

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

איור 1: ייצוג של פריטי נתונים

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

מהו מבנה נתונים?

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

ההיקף של מודל נתונים מסוים תלוי בשני גורמים:

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

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

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

רשימת קישורים java

טרמינולוגיות בסיסיות הקשורות למבני נתונים

מבני נתונים הם אבני הבניין של כל תוכנה או תוכנית. בחירת מבנה הנתונים המתאים לתוכנית היא משימה מאתגרת ביותר עבור מתכנת.

להלן כמה מינוחים בסיסיים המשמשים בכל פעם שמבני הנתונים מעורבים:

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

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

המונח 'מידע' משמש לעתים עבור נתונים עם תכונות נתונות של נתונים משמעותיים או מעובדים.

שדה:יחידת מידע בסיסית אחת המסמלת את התכונה של ישות ידועה בשם שדה.תקליט:אוסף של פריטי נתונים שונים ידוע כרשומה. לדוגמה, אם אנחנו מדברים על ישות העובד, אז ניתן לקבץ את השם, המזהה, הכתובת ותואר העבודה שלו כדי ליצור את הרשומה עבור העובד.קוֹבֶץ:אוסף של רשומות שונות מסוג ישות אחד ידוע כקובץ. לדוגמה, אם יש 100 עובדים, יהיו 25 רשומות בקובץ הקשור המכיל נתונים על כל עובד.

הבנת הצורך במבני נתונים

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

מדוע עלינו ללמוד מבני נתונים?

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

הבנת המטרות של מבני נתונים

מבני נתונים עומדים בשתי יעדים משלימים:

עץ בינארי לעומת bst

נְכוֹנוּת:מבני נתונים מתוכננים לפעול בצורה נכונה עבור כל מיני תשומות בהתבסס על תחום העניין. במילים סדר, נכונות מהווה את המטרה העיקרית של מבנה הנתונים, שתלוי תמיד בבעיות שמבנה הנתונים נועד לפתור.יְעִילוּת:מבני נתונים גם דורשים להיות יעילים. זה אמור לעבד את הנתונים במהירות מבלי לנצל משאבי מחשב רבים כמו שטח זיכרון. במצב של זמן אמת, היעילות של מבנה נתונים היא גורם מפתח בקביעת הצלחתו וכישלון התהליך.

הבנת כמה תכונות עיקריות של מבני נתונים

כמה מהתכונות המשמעותיות של מבני נתונים הם:

יציבות:ככלל, כל מתכנתי המחשבים שואפים לייצר תוכנה שמניבה פלט נכון לכל קלט אפשרי, יחד עם ביצוע יעיל בכל פלטפורמות החומרה. סוג זה של תוכנה חזקה חייב לנהל קלט תקף ולא חוקי כאחד.סְגִילוּת:בניית יישומי תוכנה כמו דפדפני אינטרנט, מעבדי תמלילים ומנוע חיפוש אינטרנט כוללים מערכות תוכנה ענקיות הדורשות עבודה או ביצוע נכון ויעילה למשך שנים רבות. יתרה מכך, תוכנה מתפתחת עקב טכנולוגיות מתפתחות או תנאי שוק משתנים ללא הרף.שימוש חוזר:תכונות כמו שימוש חוזר ויכולת הסתגלות הולכים יד ביד. ידוע שהמתכנת זקוק למשאבים רבים כדי לבנות כל תוכנה, מה שהופך אותה למפעל יקר. עם זאת, אם התוכנה מפותחת בצורה ניתנת לשימוש חוזר וניתנת להתאמה, אזי ניתן ליישם אותה ברוב היישומים העתידיים. כך, על ידי ביצוע מבני נתונים איכותיים, ניתן לבנות תוכנה לשימוש חוזר, שנראה כי היא חסכונית וחסכונית בזמן.

סיווג מבני נתונים

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

אנו יכולים לסווג מבני נתונים לשתי קטגוריות:

1. מבנה נתונים פרימיטיבי
2. מבנה נתונים לא פרימיטיבי

האיור הבא מציג את הסיווגים השונים של מבני נתונים.

איור 2: סיווגים של מבני נתונים

מבני נתונים פרימיטיביים

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

מבני נתונים לא פרימיטיביים

מבני נתונים לא פרימיטיבייםהם אותם מבני נתונים הנגזרים ממבני נתונים פרימיטיביים.
1. לא ניתן לתפעל או להפעיל מבני נתונים אלה ישירות על ידי הוראות ברמת המכונה.
2. ההתמקדות של מבני נתונים אלה היא ביצירת קבוצה של רכיבי נתונים שהם אחד מהם הוֹמוֹגֵנִי (אותו סוג נתונים) או הֵטֵרוֹגֵנִי (סוגי נתונים שונים).
3. בהתבסס על המבנה והסידור של הנתונים, אנו יכולים לחלק את מבני הנתונים הללו לשתי תת-קטגוריות -
   1. מבני נתונים ליניאריים
   2. מבני נתונים לא לינאריים

מבני נתונים ליניאריים

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

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

מבני נתונים סטטיים:מבני הנתונים בעלי גודל קבוע ידועים בתור מבני נתונים סטטיים. הזיכרון עבור מבני נתונים אלה מוקצה בזמן המהדר, ולא ניתן לשנות את גודלם על ידי המשתמש לאחר ההידור; עם זאת, ניתן לשנות את הנתונים המאוחסנים בהם.
ה מַעֲרָך הוא הדוגמה הטובה ביותר למבנה הנתונים הסטטי מכיוון שיש להם גודל קבוע, וניתן לשנות את הנתונים שלו מאוחר יותר.מבני נתונים דינמיים:מבני הנתונים בעלי גודל דינמי ידועים בשם מבני נתונים דינמיים. הזיכרון של מבני נתונים אלה מוקצה בזמן הריצה, וגודלם משתנה במהלך זמן הריצה של הקוד. יתר על כן, המשתמש יכול לשנות את הגודל כמו גם את רכיבי הנתונים המאוחסנים במבני נתונים אלה בזמן הריצה של הקוד.
רשימות מקושרות, ערימות , ו פרָאק הן דוגמאות נפוצות למבני נתונים דינמיים

סוגי מבני נתונים ליניאריים

להלן רשימת מבני הנתונים ליניאריים שבהם אנו משתמשים בדרך כלל:

1. מערכים

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

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

איור 3. מערך

ניתן לסווג מערכים לסוגים שונים:

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

כמה יישומים של מערך:

1. אנו יכולים לאחסן רשימה של רכיבי נתונים השייכים לאותו סוג נתונים.
2. מערך פועל כאחסון עזר למבני נתונים אחרים.
3. המערך גם עוזר לאחסן רכיבי נתונים של עץ בינארי של הספירה הקבועה.
4. מערך פועל גם כאחסון של מטריצות.

2. רשימות מקושרות

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

איור 4. רשימה מקושרת

ניתן לסווג רשימות מקושרות לסוגים שונים:

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

כמה יישומים של רשימות מקושרות:

1. הרשימות המקושרות עוזרות לנו ליישם ערימות, תורים, עצים בינאריים וגרפים בגודל מוגדר מראש.
2. אנחנו יכולים גם ליישם את הפונקציה של מערכת ההפעלה לניהול זיכרון דינמי.
3. רשימות מקושרות מאפשרות גם יישום פולינום עבור פעולות מתמטיות.
4. אנו יכולים להשתמש ברשימה מעגלית כדי ליישם מערכות הפעלה או פונקציות יישומים שמבצעות משימות עגולות.
5. רשימה מקושרת מעגלית מועילה גם בהצגת שקופיות שבה משתמש צריך לחזור לשקופית הראשונה לאחר הצגת השקופית האחרונה.
6. רשימה מקושרת כפולה משמשת ליישום כפתורים קדימה ואחורה בדפדפן כדי לנוע קדימה ואחורה בדפים הפתוחים של אתר אינטרנט.

3. ערימות

א לַעֲרוֹם הוא מבנה נתונים ליניארי העוקב אחר ה LIFO עקרון (Last In, First Out) המאפשר פעולות כמו הכנסה ומחיקה מקצה אחד של ה-Stack, כלומר, Top. ניתן ליישם ערימות בעזרת זיכרון רציף, מערך וזיכרון לא רציף, רשימה מקושרת. דוגמאות מהחיים האמיתיים של ערימות הן ערימות של ספרים, חפיסת קלפים, ערימות של כסף ועוד רבים.

איור 5. דוגמה מהחיים האמיתיים של Stack

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

הפעולות העיקריות ב-Stack הן כדלקמן:

לִדחוֹף:פעולה להכנסת אלמנט חדש למחסנית נקראת פעולת דחיפה.פּוֹפּ:פעולה להסרה או מחיקה של אלמנטים מהמחסנית נקראת פעולת פופ.

איור 6. מחסנית

כמה יישומים של ערימות:

1. המחסנית משמשת כמבנה אחסון זמני עבור פעולות רקורסיביות.
2. מחסנית משמשת גם כמבנה אחסון עזר עבור קריאות לפונקציות, פעולות מקוננות ופונקציות נדחות/נדחות.
3. אנו יכולים לנהל קריאות לפונקציות באמצעות Stacks.
4. ערימות משמשות גם כדי להעריך את הביטויים האריתמטיים בשפות תכנות שונות.
5. ערימות מועילות גם בהמרת ביטויי אינפיקס לביטויי postfix.
6. ערימות מאפשרות לנו לבדוק את תחביר הביטוי בסביבת התכנות.
7. אנו יכולים להתאים סוגריים באמצעות Stacks.
8. ניתן להשתמש בערימות כדי להפוך מחרוזת.
9. ערימות מועילות בפתרון בעיות המבוססות על חזרה לאחור.
10. אנו יכולים להשתמש ב-Stacks בחיפוש עומק-ראשון בגרף ומעבר עצים.
11. ערימות משמשות גם בפונקציות של מערכת ההפעלה.
12. ערימות משמשות גם בפונקציות UNDO ו-REDO בעריכה.

4. זנבות

java 8

א תוֹר הוא מבנה נתונים ליניארי הדומה ל-Stack עם כמה מגבלות על הכנסה ומחיקה של האלמנטים. הכנסת אלמנט ל-Queue מתבצעת בקצה אחד, וההסרה מתבצעת בקצה אחר או הפוך. לפיכך, אנו יכולים להסיק שמבנה הנתונים בתור עוקב אחר עקרון ה-FIFO (ראשון נכנס, ראשון יוצא) כדי לתפעל את רכיבי הנתונים. יישום של תורים יכול להיעשות באמצעות מערכים, רשימות מקושרות או ערימות. כמה דוגמאות מהחיים האמיתיים של תורים הם תור בדלפק הכרטיסים, מדרגות נעות, שטיפת מכוניות ורבים נוספים.

איור 7. דוגמה מהחיים האמיתיים לתור

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

להלן הפעולות העיקריות של התור:

תור:הוספה או הוספה של רכיבי נתונים מסוימים לתור נקראת Enqueue. הכנסת האלמנטים נעשית תמיד בעזרת המצביע האחורי.תור:מחיקה או הסרה של רכיבי נתונים מהתור נקראת Dequeue. מחיקת האלמנט נעשית תמיד בעזרת המצביע הקדמי.

הספרה 8. תוֹר

כמה יישומים של תורים:

עבור מערך מחרוזות java

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

מבני נתונים לא לינאריים

מבני נתונים לא לינאריים הם מבני נתונים שבהם רכיבי הנתונים אינם מסודרים בסדר רציף. כאן, הכנסת והסרה של נתונים אינם אפשריים באופן ליניארי. קיים קשר היררכי בין פריטי הנתונים הבודדים.

סוגי מבני נתונים לא לינאריים

להלן הרשימה של מבני נתונים לא לינאריים שבהם אנו משתמשים בדרך כלל:

1. עצים

עץ הוא מבנה נתונים לא לינארי והיררכיה המכילה אוסף של צמתים כך שכל צומת של העץ מאחסן ערך ורשימת הפניות לצמתים אחרים (ה'ילדים').

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

איור 9. עץ

ניתן לסווג עצים לסוגים שונים:

עץ בינארי:מבנה נתוני עץ שבו לכל צומת אב יכולים להיות לכל היותר שני ילדים נקרא עץ בינארי.עץ חיפוש בינארי:עץ חיפוש בינארי הוא מבנה נתוני עץ שבו אנו יכולים לשמור בקלות רשימה ממוינת של מספרים.עץ AVL:עץ AVL הוא עץ חיפוש בינארי המאזן את עצמו שבו כל צומת שומר מידע נוסף המכונה Balance Factor שהערך שלו הוא -1, 0 או +1.B-Tree:B-Tree הוא סוג מיוחד של עץ חיפוש בינארי המאזן את עצמו כאשר כל צומת מורכב ממספר מפתחות ויכולים להכיל יותר משני ילדים.

כמה יישומים של עצים:

1. עצים מיישמים מבנים היררכיים במערכות מחשב כמו ספריות ומערכות קבצים.
2. עצים משמשים גם ליישום מבנה הניווט של אתר אינטרנט.
3. אנחנו יכולים ליצור קוד כמו הקוד של האפמן באמצעות עצים.
4. עצים מועילים גם בקבלת החלטות ביישומי גיימינג.
5. עצים אחראים להטמעת תורי עדיפות עבור פונקציות תזמון מערכת הפעלה מבוססות עדיפות.
6. עצים אחראים גם לניתוח ביטויים והצהרות במהדרים של שפות תכנות שונות.
7. אנו יכולים להשתמש בעצים כדי לאחסן מפתחות נתונים לאינדקס עבור מערכת ניהול מסדי נתונים (DBMS).
8. Spanning Trees מאפשר לנו לנתב החלטות ברשתות מחשבים ותקשורת.
9. עצים משמשים גם באלגוריתם מציאת הנתיבים המיושם ביישומי בינה מלאכותית (AI), רובוטיקה ומשחקי וידאו.

2. גרפים

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

מבנה נתוני הגרף, G נחשב למבנה מתמטי המורכב מקבוצה של קודקודים, V וקבוצת קצוות, E כפי שמוצג להלן:

G = (V,E)

איור 10. גרף

האיור שלמעלה מייצג גרף בעל שבעה קודקודים A, B, C, D, E, F, G ועשרה קצוות [A, B], [A, C], [B, C], [B, D], [B, E], [C, D], [D, E], [D, F], [E, F] ו-[E, G].

בהתאם למיקום הקודקודים והקצוות, ניתן לסווג את הגרפים לסוגים שונים:

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

כמה יישומים של גרפים:

1. גרפים עוזרים לנו לייצג מסלולים ורשתות ביישומי תחבורה, נסיעות ותקשורת.
2. גרפים משמשים להצגת מסלולים ב-GPS.
3. גרפים גם עוזרים לנו לייצג את הקשרים ההדדיים ברשתות חברתיות ויישומים אחרים מבוססי רשת.
4. גרפים משמשים ביישומי מיפוי.
5. גרפים אחראים לייצוג העדפות המשתמש ביישומי מסחר אלקטרוני.
6. גרפים משמשים גם ברשתות שירות על מנת לזהות את הבעיות העולות לתאגידים מקומיים או עירוניים.
7. גרפים גם עוזרים לנהל את הניצול והזמינות של משאבים בארגון.
8. גרפים משמשים גם ליצירת מפות קישורים למסמכים של אתרי האינטרנט על מנת להציג את הקישוריות בין הדפים באמצעות היפר-קישורים.
9. גרפים משמשים גם בתנועות רובוטיות וברשתות עצביות.

פעולות בסיסיות של מבני נתונים

בסעיף הבא, נדון בסוגי הפעולות השונות שאנו יכולים לבצע כדי לתפעל נתונים בכל מבנה נתונים:

מעבר:מעבר במבנה נתונים פירושו גישה לכל רכיב נתונים פעם אחת בדיוק כדי שניתן יהיה לנהל אותו. למשל, נדרשת מעבר תוך הדפסת שמות כל העובדים במחלקה.לחפש:חיפוש הוא פעולת מבנה נתונים נוספת שמשמעותה למצוא את המיקום של רכיב נתונים אחד או יותר העומדים באילוצים מסוימים. רכיב נתונים כזה עשוי להיות קיים בקבוצה הנתונה של רכיבי נתונים או לא. לדוגמה, אנו יכולים להשתמש בפעולת החיפוש כדי למצוא את שמות כל העובדים בעלי ניסיון של יותר מ-5 שנים.הַכנָסָה:הכנסה פירושה הכנסה או הוספה של רכיבי נתונים חדשים לאוסף. לדוגמה, אנו יכולים להשתמש בפעולת ההכנסה כדי להוסיף פרטים של עובד חדש שהחברה שכרה לאחרונה.מְחִיקָה:מחיקה פירושה להסיר או למחוק רכיב נתונים ספציפי מרשימת רכיבי הנתונים הנתונה. לדוגמה, נוכל להשתמש בפעולת המחיקה כדי למחוק את שמו של עובד שעזב את העבודה.מִיוּן:מיון פירושו לסדר את רכיבי הנתונים בסדר עולה או יורד בהתאם לסוג היישום. לדוגמא, נוכל להשתמש בפעולת המיון כדי לסדר את שמות העובדים במחלקה בסדר אלפביתי או להעריך את שלושת המבצעים הטובים ביותר של החודש על ידי סידור ביצועי העובדים בסדר יורד וחילוץ הפרטים של שלושת הראשונים.לְמַזֵג:מיזוג פירושו לשלב רכיבי נתונים של שתי רשימות ממוינות כדי ליצור רשימה אחת של רכיבי נתונים ממוינים.לִיצוֹר:יצירה היא פעולה המשמשת לשמור זיכרון עבור רכיבי הנתונים של התוכנית. אנו יכולים לבצע פעולה זו באמצעות הצהרת הצהרת. יצירת מבנה הנתונים יכולה להתרחש במהלך הפעולות הבאות:
1. זמן קומפילציה
2. זמן ריצה
   לדוגמה, ה malloc() הפונקציה משמשת בשפת C ליצירת מבנה נתונים.
בְּחִירָה:בחירה פירושה בחירת נתון מסוים מתוך הנתונים הזמינים. אנו יכולים לבחור כל נתון מסוים על ידי ציון תנאים בתוך הלולאה.עדכון:פעולת העדכון מאפשרת לנו לעדכן או לשנות את הנתונים במבנה הנתונים. אנו יכולים גם לעדכן כל מידע מסוים על ידי ציון תנאים מסוימים בתוך הלולאה, כמו פעולת הבחירה.פְּצִיחָה:פעולת הפיצול מאפשרת לנו לחלק נתונים לחלקי משנה שונים, תוך הפחתת זמן השלמת התהליך הכולל.

הבנת סוג הנתונים המופשטים

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

כל הכוונות פקודה אקסל

מההגדרה שהוזכרה לעיל, אנו יכולים להסיק שהפעולות במבנה הנתונים כוללות:

1. רמה גבוהה של הפשטות כמו הוספה או מחיקה של פריט מרשימה.
2. חיפוש ומיון של פריט ברשימה.
3. גישה לפריט בעל העדיפות הגבוהה ביותר ברשימה.

בכל פעם שמבנה הנתונים מבצע פעולות כאלה, הוא ידוע בתור an סוג נתונים מופשט (ADT) .

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

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

הבנת היתרונות של שימוש ב-ADTs

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

כמה יישומים של מבני נתונים

להלן כמה יישומים של מבני נתונים:

1. מבני נתונים מסייעים בארגון הנתונים בזיכרון המחשב.
2. מבני נתונים מסייעים גם בייצוג המידע במסדי נתונים.
3. מבני נתונים מאפשרים יישום של אלגוריתמים לחיפוש באמצעות נתונים (לדוגמה, מנוע חיפוש).
4. אנו יכולים להשתמש במבני הנתונים כדי ליישם את האלגוריתמים כדי לתפעל נתונים (לדוגמה, מעבדי תמלילים).
5. אנו יכולים גם ליישם את האלגוריתמים לניתוח נתונים באמצעות מבני נתונים (לדוגמה, כורי נתונים).
6. מבני נתונים תומכים באלגוריתמים להפקת הנתונים (לדוגמה, מחולל מספרים אקראיים).
7. מבני נתונים תומכים גם באלגוריתמים לדחיסה ולפירוק של הנתונים (לדוגמה, כלי zip).
8. אנו יכולים גם להשתמש במבני נתונים כדי ליישם אלגוריתמים להצפנה ולפענוח הנתונים (לדוגמה, מערכת אבטחה).
9. בעזרת Data Structures נוכל לבנות תוכנה שיכולה לנהל קבצים וספריות (למשל מנהל קבצים).
10. אנחנו יכולים גם לפתח תוכנה שיכולה לעבד גרפיקה באמצעות מבני נתונים. (לדוגמה, דפדפן אינטרנט או תוכנת רינדור תלת מימד).

מלבד אלה, כפי שצוין קודם לכן, יש עוד הרבה יישומים של Data Structures שיכולים לעזור לנו לבנות כל תוכנה רצויה.