כל מה שרצית לדעת על עץ Splay:
במדעי המחשב, עץ Splay הוא מבנה נתונים של עץ חיפוש בינארי מאוזן בעל התכונה המאפשרת גישה חוזרת מהירה לאיברים אליהם בוצעה גישה לאחרונה.
הוא מאפשר פעולות בסיסיות כגון הכנסה, חיפוש והסרה של איברים בסיבוכיות זמן של O ( log n ) {\displaystyle \ O(\log n)} (בניתוח לשיעורין).
עבור פעולות לא אקראיות רבות, עץ Splay מתגלה כיעיל יותר מעצי חיפוש אחרים, אפילו כאשר תבנית רצף הפעולות המסוימת אינה ידועה מראש.
עץ ה-Splay הומצא על ידי דניאל סליטור ורוברט טרג'אן ב-1985.
בעץ Splay, לכל הפעולות הרגילות שניתן לבצע על עץ חיפוש בינארי מתווספת פעולה בסיסית נוספת הנקראת splaying.
ביצוע splaying לעץ עבור איבר מסוים פירושו ארגון מחדש של העץ כך שהאיבר ימצא בשורשו של העץ.
דרך אחת לבצע זאת היא ראשית על ידי ביצוע של חיפוש בינארי רגיל של האיבר בעץ ולאחר מכן להשתמש בפעולות סיבוב בעץ, בדומה לפעולות הסיבוב המבוצעות בעץ AVL, כדי להביא את האיבר אל שורש העץ.
לחלופין, אלגוריתם top- down יכול לשלב את פעולת החיפוש ופעולת הסידור לכדי שלב ביצוע אחד.
מבני נתוניםמבנים מופשטיםרשימה • מחסנית • קבוצה • רב קבוצה • תור • דו-תור • תור עדיפויות • מילון • מחרוזת • איחוד קבוצות זרותמימושים ליניארייםמערך • מערך משונן • טבלת גיבוב • רשימה מקושרת • רשימת דילוגים • חוצץגרפים ועציםערימה (בינארית • בינומית • פיבונאצ'י) • עץ חיפוש (עץ אדום שחור • עץ 2-3 • עץ 2-3-4) • עץ סיפות • עץ B • עץ +B • עץ AVL • עץ Splay • עץ BSP • עץ kd • עץ R • טריי X מהיר • טריי y מהיר• [[עץ WAVL]]הסתברותייםפילטר בלום ערך זה הוא קצרמר בנושא מדעי המחשב.
אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.
אוחזר מתוך "https://he.
wikipedia.
org/w/index.
php?title=עץ_Splay&oldid=23619110"קטגוריות: קצרמר מדעי המחשבעצי חיפושקטגוריה מוסתרת: קצרמר – כל הערכים
נלקח מויקיפדיה