Loading AI tools
מוויקיפדיה, האנציקלופדיה החופשית
במדעי המחשב עץ חיפוש הוא מבנה נתונים ממוין, המאפשר הכנסה, הוצאה וחיפוש מהירים. עץ החיפוש מתבסס על מבנה העץ בתורת הגרפים.
עבור עץ G וצמתים v ,u
עץ חיפוש בינארי הוא עץ הנתונים הפופולרי ביותר. בעץ זה יש לכל קודקוד שני בנים לכל היותר, ימני ושמאלי. הבן הימני, יחד עם כל צאצאיו, נמצא ביחס הסדר אחרי הקודקוד שממנו הוא יוצא, ואילו הבן השמאלי וכל צאצאיו קודמים לקודקוד האב ביחס הסדר.
כדי להוסיף קודקוד חדש לעץ יעבור האלגוריתם על כל קודקוד וקודקוד החל מהשורש, וינוע ימינה כאשר מפתח הקודקוד הנוכחי במסלול קטן מהמפתח של הקודקוד המוכנס, ושמאלה במקרה ההפוך. האלגוריתם ייעצר ויבצע את ההוספה במקום שבו המסלול ייגמר.
כדי למחוק קודקוד יש תחילה למצוא אותו, ולאחר מכן אם הוא עלה פשוט למחוק אותו, אם יש לו בן אחד בלבד למחוק ולהפוך את הבן הזה לבן של האבא של מה שמחקנו, ואם יש לו שני בנים, למצוא את העוקב (הקודקוד הקטן ביותר שגדול ממנו) שבהכרח אין לו בן שמאלי, למחוק את העוקב ולהחליף את הקודקוד שלנו בעוקב. לשם ביצוע פעולות אלו ביעילות יש לשמור גם מצביע להורה.
מאחר שלעץ בינארי יש שני בנים, הרי שבמקרה של עץ מלא במידה שווה, גובהו יהיה Log n, עבור n נתונים (log בסיס 2). במצב כזה חיפוש בעץ יימשך פרק זמן קצר יחסית הנמצא בסיבוכיות לוגריתמית למספר הנתונים. אומנם, ייתכנו מקרים גרועים, למשל הכנסה בסדר ממוין מראש, שבהם גובה העץ יהיה n, ועלות החיפוש גבוהה. סיבוכיות הזמן בחיפוש נתון בעץ חיפוש בינארי היא (O(n במקרה הגרוע ו-((O(log(n במקרה הממוצע.
כדי להבטיח שמצב כזה לא יתרחש פותחו אלגוריתמים משוכללים להכנסה לעצים בינאריים ולמחיקה מהם באופן המבטיח שגובה העץ לא יהיה גדול מדי. עליהם מבוססים כמה עצי נתונים בינאריים חשובים.
קיימות כמה שיטות מעבר נפוצות על עצים בינאריים.
שלוש השיטות הפשוטות והנפוצות ביותר הן:
קריאת הקודקוד, לאחר מכן קריאת תתי העץ שלו, תחילה תת-העץ השמאלי ואחר כך הימני. בהינתן הדפסת עץ המתבססות על סדר תחילי, ניתן אף לשחזר את העץ, אם אכן הוא עומד במאפייניו של עץ חיפוש.
function visit(node) print node.value if node.left != null then visit(node.left) if node.right != null then visit(node.right)
קריאת תת-העץ השמאלי, לאחר מכן קריאת השורש (הצומת ממנו התחלנו), ולאחר מכן תת-העץ הימני.
function visit(node) if node.left != null then visit(node.left) print node.value if node.right != null then visit(node.right)
עץ הוא עץ חיפוש אם ורק אם הסדר התוכי שלו ממוין.
קריאת תת-העץ השמאלי, לאחר מכן תת-העץ הימני ולאחר מכן קריאת השורש. בהינתן הדפסת עץ המתבססות על סדר סופי, ניתן אף לשחזר את העץ בצורה חד-חד ערכית, אם אכן הוא עומד במאפייניו של עץ חיפוש.
function visit(node) if node.left != null then visit(node.left) if node.right != null then visit(node.right) print node.value
בעץ חיפוש זה,
Breadth-first search (BFS)
שיטה נוספת היא מעבר רוחבי על רמות העומק בעץ בזו אחר זו: F, B, G, A, D, I, C, E, H (F ראשון).
קיימים כמה סוגים של עצים לא בינאריים. עצי multiway מסדר m, שבהם לכל אב יש עד m בנים (כל עץ יקבל m משלו לפי הצורך). וריאציה שלהם הם עצי B, שבהם כל העלים באותה רמה ומספר הבנים אינו נמוך לעולם ממחצית m. וריאציה נוספת היא עצי B+. בעצים אלו כל הקודקודים עד העלים אינם מכילים מידע, אלא משמשים אך ורק כמפתחות המכוונים את מסלול החיפוש.
השימוש בעצים אלו נוח כאשר חשוב לחסוך במספר החיפושים על ידי העלאת בסיס לוגריתם גובה העץ ובמקרה של עצי B+, כאשר חפצים שהעלים מכילי המידע יהיו מאוחסנים סדרתית.
סוג נוסף של עצים מאוזנים בהם הצמתים הפנימיים אינם מכילים מידע הם עצי R. עצים אלו משמשים לגישה למידע מרחבי, כלומר לנתונים עם אופי רב ממדי. נתונים כאלו יכולים להיות קואורדינטות גאוגרפיות, מלבנים וצורות גאומטריות נוספות. הרעיון העיקרי בעץ R הוא לקבץ עצמים שסמוכים זה לזה במרחב n-ממדי, ולייצג אותם ברמה גבוהה יותר בעץ על ידי מלבן חוסם מינימלי - המלבן ה-n-ממדי הקטן ביותר שמקיף אותם (ומקביל לצירים).
עץ חיפוש מסוג אחר הקרוי עץ תחיליות (או עץ חיפוש דיגיטלי) מאפשר חיפוש המתבסס על דמיון בתוך מרכיבים של שמות. העץ מסודר כך שכל מילה או מספר מפורק לרכיביו ומכל רכיב (אות, ספרה וכדומה) ניתן להמשיך לאחד הרכיבים האפשריים הבאים.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.