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

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

היתרון בעץ זה הוא האפשרות לחפש איבר מסויים או למיין את האיברים בזמן מהיר יחסית לרשימה מקושרת או מערך. ניתן למצוא, להוסיף או למחוק איבר בזמן ממוצע של (O(logn, אך במקרה הגרוע ביותר פעולות אלה עלולות לקחת זמן (O(n.

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

הדגמה ויזואלית

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

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

struct bst_node {
   int data;
   bst_node *left_child;
   bst_node *right_child;
}

אם ידוע שהעץ מאוזן או קרוב למאוזן, ניתן להשתמש במערך המכיל את ערכי הצמתים. השורש יהיה במקום 1. לצומת הנמצאת במקום n, הבן הימני יהיה במקום 2n והבן השמאלי במקום 2n+1.

הפעולות הבסיסיות

• חיפוש: מציאת איבר בעל ערך מסויים.
• הוספת איבר
• מחיקת איבר
• הוצאת איברי העץ בסדר ממוין