עץ חיפוש בינארי (BST) - מבנה החיפוש הקלאסי
הבנת תכונת ה-BST, פעולות חיפוש והכנסה, ומדוע איזון העץ הוא קריטי.
עץ חיפוש בינארי (Binary Search Tree, BST) הוא עץ בינארי שבו לכל צומת: כל הערכים בתת-העץ השמאלי קטנים ממנו, וכל הערכים בתת-העץ הימני גדולים ממנו. תכונה זו מאפשרת חיפוש יעיל בסיבוכיות O(log n) בעץ מאוזן.
פעולת חיפוש
חיפוש ב-BST דומה לחיפוש בינארי במערך ממוין: בכל צומת משווים את הערך המבוקש לערך הצומת ופונים שמאלה או ימינה בהתאם.
function search(node, target) {
if (!node) return null;
if (target === node.val) return node;
return target < node.val
? search(node.left, target)
: search(node.right, target);
}הכנסה ומחיקה
הכנסה: יורדים לפי כללי החיפוש עד שמגיעים למיקום ריק ושותלים שם את הצומת החדש. מחיקה מורכבת יותר ויש לה שלושה מקרים: צומת ללא בנים, צומת עם בן אחד, וצומת עם שני בנים (מחליפים עם ה-in-order successor).
הבעיה של חוסר איזון
אם מכניסים ל-BST ערכים בסדר ממוין (1, 2, 3, 4...), העץ הופך ל'שרשרת' לינארית וכל פעולה הופכת ל-O(n) - איבדנו את כל היתרון!
עצים מאוזנים
כדי להבטיח גובה O(log n) בכל מקרה, פותחו וריאציות מאוזנות:
- AVL Tree - עץ מאוזן באופן הדוק (הפרש גובה ≤ 1) עם סיבובים אחרי כל הכנסה/מחיקה
- Red-Black Tree - עץ מאוזן 'בערך' שדורש פחות סיבובים (משמש ב-TreeMap של Java ו-std::map ב-C++)
- B-Tree - עץ עם הרבה בנים בכל צומת, אופטימלי למסדי נתונים ומערכות קבצים
מעבר על עץ (Tree Traversal)
- In-order (שמאל-שורש-ימין) - מחזיר את הערכים בסדר ממוין ב-BST
- Pre-order (שורש-שמאל-ימין) - שימושי לשכפול עץ
- Post-order (שמאל-ימין-שורש) - שימושי למחיקת עץ
- Level-order (BFS) - מעבר שכבה-שכבה