מתוך ויקיפדיה, האנציקלופדיה החופשית

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

[עריכה] סוגי עצים

[עריכה] עץ בינארי

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

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

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

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

[עריכה] עצים בינאריים נפוצים

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

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

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

עצי kd - עצים שמשמשים לחיפוש נקודות במרחב k-ממדי ומנצלים את האספקט הגאומטרי של הנתונים.

[עריכה] מסלולי מעבר

קיימות כמה שיטות מעבר נפוצות על עצים בינאריים.

שלוש השיטות הפשוטות והנפוצות ביותר הן -

[עריכה] סדר תחילי (preorder traversal)

   print node.value
   if node.left  != null then visit(node.left)
   if node.right != null then visit(node.right)

[עריכה] סדר תוכי (inorder traversal)

   if node.left  != null then visit(node.left)
   print node.value
   if node.right != null then visit(node.right)

[עריכה] סדר סופי (postorder traversal)

   if node.left  != null then visit(node.left)
   if node.right != null then visit(node.right)
   print node.value

הראשונה (preorder) מבקרת בקודקוד ואחר כך פונה לקרוא את תתי העץ שלו, תחילה השמאלי ואחר כך הימני.

שיטה נוספת (inorder) קוראת את תת־העץ השמאלי, מבקרת בשורש, ולבסוף תת־העץ הימני.

בשיטה השלישית (postorder) קוראים את שני תתי העצים ורק אז עורכים ביקור בשורש.

שיטה נוספת היא מעבר רוחבי על רמות העומק בעץ בזו אחר זו.

[עריכה] עצים לא בינאריים

קיימים כמה סוגים של עצים לא בינאריים. החשובים שבהם הם עצי multiway מסדר m, שבהם לכל אב יש עד m בנים (כל עץ יקבל m משלו לפי הצורך). ואריאציה שלהם הם עצי B, שבהם כל העלים באותה רמה ומספר הבנים אינו נמוך לעולם ממחצית m. ואריאציה נוספת היא עצי B+. בעצים אלו כל הקודקודים עד העלים אינם מכילים מידע, אלא משמשים אך ורק כמפתחות המכוונים את מסלול החיפוש.

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

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