tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
באופן כללי, אם נרצה להוסיף שדה לאיברי העץ, אז מובטח לנו שאם ניתן לחשב את ערך השדה של צומת על ידי המידע בצומת הנוכחי ושני בניו, אז אפשרי לתחזק את ערכי השדה בעץ בכל הצמתים במהלך פעולות הכנסה ומחיקה.
קביעה זו מסייעת לנו, לדוגמה, להרחיב עץ אדום שחור לעץ ערכי מיקום על ידי הוספת שדה size לכל צומת, המייצג את מספר הצמתים באותו תת-עץ שמייצג הצומת, ומאפשר מימוש שתי שאילתות מיקום בזמן log(n).
מבנה הנתונים המקורי הומצא בשנת 1972 על ידי רודולף באייר אשר קרא לו "עץ B בינארי סימטרי" ואת שמו המקורי קיבל במאמר שנכתב על ידי רוברט סדגוויק וליאונידס גויבס בשנת 1978.
עץ אדום שחור הוא סוג מיוחד של עץ חיפוש בינארי, בו משתמשים במדעי המחשב לארגון מידע בר השוואה כגון מספרים או טקסט.
העלים של עץ אדום שחור אינם מכילים מידע.
עלים אלו בדרך כלל לא מופיעים בזיכרון אלא מופיעים כ-null, שמשמעותו במדעי המחשב היא "כלום" או "ללא ערך" והוא בדרך כלל מיוצג על ידי 0, אך ניתן לפשט אלגוריתמים מסוימים באמצעות עלה יחיד המופיע בזיכרון המשמש לייצוג כל העלים של העץ.
כלומר, כל ההפניות מצמתים פנימיים לעלים מצביעות לאותו עלה.
לעיתים מגדירים עץ אדום שחור כעץ בו הקשתות צבועות ולא הצמתים אך למעשה אין לכך כל משמעות, צבעו של צומת בטרמינולוגיה של הערך יכול להיות צבעה של הקשת המחברת אותו לאביו, מלבד השורש, אשר צבעו תמיד שחור אך כפי שנראה בהמשך הגדרה זו אינה הכרחית ולא משמעותית במיוחד.
עץ אדום שחור הוא עץ בינארי בו לכל צומת קיים שדה המגדיר צבע, שערכו אדום או שחור.
בנוסף לדרישות הרגילות של עצי חיפוש בינאריים, עץ אדום שחור מקיים גם את הדרישות הבאות:
כל צומת הוא שחור או אדום בלבד.
כל העלים הריקים הם שחורים .
לצומת אדום אין צאצא אדום.
כל מסלול פשוט מצומת מסוים לכל אחד מהצאצאים העלים שלו מכיל אותו מספר של צמתים שחורים.
(מסקנה) אם לצומת N כלשהי יש בדיוק צאצא אחד, הצאצא בצבע אדום.
(אם הצאצא היה שחור, אז הצאצאים שלו גם כן שחורים (ריקים),ותנאי 4 לעיל נשבר.)
חלק מהמימושים דורשים מאפיין נוסף: 6. השורש הוא שחור.
מאפיין זה לעיתים מושמט מכיוון שצבע השורש תמיד יכול להשתנות מאדום לשחור אך לא תמיד להפך והשפעתו על ניתוח הסיבוכיות זניחה, אך מסבכת את ההסבר על "גלגול" בצורה משמעותית).
אילוצים אלו כופים הגבלה משמעותית על עצים אדומים שחורים: אורכו של המסלול הארוך ביותר מהשורש לכל אחד מן העלים הוא לכל היותר פעמיים אורכו של המסלול הקצר ביותר מהשורש לאחד העלים.
התוצאה היא שהעץ מספיק מאוזן כדי לשמור על סיבוכיות טובה של הפעולות השונות, מכיוון שפעולות אלה דורשות במקרה הגרוע ביותר זמן יחסי לגובה העץ, הגבלת גובה העץ מגבילה גם את סיבוכיות הפעולות.
על מנת לראות מדוע מאפיינים אלה מבטיחים הגדרה זו, מספיק להבחין בכך שאף מסלול לא יכול להכיל שני צמתים אדומים ברצף, לפי מאפיין מספר 4. המסלול הקצר ביותר מכיל צמתים שחורים בלבד והמסלול הארוך ביותר מכיל לסירוגין צמתים אדומים ושחורים.
בנוסף, כל המסלולים מהשורש לעלים מכילים מספר זהה של צמתים שחורים, לפי מאפיין מספר 5, ולכן אין מסלול הארוך פי שניים מאורכו של מסלול אחר.
בייצוגים רבים של עצים בתור מבני נתונים, לצומת יכול להיות בן אחד בלבד, ועלים תמיד מכילים מידע.
קיימת אפשרות לייצג עצים אדומים שחורים בפרדיגמה זו, אך היא משנה ומוסיפה מאפיינים שונים ומסבכת את האלגוריתם.
מסיבה זו אנו משתמשים בערך זה בעלים ריקים אשר מטרתם היא לסמן את "סוף" העץ, כפי שהראנו למעלה, ובצמתים בעלי שני בנים בלבד.
לעיתים, מנוסח מאפיין מספר 4 בצורה שקולה – שכל מסלול פשוט מהשורש לאחד העלים כולל מספר קבוע של צמתים שחורים – הוא הגובה השחור.
פעולת החיפוש (Search) מתבצעת בדיוק כמו בעץ חיפוש בינארי סטדנרטי בסבוכיות ואינה דורשת התאמות.
הכנסה (Insert), והסרה (Remove) של צמתים לעץ מתבצעות בדומה לעץ חיפוש בינארי בסבוכיות (ראה קוד בהמשך), ולאחר מכן יש לבצע "איזון" לעץ.
"איזון העץ" (rebalancing) : ביצוע החלפות צבע למספר צמתים, ולכל היותר 3 (2 להכנסה) פעולות רוטציה מתבצע בסיבוכיות במקרה הגרוע, אך במקרה הממוצע לוקח בלבד.
קיימים שני סוגים של רוטציה: רוטציה ימנית (Right-Rotate), ורוטציה שמאלית (Left-Rotate).
פעולות ההוצאה וההכנסה של צומת מבוצעות באמצעות החלפה של "עלה" בצומת אדומה חדשה, או הוצאה של צומת והחלפתה ב"עלה", פעולות אלו לעיתים גוררות מעבר על המאפינים של העץ.
לצורך איזונו ותיקונו יש לבצע מספר פעולות: הפעולות המובאות בהמשך כוללות 12 תתי-מקרים של העץ לאחר השינוי (6 עבור הוצאה, 6 עבור הכנסה), ראשית נגדיר 2 פעולות עזר שנשתמש בהן בהמשך.
פעולת הרוטציה היא פעולת עזר, ניתן להבינה באמצעות הדוגמה הבאה:
נתון צומת אב N ולו שני בנים: L שמאלי, R ימני.
ל־L ישנם שני בנים: S שמאלי, Y ימני.
לאחר רוטציה ימנית L יהפוך להיות האב, S יישאר בנו השמאלי, N יהה בנו הימיני ול N יהיו שני בנים: R ימני, Y שמאלי.
פעולת הרוטציה השמאלית היא הופכית לימנית, למשל בדוגמה לעיל, היא תחזיר את המצב לקדמותו בדיוק.
פעולת החלפת הצבע היא אלמנטרית- מחליפה את הצבע של הצומת הספציפי (מאדום לשחור, ולהפך).
הכנסת איבר חדש לעץ אדום-שחור
הכנסת איבר חדש לעץ מתבצעת במיקום המתאים לפי עץ חיפוש בינארי, האיבר החדש מחליף "עלה ריק שחור" וצבאו אדום.(פעולת ההכנסה כוללת את העץ כולו, העלה החדש, האב של העלה החדש (יכול להיות ריק), והאם הוא יהה בן ימני/שמאלי.)
לאחר מכן מתבצע האיזון בהתאם לצורך, לקיומם וצבעם של האב, הסב, והדוד של הצומת החדש.
(פירוט 6 הפעולות יפורט בטבלה בהמשך)
הכנסת איבר חדש X לעץ – על פי אלגוריתם סטנדרטי של הכנסה לעץ חיפוש בינארי (X יהפוך לעלה חדש של העץ).
כל עוד X אינו השורש וגם אביו של X אדום בצע:
צביעת הדוד של X בשחור.
צביעת האבא של X בשחור.
צביעת הסבא של X באדום.
כעת X מצביע לסבא של X.
אחרת (הדוד שחור או לא קיים) בצע:
אם האבא של X הוא בן שמאלי בצע:
אם X הוא בן ימני בצע:
כעת X מצביע לאבא של X.
צביעת אבא של X בשחור.
צביעת סבא של X באדום.
רוטציה ימנית לסבא של X.
אחרת (אבא של X בן ימני) בצע:
אם X הוא בן שמאלי בצע:
X מצביע לאבא של X.
רוטציה שמאלית לסבא של X.
אם לצומת שנמחקת יש בדיוק 2 ילדים : ניתן להחליף את הצומת עם הצומת היורשת שלו (הבן השמאלי ביותר, בתת-עץ הימני), ולמחוק אותה.
[מכיוון שהיורש הוא שמאלי ביותר,אין לו בנים שמאלים]
אם לצומת שנמחקת יש בדיוק ילד אחד, ניתן לצבוע את הבן בשחור, ולשים את הבן במקום הצומת שנמחקת.
[הילד חייב היה להיות אדום, והאב היה שחור לפי מאפין 3, ומאפין 5]
אם לצומת שנמחקת אין ילדים והוא היה השורש, מחק אותו ושים במקומו עלה ריק, העץ ריק.
אם לצומת שנמחקת אין ילדים והוא אדום, מחק אותו.
במקרה בו לצומת שנמחקת אין ילדים והיא שחורה, מחיקתו תגרום לחוסר-איזון בעץ ויש לתקן זאת באמצעות אחת משש הפעולות המפורטות בטבלה בהמשך.
שימושים ויישומים ודמיון לעצים אחרים
מבנה נתונים מסוג עץ אדום שחור משמש בדרך כלל למימוש מילון.
עפרים (בעפרית: Qafár, באמהרית: አፋር) הם קבוצה אתנית המתגוררת בעיקר במדבר דנקיל במחוז עפר באתיופיה, במחוז דרום הים האדום באריתריאה ובמדינת ג'יבוטי.
הם נקראים גם בשם דנקילים, במיוחד אלו החיים בצפון, בעוד שהדרומיים נקראים אדאלים, על שם סולטנות אדאל ששכנה באזור.
העפרים מהווים שליש מאוכלוסיית ג'יבוטי, באריתריאה הם חיים בעיקר בדרום-מזרח המדינה ובאתיופיה מוכרים כמחלקה אתנית אוטונומית.
שפתם, העפרית, היא מענף השפות הכושיות במשפחת השפות האפרו-אסיאתיות.
האבות הקדמונים של העפרים עיבדו שטחים חקלאים וניהלו משק חי ברמה האתיופית בשנת 1000 לפנה"ס.
זמן קצר לאחר מכן, הם החלו במעבר הדרגתי לסגנון חיים נוודי ונדדו לאזור זה.
מאז הם היו מעורבים בהרבה סכסוכים על הגבול עם שבטים ועמים אחרים.
האזכור הקדום ביותר ששרד, הנוגע לעפרים, הוא מהמאה ה-13 והוא נמצא ברשימותיו של הסופר הערבי איבן סעיד.
הוא כתב כי הם חיו מאזור הנמל של סואקין ועד דרומה עד העיר מאנדאב, שליד זילע.
העפרים מוזכרים גם בכתבים אתיופים.
האזכור הראשון מיוחס לקיסר עמדה ציון שניהל מערכה צבאית באזור נהר האווש, אחרי כן הם מוזכרים בכך שעזרו לקיסר באדה מאריאם כאשר הוא ניהל קמפיין צבאי כנגד שכניהם הדובאים.
במאה ה-17 הוקמה סולטנות עצמאית של העפרים- סולטנות עפר.
ב-1975 החזית לשחרור עפר התחילה באתיופיה מרד שלא הצליח והונהג על ידי הסולטאן המקומי.
הדרג בסופו של דבר הקים את האזור האוטונומי של עסב (שכלל את כל שטחי העפרים באתיופיה ואריתריאה), אף על פי שהמרד המשיך עד תחילת שנת 1990. בג'יבוטי, התקוממה תנועה דומה בשנות ה-80 של המאה ה-20, ולבסוף הסתיימה בסיום מלחמת האזרחים הג'יבוטית שנתגלעה בין העפרים והעיסה.
אף על פי שכמה מהעפרים היגרו לערים ואימצו דרך חיים "מערבית", תמיד היו רובם נוודים וחקלאים, המגדלים עיזים, כבשים ובקר במדבר.
במשך העונות היבשות הם נודדים לנהר אווש, שם הם חונים וממקמים את אוהליהם.
גמלים הם אמצעי התחבורה השכיח ביותר באזור.
ה'באררה' (מחנה), מורכב משנים או שלושה אוהלים, והוא בתחום אחריותן של הנשים.
העפרים מאורגנים במשפחות, שבטים, וקבוצות מעמדיות - אסאימארה (האדומים) הדומיננטיים באופן פוליטי, והאדוימארה (הלבנים) המהווים את המעמד הנמוך.
מילה מתבצעת גם לגברים וגם לנשים.
העפרים בוחרים את בת זוגם, לרוב ובעדיפות מתוך אותו שבט.
האידיאל הוא נישואין בין קרובי משפחה, כגון בני דודים.
העפרים אימצו את האסלאם בעקבות המגע עם הערבים.
לאמונתם באסלאם אופי מיוחד, הכולל בתוכו אלמנטים רבים מדתם הקודמת.
עץ או פלסטיין הוא סרט תיעודי ישראלי, שהופק בשנת 1962 ובוים בידי נתן אקסלרוד, יואל זילברג ואורי זוהר.
הסרט הופק על ידי "סרטי כרמל" וא.
דשא (פשנל), והתבסס על מהדורותיו של "יומן כרמל" - יומן חדשות שבועי, משנות ה-30 ועד ליום העצמאות הראשון בשנת 1949. בחירת הקטעים לסרט הציגה את תולדות היישוב בגישה הומוריסטית-נוסטלגית.
קטעי הקריינות בסרט נכתבו על ידי חיים חפר והוקראו על ידי חיים טופול.
את הפסקול כתב המנצח והמעבד יצחק גרציאני.
שמו של הסרט נובע מהשם ששימש בתקופת המנדט, שבה עוסק הסרט, להטלת מטבע.
הקרנת עץ או פלסטיין חנכה את סינמטק תל אביב והסרט הוא הראשון שהוקרן עם פתיחת שערי הסינמטק ביום 12.5.1973.
עפרוניים (שם מדעי: Alaudidae) היא משפחה של ציפורי שיר.
כל מיני העפרוניים מצויים בעולם הישן, וגם בצפון אוסטרליה ובמזרחה.
רק מין אחד, צחיחנית חרמון, נפוץ ביבשת אמריקה.
אזורי הגידול משתנים במידה רבה, אך מינים רבים חיים באזורים יבשים יחסית.
רוב המינים בונים את קניהם על הקרקע.
צבעיהם – בגוונים של אפור, חום וצהוב – דהויים בדרך כלל ומשמשים כצבעי הסוואה מפני טורפים, בעיקר כשהם מקננים על הקרקע.
לעפרוניים יש קריאות משוכללות יותר מרוב הציפורים האחרות, והם שרים בראוותנות בזמן תעופה.
באמצעות שירה זו הזכרים מושכים נקבות וגם מגינים על הטריטוריה שלהם.
השירה המיוחדת של העפרוניים, בשילוב התפשטותם באזורים מאוכלסים בני אדם, תרמה רבות לחשיבותם בספרות ובמוזיקה.
סוג ומין יחיד עפרוני עב-מקור (Ramphocoris clotbey)
סוג ומין יחיד חוגת עצים (Lullula arborea)
עפרת ברזל היא עפרה הכוללת סלעים ומינרלים מהם ניתן להפיק באופן כלכלי ברזל מתכתי.
העפרות עשירות בדרך כלל בתחמוצות ברזל וצבעיהן מגוונים, החל מאפור כהה, צהוב עז, סגול, וכלה באדום חלודה.
הברזל עצמו נמצא בדרך כלל בצורות המינרליות: מגנטיט (Fe3O4), המטיט (Fe2O3), גתיט (FeOOH), לימוניט (FeO(OH)·nH2O), או סידריט (FeCO3).
המטיט אף ידוע כ"עפרת ברזל טבעית": שריד מימי העבר, אז חלק ממכרות ההמטיט הכילו עד 66% ברזל וניתן היה להזין את העפרה ישירות לכבשן כדי להפיק ברזל.
עפרת ברזל היא חומר הגלם להפקת ברזל, שהוא בתורו חומר הגלם העיקרי להפקת פלדה.
98% מעפרת הברזל אותה כורים בעולם משמשת להפקת פלדה.
הפלדה מהווה כ-95% מכלל שוק המתכות העולמי.
השימוש העיקרי בפלדה הוא בענף הבניה, בתעשיית הספנות, בתעשיית הרכב ובייצור מכונות.
כתוצאה מכך, למחירי עפרת הברזל השפעה נרחבת, ישירה ועקיפה, על מדדי הכלכלה בעולם.
+הערכת תפוקת עפרת הברזל במיליוני טון לשנת 2007
<small>על פי השירות הגאולוגי האמריקאי מדינה תפוקה סין 707 ברזיל 354 אוסטרליה 299 הודו 180 רוסיה 105 אוקראינה 78 ארצות הברית 53 דרום אפריקה 42 קנדה 33 איראן 32 שוודיה 25 קזחסטן 24 ונצואלה 23 מקסיקו 13 מאוריטניה 12 מדינות אחרות 50 סה"כ בעולם 2,030
סלעים עשירים בברזל נפוצים בכל העולם, אולם במספר מצומצם יחסית של מדינות נמצאו מרבצים של עפרת ברזל שמהן הפקת ברזל כדאית מבחינה כלכלית.
המגבלה העיקרית לכדאיות הכלכלית שבהפקת ברזל ממרבץ עפרת ברזל אינו בהכרח איכות העפרה או גודל המרבץ, אלא במיקום המרבץ ביחס לשוק, עלות שינוע העפרה מן המכרה אל השוק, עלויות האנרגיה הדרושות להפקה, ושיקולים דומים.
כריית עפרת ברזל היא עסק הפועל בהיקף ענק ובמתח רווחים נמוך.
כריית עפרת ברזל דורשת השקעות גדולות בתשתיות, כגון סלילת מסילות ברזל לצורך שינוע העפרה מן המכרה למזח שם תועמס על אוניית צובר.
מסיבות אלה כריית עפרת ברזל נעשית בידי מספר מצומצם יחסית של חברות.
התפוקה העולמית השנתית הממוצעת היא כמיליארד טונות של עפרת ברזל בשנה.
יצרנית עפרת הברזל הגדולה ביותר בעולם היא חברת המכרות הברזילאית Vale, ואחריה החברות הבריטיות-אוסטרליות BHP Billiton, ו-Rio Tinto Group.
נפח המסחר הימי בעפרת ברזל - כמויות עפרת הברזל המשונעות באוניות צובר ממדינת המכרה למדינות אחרות - הייתה בהיקף של 849 מיליון טון בשנת 2004. אוסטרליה וברזיל שולטות בתחום המסחר הימי בעפרת ברזל, ומחזיקות בנתח של 72% מן השוק העולמי.
שלוש החברות הגדולות בעולם שולטות יחד ב-66% מן השוק העולמי.
הצרכניות העיקריות של עפרת ברזל בעולם הן סין, יפן, קוריאה הדרומית, ארצות הברית, והאיחוד האירופי.
סין היא המפיקה, הצרכנית, והיבואנית הגדולה בעולם של עפרת ברזל ואף המפיקה הגדולה בעולם של ברזל גולמי.
בשנת 2004 יעדו של רוב הסחר הימי בעפרת ברזל (52%) היה סין.
אף שסין היא המפיקה הגדולה בעולם של עפרת ברזל, היא ממשיכה לרכוש, ולהוביל לסין בדרך הים, עפרת ברזל איכותית יותר ממכרות באוסטרליה.
החל משנות ה-60 נקבעו מחירי עפרת הברזל בשוק העולמי בשיטה המכונה "שיטת קנה מידה" , בין החברות המובילות בכריית עפרת ברזל לבין יצרני הברזל הגולמי.
באופן מסורתי, קבעה העסקה הראשונה בין שני צדדים אלה קנה מידה שעל פיו התנהלה כל התעשייה לאורך כל השנה.
שיטה זו החזיקה מעמד עד 2008, אז כרתו שלוש החברות המפיקות השולטות בשוק (Vale, Rio Tinto, BHP Billiton) הסכם עם יפן להוזלת מחירי העפרה ב-33%, אולם סין דחתה את "אמת המידה" שנקבעה ודרשה הפחתה גדולה יותר במחיר.
במקביל גילתה BHP Billiton, אשר ניסתה לבטל את שיטת אמת המידה, כי כשליש מלקוחותיה רוכשים ממנה עפרת ברזל במחירי השוק.
עפרת ברזל אף נסחרת בשוק הסחורות העולמי, אולם באופן מסורתי היקפו של שוק זה היה קטן בהרבה מגודל העסקאות שנכרתו בין שלוש חברות הכרייה הגדולות ליצרני הברזל, על פי מחירי אמת מידה.
שיטת קביעת המחיר המסורתית של עפרת הברזל היא בעייתית כיוון שכאשר מחירי העפרה בשוק הסחורות גבוהים יותר ממחירי אמת המידה, הרי שחברות הכרייה מפסידות הכנסות שהיו באות להן לו היו מוכרות את העפרה בשוק.
מנגד, כאשר מחירי מחירי העפרה בשוק נמוכים ממחירי אמת המידה, חלק מיצרני הברזל מעדיפים להסתיר מחברות הכרייה כי הם רוכשים את העפרה בשוק הסחורות.
נכון לשלהי העשור הראשון של המאה ה-21 קיימת דעיכה הדרגתית של מספר העסקאות בתחום זה הנעשות על פי מחירי אמת מידה, ועליה בעסקאות הנעשות בשוק הסחורות.
ככל שגדל היקף העסקאות בתחום זה, הנעשות במסגרת שוק הסחורות, משתכללים אף המכשירים הפיננסיים הנמצאים בשימוש בשוק זה.
עם זאת, במקרים מסוימים גבוה יותר מחיר ההובלה הימית של עפרת ברזל מערך העפרה.
מצב זה רלוונטי באופן מיוחד לעפרת הברזל המופקת בברזיל, אשר הובלתה לסין, הצרכנית המרכזית בשוק, יקרה הרבה יותר מהובלת עפרה מאוסטרליה.
מסיבה זו דרשו בעבר חברות הכרייה האוסטרליות מחירים גבוהים יותר עבור העפרה שהפיקו, כיוון שזול יותר להובילה ליצרני הברזל.
עלות המשלוח הזולה יחסית גורמת לניצול יתר של המכרות הפתוחים בגואה, אמנם אחוז הברזל באדמה נמוך יחסית אבל הקרבה לסין מפצה על כך.
עתודות עפרת ברזל בעולם, בעשור הראשון של המאה ה-21, הן עצומות.
אולם יש הטוענים כי העלייה המהירה בצריכת ברזל ומוצריו בעולם עלולה בעתיד לגרום אף להצטמצמות עתודות אלה.
כך למשל, מומחה ממכון וורלדוואטש (Worldwatch Institute), ארגון אמריקאי העוסק באיכות הסביבה בעולם, טען בספר שפרסם בשנת 2006 כי עתודות עפרת הברזל בעולם עלולות להיגמר בתוך 64 שנים, אף בהנחה שמרנית של גידול שנתי בשיעור 2% בצריכה העולמית של ברזל.
עתודות עפרת הברזל הגדולות ביותר בעולם נמצאות כיום בגינאה.
עפרה זו נחשבת איכותית במיוחד, משום שרובה מכילה מעל ל-65% ברזל.
מרבצי עפרת הברזל בגינאה נמצאים בעיקר בדרום ומרכז המדינה: סימנדו, זוגוטה, ונימבה בדרום-מזרח, וקאליה במרכז המדינה.
במדעי המחשב, עץ B הוא מבנה נתונים בצורת עץ, הכללה של עץ חיפוש בינארי, בכך שלכל צומת יכולים להיות יותר מ-2 בנים.
עץ B שומר מידע ממוין (לפי מפתח) ומאפשר חיפוש, גישה סדרתית, הוספת איברים ומחיקתם בסיבוכיות לוגרתמית.
עץ B מסדר m מקיים את התכונות הבאות:
לכל צומת יש לכל היותר m ילדים.
לכל צומת שאינו עלה ואינו השורש, יש לפחות ⌈m/2⌉ ילדים.
אם השורש אינו עלה, יש לו לפחות 2 ילדים.
צומת פנימי עם k ילדים מכיל בדיוק k-1 מפתחות.
להבדיל מעצי חיפוש מאוזנים, עץ B מיועד לעבודה יעילה במערכות שקוראות וכותבות בלוקים גדולים של מידע.
השימוש בו שכיח במסדי נתונים ובמערכות קבצים.
עץ +B הוא וריאנט של עץ B.
ההבדל בין עץ B לבין עץ +B הוא בכך שבעץ +B המפתחות בצמתים הם העתק של המפתחות בעלים, ואילו בעץ B כל איבר נמצא בצומת פנימי או בעלה.
בנוסף לכך בעץ +B יש בדרך כלל רשימה המקשרת בין העלים לאפשר מעבר סדרתי מהיר.
עִפְרִית הוא שד בפולקלור הערבי.
העפרית מוזכרים בקוראן בסורת א-נַמְל.
העפרית הם יצורים מכונפים עצומים, עשויים מאש, בדמות זכר או נקבה, שחיים במעבה האדמה.
הם ידועים במיוחד בשל כוחם הרב וערמומיותם.
העפרית בדרך כלל נישאים זה לזה, אף על פי שהם עשויים גם להתחתן עם בני אנוש.
כדי להשפיע עליהם או לפגוע בהם, בני האנוש צריכים להשתמש בכשפים.
העפרית עשויים להיות טובי-לב, אך לרוב הם מתוארים כיצורים מרושעים וחסרי רחמים.
לעפרית יש הופעות ואזכורים רבים בספרות, בתוכניות טלוויזיה ובמשחקי וידאו.
בין האזכורים התרבותיים הידועים - מוזכר לעיתים קרובות בסיפורי אלף לילה ולילה, בספרו של ניל גיימן אלים אמריקאים, בסדרת הספרים דברי ימי נרניה של ק.ס.
עפרית (Qafár af) היא שפה ממשפחת השפות הכושיות המזרחיות המדוברת באתיופיה, באריתריאה ובג'יבוטי.
בשפה יש כ-1.5 מיליון דוברים, בני אומת העפרים.
באריתריאה מוכרת השפה כאחת מתשע השפות הרשמיות, אם כי התיגרינית והערבית נמצאות בשימוש נרחב בהרבה במסמכים רשמיים.
הרדיו הלאומי משדר שידורים יומיים בעפרית, והחוקה האריתראית תורגמה לשפה זו.
בחבל עפר שבאתיופיה השפה הרשמית היא האמהרית, אך בשל ריבוי דוברי העפרית ישנם בתי ספר המלמדים בשפה זו.
+פונמות בעפרית סדקי לועי וילוני חכי כפוף מכתשי שפתי(־שִנִּי) אפיnm סותםɡkɖdtb חוכך hʕħ s f מקורב(צדי)wjl מקישɾ
במדעי המחשב, עץ 2-3 הוא מבנה נתונים מסוג עץ חיפוש מאוזן.
כל צומת אב (צומת פנימי) מכיל מפתח אחד ושני בנים (צומת-2, איור 1), או שני מפתחות ושלושה בנים (צומת-3, איור 2).
כל הצמתים ללא בנים (צמתים חיצוניים או עלים), נמצאים באותו העומק (ראה איור 3).
כמו כן, עץ ריק ועץ עם עלה אחד הם עצי 2-3.
לעץ 2-3 מספר גרסאות בעלות תכונות שונות מעט, אשר נבחרות על פי התאמתן לשימוש מסוים.
בגרסה המתוארת כאן, הרשומות (המכילות מפתח וערך הקשור אליו) נמצאות רק בעלים, בעוד הצמתים הפנימיים מכילים מידע לארגון בלבד.
הערך- מכיל תמיד את המפתח המקסימלי המצוי בתת-העץ השמאלי המחובר ל-.
תת-העץ המרכזי המחובר ל- מכיל מפתחות הגדולים מ-.
בצומת-3, הערך מכיל את המפתח המקסימלי המצוי בתת-העץ המרכזי המחובר ל-.
בצומת-3, תת-העץ הימני המחובר ל- מכיל מפתחות הגדולים מ-.
בעץ 2-3 עם רמות, יש בין ל- עלים (כאשר העץ מורכב מצמתים מסוג צומת-2 בלבד, או צומת-3 בלבד, בהתאמה).
במילים אחרות, על מנת ליצג רשומות, יש צורך בעץ עם לפחות רמות, אך לא יותר מ- רמות.
משמע, כל המסלולים בעץ הם באורך .
מבנהו של עץ 2-3 מבטיח חיפוש, הכנסה, והוצאת מפתח (המיצג רשומה) בסיבוכיות במקרה הגרוע ביותר, כאשר הוא מספר המפתחות (רשומות) בעץ.
עץ 2-3 פותח על ידי ג'ון הופקרופט בשנת 1970, ושייך למשפחה של עצי חיפוש המאזנים את עצמם.
בעצים מסוג זה פעולות הכנסת מפתח והוצאת מפתח עשויות לגרום שינויים במבנה העץ, לשם שימור איזונו.
דוגמאות נוספות לעצי חיפוש המאזנים את עצמם הן: עץ AVL, עץ אדום שחור, עץ 2-3-4, ועץ B.
חיפוש רשומה שלה מפתח מתקדם במורד העץ כאשר בכל צומת:
אם והצומת הוא צומת-2, ממשיכים בתת-העץ הימני.
אם והצומת הוא צומת-3, אזי אם ממשיכים בתת-העץ האמצעי, אחרת ממשיכים בתת-העץ הימני.
בסופו של דבר מגיעים לעלה.
אם הרשומה נמצאת בעץ, אזי העלה יכיל את המפתח ואת הרשומה השייכת לו (ראה איור 4).
אם רוצים רק לוודא את הימצאות הרשומה, ולא לגשת אליה, אפשר לעצור בכל שלב בו או .
אם העץ הוא ריק, מוסיפים את הרשומה בעלה, במקומו של השורש.
אם העץ מכיל עלה אחד, מוסיפים צומת-2 כשורש, ואת שני העלים כבניו (ראה איור 5).
בעץ עם צמתים פנימיים, הכנסת רשומה חדשה עם מפתח מתקדמת כמו חיפוש, עד אשר מגיעים ל-, הצומת הפנימי האחרון לפני העלים.
אם צומת הוא צומת-2, מוסיפים לו עוד בן (עלה) והופכים אותו לצומת-3, כאשר העלים ממוינים והערכים מעודכנים כנדרש.
אם הוא הערך הגדול מבין שלושת הבנים, יש לעדכן גם את הערכים או של האבות של הצומת (ראה איור 6).
אם צומת הוא צומת-3, מרחיבים אותו זמנית לצומת-4 (האסור בעץ 2-3), ומוסיפים לו עלה במקום המתאים.
על מנת לשמור על מבנה העץ, מפצלים את צומת-4 שנוצר לשני צמתים-2, ו-.
את זוג המפתחות הנמוכים מציבים בצומת השמאלי , ואת זוג המפתחות הגבוהים מציבים בצומת הימני .
כעת מוסיפים את הצומת החדש שנוסף () לאב של צומת המקורי.
תהליך זה זהה להוספת עלה לצומת פנימי - אם צומת הוא צומת-2 הוא יהפוך לצומת-3, ואם הוא צומת-3 הוא יעבור הרחבה לצומת-4 ופיצול.
כך ממשיכים בסדרה של הרחבות ופיצולים עד אשר מגיעים לצומת-2 או מפצלים את השורש (ראה איור 7).
פיצול השורש הוא מקרה מיוחד, אשר גורם ליצירת שורש חדש מסוג צומת-2 אשר בניו הם שני הצמתים שאליהם פוצל השורש הקודם.
באופן זה גדל העומק של עץ 2-3.
הוצאת רשומה עם מפתח מתקדמת כמו חיפוש, עד אשר מגיעים ל-, הצומת הפנימי האחרון לפני העלים.
אם צומת הוא צומת-3, מסירים את הבן עם מפתח , והופכים אותו לצומת-2. אם הבן שהוסר היה הגדול משלושת הבנים, יש לעדכן גם את הערכים או של האבות של הצומת (ראה איור 8).
אם צומת הוא צומת-2, מסירים את הבן עם מפתח , והופכים אותו זמנית לצומת-1, האסור בעץ 2-3. על מנת לשמר את מבנה העץ מבצעים את אחת מפעולות המיזוג הבאות:
אם לצומת יש אח מימין או משמאל שלו 3 בנים, מעבירים את אחד הבנים של לצומת , ומעדכנים את הערכים או של האבות של הצומת במידת הצורך.
אם לצומת יש רק אחים מסוג צומת-2, אזי מסירים את הבן היחיד של , מעבירים אותו לאחד מהאחים של , ומוחקים את צומת מהאב שלו .
אם האב נותר צומת-2, התהליך הסתיים.
אם האב נותר צומת-1 (האסור בעץ 2-3), חוזרים על תהליך המיזוג כפי שתואר לעיל (ראה איור 9).
אם בסוף התהליך השורש נותר צומת-1, מוחקים את השורש והופכים את בנו היחיד לשורש החדש.
באופן זה קטן עומקו של עץ 2-3.
עץ 2-3 ניתן לייצג גם באמצעות צמתים מסוג צומת-2 בלבד, כאשר מוסיפים לכל קשת עוד סיבית אשר מסמנת האם הקשת היא קשת אופקית או אנכית.
כפי שניתן לראות באיור 10, ניתן לפצל כל צומת-3 לשני צמתים מסוג צומת 2, המחוברים בקשת אופקית, אותה נהוג לסמן באדום.
שני הייצוגים האפשריים הם שקולים.
העץ הבינארי המתקבל מהמרת עץ 2-3 באופן זה (ראה איור 11), הוא עץ מאוזן, במובן הבא:
העץ הוא "מאוזן שחור", כלומר כל המסלולים בין השורש לעלים עוברים דרך אותו מספר קשתות שחורות.
תכונה זו מתקיימת מכיוון שהקשתות השחורות הן הקשתות המקוריות של עץ 2-3, שהוא מאוזן באופן מושלם.
המסלול הארוך ביותר מהשורש לעלה כלשהו, ארוך לכל היותר פי שניים מהמסלול הקצר ביותר מהשורש לעלה כלשהו.
מצב זה עשוי להתקבל כאשר בעץ 2-3 עם שורש מסוג צומת-3, תת-העץ הימני מורכב רק מצמתים מסוג צומת-3, בעוד תת-העץ השמאלי מורכב מצמתים מסוג צומת-2. מסלול אחד לפחות בתת-העץ הימני יהיה מורכב מקשת אדומה ושחורה לסירוגין, בעוד בתת-העץ השמאלי כל המסלולים שחורים.
מתברר שפעולות האיזון המתבצעות בעץ 2-3 בעת הכנסה והוצאה של מפתח (הרחבה ופיצול, מחיקה ומיזוג), מתבטאות ביצוג כעץ בינארי המתקבל לאחר המרה, כפעולות דומות לפעולות האיזון בעץ AVL (סיבוב העץ).
מכיוון שכך, גם ביצוג כעץ בינארי של עץ 2-3 פעולות החיפוש, ההכנסה, וההוצאה של מפתח מתבצעות בסיבוכיות במקרה הגרוע ביותר.
היצוג כעץ בינארי של עץ 2-3 היווה את הבסיס לפיתוח עץ אדום שחור, שהוא עץ החיפוש הבינארי המאוזן הפופולרי ביותר במימושים מעשיים.
כאמור לעץ 2-3 מספר אפשרויות ליחוס הרשומות לצמתים, הנבחרות לפי התאמתן לשימוש מסוים.
לדוגמה, בגרסה אחת של עץ 2-3 הרשומות נשמרות גם בצמתים פנימיים וגם בעלים, ללא שכפול.
באופן זה מספר הצמתים בעץ זהה למספר הרשומות, בניגוד לגרסה המתוארת לעיל, בה נשמרות הרשומות רק בעלים.
למרות הבדלים אלה, פעולות האיזון בהכנסת מפתח (הרחבה ופיצול) והוצאת מפתח (מחיקה ומיזוג) זהות למעשה בכל הגרסאות.
במדעי המחשב, עץ Splay הוא מבנה נתונים של עץ חיפוש בינארי לא בהכרח מאוזן בעל התכונה המאפשרת גישה חוזרת מהירה לאיברים אליהם בוצעה גישה לאחרונה.
הוא מאפשר פעולות בסיסיות כגון הכנסה, חיפוש והסרה של איברים בסיבוכיות זמן של (בניתוח לשיעורין).
עבור פעולות לא אקראיות רבות, עץ Splay מתגלה כיעיל יותר מעצי חיפוש אחרים, אפילו כאשר תבנית רצף הפעולות המסוימת אינה ידועה מראש.
עץ ה-Splay הומצא על ידי דניאל סליטור ורוברט טרג'אן ב-1985.
בעץ Splay, לכל הפעולות הרגילות שניתן לבצע על עץ חיפוש בינארי מתווספת פעולה בסיסית נוספת הנקראת splaying.
ביצוע splaying לעץ עבור איבר מסוים פירושו ארגון מחדש של העץ כך שהאיבר ימצא בשורשו של העץ.
דרך אחת לבצע זאת היא ראשית על ידי ביצוע של חיפוש בינארי רגיל של האיבר בעץ ולאחר מכן להשתמש בפעולות סיבוב בעץ, בדומה לפעולות הסיבוב המבוצעות בעץ AVL, כדי להביא את האיבר אל שורש העץ.
לחלופין, אלגוריתם top- down יכול לשלב את פעולת החיפוש ופעולת הסידור לכדי שלב ביצוע אחד.
במדעי המחשב, עץ 2-3-4 הוא מבנה נתונים מסוג עץ חיפוש מאוזן.
כל צומת עם בנים (צומת פנימי) מכיל מפתח אחד ושני בנים (צומת-2, איור 1), או שני מפתחות ושלושה בנים (צומת-3, איור 2), או שלושה מפתחות וארבעה בנים (צומת-4, איור 3).
לכל הצמתים ללא בנים (צמתים חיצוניים או עלים), אותו העומק.
בעלים מאוכסנים אחד, שניים או שלושה מפתחות.
בגרסה המתוארת כאן , גם הצמתים הפנימיים וגם העלים מכילים רשומות, כאשר כל רשומה מיוצגת על ידי מפתח, ואין חפיפה בין המפתחות שבעלים ובצמתים הפנימיים.
המפתחות המאוכסנים בצומת פנימי מגדירים את תחום המפתחות המאוחסן בכל תת-עץ המחובר לאותו צומת.
תת-העץ המחובר לבן מכיל מפתחות הקטנים מ- .
תת-העץ המחובר לבן מכיל מפתחות הגדולים מ- .
תת-העץ המחובר לבן מכיל מפתחות הגדולים מ- וקטנים מ- .
בעץ 2-3-4 עם רמות, יש בין ל- מפתחות (כאשר העץ מורכב מצמתים מסוג צומת-2 בלבד, או צומת-4 בלבד, בהתאמה).
מבנהו של עץ 2-3-4 מבטיח חיפוש, הכנסה, והוצאת מפתח (המיצג רשומה) בסיבוכיות במקרה הגרוע ביותר, כאשר הוא מספר המפתחות (רשומות) בעץ.
עץ 2-3-4 שייך למשפחה של עצי חיפוש המאזנים את עצמם.
דוגמאות נוספות לעצי חיפוש המאזנים את עצמם הן: עץ AVL, עץ 2-3, עץ אדום שחור, ועץ B.
חיפוש רשומה שלה מפתח מתחיל בשורש ומתקדם במורד העץ כאשר בכל צומת:
אם שווה לאחד המפתחות אזי נמצאה הרשומה.
אחרת, ממשיכים בתת-העץ אשר תחום המפתחות בו מכיל את מכיל את המפתח .
לדוגמה, בצומת- 4 שבאיור 3:
בסופו של דבר, או שהמפתח נמצא בצומת פנימי, או שמגיעים לעלה.
אם הרשומה נמצאת בעץ, אזי העלה יכיל את המפתח ואת הרשומה השייכת לו .
הכנסת מפתח לעץ ניתנת לביצוע באחת משתי שיטות עיקריות.
בשתי השיטות, הכנסת מפתח חדש לעץ 2-3-4 מתחילה כמו חיפוש, בו מתקדמים במורד העץ עד אשר מגיעים לעלה בו מסתיים חיפוש כושל.
אם העלה הוא צומת-2 או צומת-3, מוסיפים לו מפתח נוסף במקום המתאים והופכים אותו לצומת-3 או צומת-4, בהתאמה .
השיטות נבדלות ביניהן בדרך שבה הן מתמודדות עם הוספת מפתח לצומת-4.
בשני המקרים, הפעולה הבסיסית הנדרשת לפני ההוספה היא פיצול צומת-4 לשלושה צמתים מסוג צומת-2, כאשר :
המפתח האמצעי נמצא בצומת העליון
הבן השמאלי מכיל את המפתח הקטן ואת שני תתי העץ המחוברים ל-
הבן הימני מכיל את המפתח הגדול ואת שני תתי העץ המחוברים ל-
שיטה 1 - פיצול מלמטה למעלה
כאשר העלה שנמצא הוא צומת-4, מפצלים אותו לפני הוספה לשלושה צמתים מסוג צומת-2, על ידי העלאת המפתח המרכזי () לצומת העליון (איור 7).
לאחר מכן מוסיפים את המפתח לאחד מבניו של , העלים החדשים אשר מכילים את המפתחות בהתאמה (איור 8).
על מנת לשמור על מבנה העץ אשר דורש עומק זהה לכל העלים, יש להוסיף את הצומת לאב של הצומת המקורי .
אם האב הוא צומת-2 או צומת-3, התהליך הסתיים, והאב הופך לצומת-3 או צומת-4, בהתאמה.
אולם אם הוא צומת-4, נדרש לפצל גם אותו לפני ההוספה, ולהוסיף את לאחד מבניו (איור 9).
תהליך זה של פיצול והוספה עשוי להמשיך להתרחש בדרך למעלה מן העלה לכיוון השורש (ומכאן השם: פיצול מלמטה למעלה), עד אשר מגיעים לצומת שאינו צומת-4, או שמפצלים את השורש (איור 10).
פיצול השורש הוא מקרה מיוחד, אשר גורם ליצירת שורש חדש מסוג צומת-2 אשר בניו הם שני צמתים מסוג צומת-2. באופן זה גדל העומק של עץ 2-3-4.
שיטה 2 - פיצול מלמעלה למטה
גם בשיטה זו, הכנסת מפתח חדש מתחילה כמו חיפוש, בו מתקדמים במורד העץ עד אשר מגיעים לעלה בו מסתיים חיפוש כושל.
אולם בניגוד לשיטה המתוארת לעיל, מוודאים שכאשר מגיעים לעלה מסוג צומת-4, ניתן יהיה לפצל אותו לשלושה צמתים כמתואר לעיל, ולמזג את הצומת העליון אל תוך האב , מבלי שיהיה צורך לפצל את .
את זאת משיגים על ידי כך שמפצלים כל צומת-4 בו נתקלים במהלך החיפוש במורד העץ, החל מהשורש (ומכאן השם: פיצול מלמעלה למטה, איורים 11-13).
כאשר מפצלים צומת פנימי באופן זה, אין צורך לדאוג לאביו, כיוון שמובטח לנו שאינו צומת-4. מכיוון שכך, תמיד נוכל למזג את הצומת העליון מבין שלושת הצמתים אל האב.
פיצול צומת אם כך, היא פעולה מקומית אשר אינה מתפשטת במעלה העץ.
באופן זה, הכנסת מפתח נעשית במעבר אחד החל מהשורש ועד העלה .
אם העלה הוא צומת-2 או צומת-3, מוסיפים לו את המפתח והתהליך הסתיים.
אם העלה הוא צומת-4, מפצלים אותו.
מכיוון שהאב אינו מסוג צומת-4 (אחרת היה מפוצל קודם לכן), הרי ניתן להוסיף לו את הצומת העליון מבין שלושת הצמתים שאליהם פוצל העלה, והתהליך הסתיים.
הוצאת מפתח מעץ 2-3-4 מתקדמת במורד העץ כמו חיפוש, עד אשר נמצא הצומת בו נמצא המפתח אותו רוצים להוציא.
אם המפתח נמצא בעלה, מוחקים אותו (איור 14).
אם העלה הוא מסוג צומת-3 או צומת-4, בכך הסתיים התהליך.
אולם אם העלה הוא מסוג צומת-2, הוא הופך לעלה ריק אשר מפר את תכונות העץ.
לשם שימור תכונות העץ מבצעים את פעולות השימור המתוארות בהמשך.
כל מפתח בצומת פנימי מצוי בין ערכי המפתחות של תת-עץ ימני (הגדולים ממנו) ותת עץ שמאלי (הקטנים ממנו), אשר ביניהם הוא מפריד.
על מנת להסירו עלינו למצוא לו מחליף.
הערך הגדול ביותר בתת-העץ השמאלי, אותו אפשר למצוא על ידי ירידה בבן הימני ביותר של כל צומת עד הגעה לעלה הימני ביותר בתת-העץ, או
הערך הקטן ביותר בתת-העץ הימני, אותו אפשר למצוא על ידי ירידה בבן השמאלי ביותר של כל צומת עד הגעה לעלה השמאלי ביותר בתת-העץ.
הוצאת מפתח מצומת פנימי מתבצעת באופן הבא (איור 15):
מצא מחליף למפתח , הצב אותו במקום , והסר אותו מהעלה שבו היה מוצב.
פעולה זו הסירה מפתח מעלה, ולכן שקולה למקרה הקודם.
שימור מבנה העץ לאחר הוצאה
לאחר הוצאת מפתח מעלה או מצומת פנימי , ייתכן וצומת זה יישאר ללא מפתחות כלל, וללא בנים (במקרה של עלה) או עם בן אחד (במקרה של צומת פנימי).
על מנת לשמר את מבנה העץ, מבצעים את סדרת הפעולות הבאות, החל מהעלה שהתרוקן.
אם לצומת יש מימין אח מסוג צומת-3 או צומת-4 (איור 16)
מוסיפים את המפתח המפריד בין ל- באב אל הצומת
מסירים את , המפתח הקטן ביותר של צומת ומכניסים אותו במקום המפתח של האב
מעבירים את הבן הראשון של צומת להיות הבן האחרון של צומת
אחרת, אם לצומת יש משמאל אח מסוג צומת-3 או צומת-4 (איור 17)
מסירים את , המפתח הגדול ביותר של צומת ומכניסים אותו במקום המפתח של האב
מעבירים את הבן האחרון ( או ) של צומת להיות הבן הראשון של צומת
אם לצומת אין אחים, מימין או משמאל, מסוג צומת-3 או צומת-4 (איור 18)
צור צומת חדש המכיל את המפתחות של צומת , המפתחות של אחד מאחיו מימין או משמאל, והמפתח המפריד בין לבין האח בצומת האב
הסר את המפתח מן האב , וחבר אל האב את הצומת החדש במקום שני הצמתים שיצרו אותו
אם הסרת המפתח מן האב גורמת לו להפוך לצומת ללא מפתחות, חזור על תהליך האיזון מחדש עם צומת זה.
מקרה מיוחד הוא כאשר השורש נותר צומת ריק עם בן אחד.
במקרה זה מסירים את השורש והופכים את בנו לשורש החדש (איור 19).
באופן זה קטן עומקו של עץ 2-3-4.
עץ 2-3-4 ניתן לייצג גם באמצעות צמתים מסוג צומת-2 בלבד, כאשר מוסיפים לכל קשת עוד סיבית אשר מסמנת האם הקשת היא קשת אופקית או אנכית.
כפי שניתן לראות באיור 20, ניתן לפצל כל צומת-3 לשני צמתים מסוג צומת 2, המחוברים בקשת אופקית, בעוד צומת-4 ניתן לפצל לשלושה צמתים מסוג צומת-2. את הקשתות האופקיות נהוג לסמן באדום.
העץ הבינארי המתקבל מהמרת עץ 2-3-4 באופן זה (איור 21), הוא עץ מאוזן, במובן הבא:
תכונה זו מתקיימת מכיוון שהקשתות השחורות הן הקשתות המקוריות של עץ 2-3-4, שהוא מאוזן באופן מושלם.
מצב זה עשוי להתקבל למשל, כאשר בעץ 2-3-4 עם שורש מסוג צומת-2, תת-העץ הימני מורכב רק מצמתים מסוג צומת-4, בעוד תת-העץ השמאלי מורכב מצמתים מסוג צומת-2. מסלול אחד לפחות בתת-העץ הימני יהיה מורכב מקשת אדומה ושחורה לסירוגין, בעוד בתת-העץ השמאלי כל המסלולים שחורים.
היצוג כעץ בינארי של עץ 2-3-4 היווה את הבסיס לפיתוח עץ אדום שחור, שהוא עץ החיפוש הבינארי המאוזן הפופולרי ביותר במימושים מעשיים.
פעולות האיזון המתבצעות בעץ 2-3-4 בעת הכנסה והוצאה של מפתח (הרחבה ופיצול, מחיקה ומיזוג), מתבטאות ביצוג כעץ בינארי המתקבל לאחר המרה, כפעולות דומות לפעולות האיזון בעץ אדום שחור.
מכיוון שכך, גם ביצוג כעץ בינארי של עץ 2-3-4 פעולות החיפוש, ההכנסה, וההוצאה של מפתח מתבצעות בסיבוכיות במקרה הגרוע ביותר.
עפרי כנעני (נולדה ב-11 במרץ 1975) היא אמנית ואשת חינוך ישראלית, אשר חיה בניו יורק.
היא עוסקת באמנות מבוססת זמן, הכוללת וידאו ארט ומיצגים ובנוסף במיצבים ובהדפס.
היא מלמדת בבית הספר לאמנות חזותית בניו יורק ובמחלקה לתרבות חזותית חומרית בבצלאל שבירושלים.
עבודותיה מתבססות לעיתים קרובות על מחקר ארכיוני וטקסטים קלאסיים וקאנוניים, ומערבות דימויים מן המוכן עם דימויים שיצרה כנעני בעצמה, יחד עם נראטיב שחלקו עובדתי וחלקו מומצא.
בעבודות ניתן למצוא תמות הקשורות לשפה, טכנולוגיה, מיתולוגיות שונות, וכן פמיניזם.
עבודותיה הוצגו בין השאר במוזיאון המטרופוליטן, במומה פי אס1 ובמוזיאון ישראל.
עפרי כנעני נולדה בישראל, נכדתו של הפסל יחיאל שמי, בתה של האמנית והכוריאוגרפית יעל כנעני, ואחות בכורה לאמנית אביטל כנעני.
היא בעלת תואר ראשון באמנות וחינוך מהמדרשה לאמנות, מכללת בית ברל ותואר שני באמנות ממכללת האנטר בניו יורק.
התגוררה שנים רבות בברוקלין, ניו יורק עד שעברה ללונדון עם בן זוגה ושתי בנותיהם.
הבחירה לעסוק באמנות הייתה עבור כנעני טבעית, "כי זה מה שהמשפחה שלי יודעת לעשות", היא ציינה בראיון שנערך עימה.
האופי של עבודותיה קשור באופן קבוע לעולמות של הוריה: "אמא שלי מגיעה מתחום של תנועה ואבא שלי מאדריכלות.
העבודות שלי, גם אם יש וגם אם אין בהן סיפור, תמיד עוסקות בגוף וחלל".
לאחר סיום לימודיה במכללת האנטר זכתה כנעני במלגת סיקס פוינטס (Six Points) שתמכה בפיתוחו והפקתו של "פרויקט סוטה", עליו עבדה כנעני כחמש שנים.
ב-2009 הוזמנה כנעני ליצור עשרה מיצבי וידאו שהוצגו במקביל בעשרה מוזיאונים בחבל לומברדיה שבאיטליה.
בפרויקט זה, "Dreams and Dramas", הותאמו יצירות הווידאו לחלל הארכיטקטוני וההקשר ההיסטורי של כל אחד ממוסדות האמנות, וכן הכילו תכנים משותפים שקשרו אותם זה לזה ביצירה אחת המורכבת מעשרה חלקים.
ב-2013 היא הוזמנה על ידי מוזיאון המטרופוליטן ליצור עבודת וידאו ארט לאולם הקונצרטים שלו, המבוססת על אוסף המוזיאון והוצגה בשיתוף עם נגינת תזמורת.
היצירה, "שבע מילים", הוזמנה להציג שוב במוזיאון ב-2015.
משנת 2008 כנעני משמשת כמרצה בבית הספר לאמנות חזותית בניו יורק.
ב-2014 היא הוזמנה להקים תוכנית שהות אמן בבית הספר, העוסקת באמנות חברתית במרחב בציבורי.
כנעני מרצה גם במרכז הבינלאומי לצילום בניו יורק (ICP).
בשנת 2024 פורסם כי כנעני משמשת כפרופסורית אורחת באוניברסיטה הטכנית של וינה ומלמדת בבצלאל, שנקר ובאוניברסיטת תל אביב.
עבודותיה של כנעני מתבססות לעיתים קרובות על מחקר ארכיוני וטקסטים קלאסיים וקאנוניים, המעובדים למיצג המשולב עם הקרנת שקופיות או וידאו ארט.
עבודותיה מערבות דימויים שהם רדי מייד עם דימויים שיוצרת כנעני בעצמה, יחד עם נראטיב שחלקו עובדתי וחלקו מומצא.
חלק מעבודותיה הן מבוססות מקום ומיועדות לארכיטקטורה המסוימת שלו.
עבודות המיצב שלה בודקות את הפוטנציאל התיאטרלי של החלל האורבני ואת היחסים בין ארכיטקטורה לנרטיב.
עבודות הווידאו שלה מותאמות לחלל, ויוצרות יחסים חדשים בין הצופה לחלל בו הן מוקרנות.
רישומיה מייצרים סיטואציות מתעתעות, הנראות לעיתים משחקיות ולעיתים אלימות.
הרישומים חוקרים יחסי כוח, תפקידים מגדריים ואופני נראות.
את השימוש בדרכי הבעה מגוונות היא מסבירה: "אני עובדת במדיומים רבים.
שנים רבות עבדתי עם רישומים ועם וידאו.
זה יצר איזון בעבודת הסטודיו שלי - מחד יצרתי בהיקף קטן וביחידות מרובות, ומאידך עשיתי גם הקרנות וידאו גדולות, אותן יכולתי לייצר בתדירות נמוכה יותר, בערך פעם בשנה.
שאלו אותי רבות למה אני לא מחברת ביניהם, אבל מעולם לא התעניינתי באנימציה.
בשלב מסוים התחלתי לעבוד עם הקרנה של שקופיות, אותן אני חותכת ומשנה על ידי רישום.
המעבר הזה בין דו מימד לתלת מימד של ההקרנה עובד בשבילי".
"פרויקט סוטה" (2011) – מיצב וידאו רב הקרנות המעניק פרשנות עכשווית למסכת סוטה התלמודית, העוסקת באישה הנואפת.
המיצב מספר על שתי אחיות אשר בעלה של אחת מן השתיים מאשים אותה בבגידה.
האחות השנייה נחלצת לעזרתה במעשה דרמטי הכולל מסע, התחזות, וסוף טראגי.
במיצב וידאו זה משתתפים השחקנים משה אבגי, טלי שרון, וקרן אור.
"שבע המילים" (2013) - "שבע המילים הוא פרויקט שאפתני ומורכב".
מיצב וידאו מוזיקלי הנעשה במיוחד למוזיאון המטרופוליטן המשלב קונצרט של יצירתו המונומנטלית של יוזף היידן "שבע מילים אחרונות של ישו" המבוצעת על ידי רביעיית מיתרים יחד עם סביבת וידאו דינאמית ומושכת את העין.
Yes, Yes, Yes (2015) – מיצג העוסק בנושא האקסטזה, תחושה של היות אדם מחוץ לעצמו.
העבודה מוצגת בצורת סיור מודרך בו מתהלך הקהל ברחובות העיר, מובל על ידי דמות בשם וי.
וי מנחה את הקהל במסלול שמטרתו היא "בניית מכונת אקסטזה אולטימטיבית".
הסיור עוצר במספר נקודות, בהם מתגלה בפני הקהל כנעני, המציגה בפניהם הרצאה קצרה בנושאים הקשורים לנושא האקסטזה, בשילוב "מכונות אקסטזה" פרי יצירתה.
בדומה לרעיון כי אקסטזה היא תחושה של היות אדם מחוץ לעצמו, כך גם מכונותיה של כנעני מתרגמות מדיום אמנותי אחד (טקסט, סאונד או דימוי) למדיום אמנותי אחר.
1997-2001 בי.אי.די., המדרשה לאמנות, בית ברל, התמחות בווידאו ארט
באמנות חזותית, מכללת האנטר, ניו יורק
2000 מלגה קרן התרבות אמריקה-ישראל ע'ש שרת
2000 מלגת הצטיינות בהישגים אקדמיים, המדרשה לאמנות, מכללת בית ברל
2001 מלגת הצטיינות בהישגים אמנותיים, המדרשה לאמנות, מכללת בית ברל
2003-2004 מלגת לימודים בחו"ל, קרן תרבות אמריקה-ישראל ע'ש שרת
2007 מענק תוכנית Six Points, ניו יורק
2007 מלגת מחקר, מכון הדסה ברנדייס, מסצ'וסטס
2011 מלגת קרן פיליפ ומיוריאל ברמן
2011 מלגת קולנוע נסיוני, קרן רבינוביץ'
2013 מלגת קרן משפחת אוסטרובסקי
2014 מלגת Residency Unlimited, ברוקלין, ניו יורק
2000 "חדר המתנה", גלריה פאר, תל אביב
2003 "תיאטרון שחור לבן", גלריה אלון שגב, תל אביב
2003 "פטרול", מוזיאון הרצליה לאמנות, הרצליה
2004 "השמש עדיין זורחת", גלריה פק, מילאנו
2005 "הקולונל ואני", גלריה אנדראה מייזלין, ניו יורק
2006 "מיתה משונה", מוזיאון חיפה לאמנות, חיפה
2007 "Decreation", גלריה ברוורמן, תל אביב
2007 "Two Dimensional Days", גלריה אנדראה מייזלין, ניו יורק
2009 "עפרי כנעני", גלריה Ugo Ferranti, רומא
2009 "Dreams and Dramas", רשת המוזיאונים של חבל לומברדיה, איטליה
2010 "מאניה", בית ביאליק, תל אביב
2010 "The Vanishing Woman", מיצג במומה פי אס 1, ניו יורק
2011 "פרויקט סוטה", Kunsthalle Galapagos, ברוקלין, ניו יורק
2011 "Public Notice", בשיתוף פעולה עם שריל קפלן, BMW Guggenheim Lab, ניו יורק
2012 "אפקטים מיוחדים" גלריה אנדראה מייזלין, ניו יורק
2013 "ספר", הספרייה הלאומית, ירושלים
2013 "שבע המילים", מוזיאון המטרופוליטן, ניו יורק
2013 "חמש רוחות רפאים עונות על עשר שאלות", פרויקט אמנות ציבורית, The High Line, ניו יורק
2015 "שבע המילים", מוזיאון המטרופוליטן, ניו יורק
בתורת הקבוצות, עץ אהרנשיין הוא עץ שכל שלביו וכל ענפיו בני מניה לכל היותר, ועם זאת הוא אינו בן מניה בעצמו.
קיומו של עץ כזה מפריך את הכללת הלמה של קניג עבור עצמות הגבוהות מ־.
כל עץ סוסלין הוא עץ אהרונשיין.
באופן כללי, לכל מונה , ־עץ אהרונשיין הוא עץ מגובה כך שכל רמה שלו היא בגודל לכל היותר וכל ענף הוא בגובה לכל היותר (ומכאן "עץ אהרונשיין" סתם הוא למעשה ־עץ אהרונשיין).
העץ קרוי על שם המתמטיקאי הפולני נחמן אהרונשיין שהראה בנייה שלהם לראשונה בשנת 1934.
מהלמה של קניג נובע כי לא קיים ־עץ אהרונשיין.
קיומו של ־עץ אהרונשיין הוכח על ידי נחמן אהרונשיין.
טענת קיומו של ־עץ אהרונשיין היא עצמאית — השערת הרצף גוררת את קיומו של עץ זה, ויליאם מיטשל וג'ק סילבר הראו שעקבי שלא קיים ־עץ אהרונשיין (בהינתן קיום של מונה קומפקטי חלש).
רונלד ינסן הוכיח שאקסיומת הבנייה גוררת שקיים ־עץ אהרונשיין (ולמעשה ־עץ סוסלין) לכל מונה אינסופי עוקב .
ג'יימס קאמינגס ומת'יו פורמן הוכיחו בשנת 1998 באמצעות אקסיומות של מונים גדולים שעקבי שאין ־עץ אהרונשיין לכל הגדול מ־.
אם הוא קומפקטי חלש אזי לא קיים ־עץ אהרונשיין.
בכיוון השני, אם הוא אי נסיג, ולא קיים ־עץ אהרונשיין, אזי קומפקטי חלש.
עפרי אילני (נולד ב-9 באפריל 1979) הוא היסטוריון, מרצה, עיתונאי, עורך, בלוגר, מבקר תרבות, מבקר ספרות ואינטלקטואל ציבורי ישראלי.
בעל טור שבועי בעיתון "הארץ" ועורך מגזין "הזמן הזה", מגזין דיגיטלי שבועי, מבית מכון ון ליר בירושלים.
עפרי הוא בנם של המורה לביולוגיה תחיה אקסלרוד והזואולוג גיורא אילני.
גדל ביישוב ספיר בערבה ולמד בתיכון לחינוך סביבתי במדרשת בן-גוריון שבנגב.
אילני החל את הקריירה העיתונאית שלו ככתב ב"זמן הנגב", מרשת המקומונים של "מעריב", ועבר לכתוב במקומון "העיר".
בשנים 2004–2009 עבד ב"הארץ", שם שימש, בין השאר, ככתב במוסף "קפטן אינטרנט" וככתב להשכלה גבוהה ומדע.
באפריל 2009 נפצע קל במהלך סיקור הפגנת ארגוני הנשים מול תחנת המשטרה ברחוב דיזנגוף בתל אביב, שם מחו המפגינים נגד מעצרם של חברי ארגון "פרופיל חדש".
מ-2010 ועד 2017 היה מבקר ספרי עיון ב"ידיעות אחרונות", במדור לספרות.
משנת 2015 הוא בעל טור שבועי, "תחת השמש", ב"הארץ", שעוסק בסוגיות עכשוויות מפרספקטיבה היסטורית ושל ביקורת התרבות.
כעיתונאי סיקר בהרחבה מחקרים ודיונים במדעי הטבע ובמדעי הרוח והיסטוריה.
בין היתר, הציג גישה ביקורתית למחקרים במדעי המוח המבקשים לספק הסברים ביולוגיים לתופעות פוליטיות ותרבותיות.
אילני היה גם עורך בדסק החדשות ובמוסף "גלריה" ב"הארץ" וכן במגזין "כותרת".
בשנת 2023 יצא לאור בהוצאת בבל ספרו "אנחנו אנשים חדשים", ובו טורים שפרסם ב"הארץ" וטורים חדשים.
בשנת 2013 סיים אילני את כתיבת עבודת הדוקטורט שלו באוניברסיטת תל אביב, בהנחיית פרופ' שולמית וולקוב.
העבודה מחדשת בהצבתו במרכז של העם העברי כמושא מחקר במסגרת מחקר המקרא הגרמני.
הטענה היא שחוקרי המקרא האוריינטליסטים באוניברסיטאות הגרמניות ביקשו לבצע רקונסטרוקציה של העם העברי, לצורך שחזורו של הקונטקסט שבתוכו נכתב הטקסט.
בשנים 2013–2015 היה פוסט-דוקטורנט באוניברסיטה העברית ובאוניברסיטת הומבולדט בברלין, גרמניה, בפקולטה לתאולוגיה אוונגלית.
בשנת 2016 היה פוסט-דוקטורנט במרכז לחקר המרת דת ומפגשים בין-דתיים באוניברסיטת בן-גוריון בנגב.
משנת 2017 ועד שנת 2022 היה פוסט-דוקטורנט באקדמיית פולונסקי של מכון ון ליר.
הרצה בחוגים להיסטוריה ולספרות באוניברסיטת תל אביב, וכן בשלוחת תל אביב ושלוחת אבו דאבי של אוניברסיטת ניו יורק.
אילני חוקר גם את ההיסטוריה של היחס להומוסקסואליות בתנועה הציונית.
פרסם בכתב העת "זמנים" מאמר העוסק ביחס להומוסקסואליות בארץ ישראל בתקופת המנדט הבריטי.
במאמרו בחן את השיח על "משכב זכר" בעיתונות העברית של שנות ה-30 ושנות ה-40 של המאה העשרים.
אילני גילה שבתקופת המנדט ראו במקרים של משכב זכר צורה של נחשלות הקשורה לקיום במזרח.
אי לכך תוארו הומוסקסואלים לא רק כסוטים וכדגנרטים מיניים, אלא גם כמחבלים בטוהר הפרויקט הציוני וכבוגדים בפוטנציה.
כמו כן, חקר את ההומוסקסואליות בעולם המוסלמי והערבי.
פרסם מאמרים אקדמיים בכתבי עת שפיטים, בהם: "Journal of the History of Ideas", "Journal of the History of Sexuality", "היסטוריה", "תיאוריה וביקורת" ו"זמנים".
כמו כן, פרסם בכתבי עת שונים, בהם: "אלכסון", המדרשה", "מעיין", "מפתח" ו"ערב רב".
בשנת 2016 יצא לאור ספרו "החיפוש אחר העם העברי: תנ"ך ונאורות בגרמניה" בהוצאת מכון ליאו בק ירושלים ומרכז זלמן שזר.
משנת 2010 שותף אילני בכתיבת ועריכת בלוג ביקורת התרבות "ארץ האמורי" לצד הפילוסוף והעיתונאי גל כץ.
בבלוג התפרסמו סקירות, מאמרים ודעות על עניינים שעל סדר היום ועל עניינים שנדחקו מסדר היום בתחומי פוליטיקה, פילוסופיה, היסטוריה, סוציולוגיה, אקולוגיה, מיניות ותאולוגיה.
הבלוג זכה להצלחה ולשבחים רבים.
בין היתר, הוא נבחר לרשימת המומלצים של רועי צ'יקי ארד ושל אורי קציר; בנוסף, המשורר אהרן שבתאי ציין כי זהו הבלוג המועדף עליו.
2008 - מלגה ENPI, הנציבות האירופית
2013 - מענק מחקר של האוניברסיטה הפתוחה למחקרו "פייטיזם ופילושמיות בגרמניה במאות ה-18 וה-19"
2013 - מלגת מינרבה לפוסטדוקטורט בפקולטה לתאולוגיה אוונגלית של אוניברסיטת הומבולדט בברלין
2016 - מלגה על שם תרצה ויעקב רוזנטל
2016 - פרס על שם גלעד מרגלית על עבודת דוקטורט מצטיינת בהיסטוריה אירופית בעת החדשה
2017- פרס "עם ועולם" על שם בלה ושלמה ברטל, על ספרו "החיפוש אחר העם העברי".
2017 - מלגת פולונסקי לפוסטדוקטורט, מכון ון ליר בירושלים
במשך כ-15 שנה היה בן זוגו של הבלשן ד"ר יאיר אור, מו"ל הוצאת "אוב".
במדעי המחשב, עץ R הוא מבנה נתונים בצורת עץ שנועד לשמש לגישה למידע מרחבי, כלומר לנתונים עם אופי רב ממדי.
נתונים אלו יכולים להיות קואורדינטות גאוגרפיות, מלבנים וצורות גאומטריות נוספות.
עץ R הוצע לראשונה על ידי אנטונין גוטמן בשנת 1984, ומאז נעשה בו שימוש תאורטי ומעשי נרחב.
האות R בשם של מבנה הנתונים היא קיצור למילה מלבן באנגלית - Rectangle.
מבנה הנתונים של עץ R התבסס על עץ +B, והוא תוכנן כך שחיפוש של מידע מרחבי באמצעותו יצריך מעט גישות לצמתים ויתבצע בצורה מהירה.
עץ R הוא עץ חיפוש מאוזן, שבו כל צומתי העלים של העץ הם באותו גובה, והעלים מכילים רשומות אינדקס ומצביעים לערכים בבסיס נתונים.
לכל הצמתים בעץ מוגדר סף מקסימום של ערכים שניתן לאחסן בהם, שמסומן כפרמטר .
כמות הערכים שניתנים לאחסון בצומת היא למעשה כמות הבנים שיכולים להסתעף ממנו והיא מכונה גם רמת הסתעפות (branching factor).
האחסון הקבוע של עץ R הוא לרוב בזיכרון חיצוני למחשב, כי האינדקס נוטה להיות גדול מדי לאחסון בחוצץ בזיכרון הפנימי (שהקיבולת שלו קטנה יחסית).
לכן נוח להגדיר גודל של צומת בעץ כך שיהיה זהה בקירוב לגודל של דף, ובכך בכל קריאה מהזיכרון החיצוני לפנימי יישלף צומת אחד.
פרמטר המקסימום נקבע בפועל כך שניתן יהיה למלא דף בזיכרון בצורה מלאה ככל האפשר, וחישוב נתון זה מבוסס בעיקרו על גודל השדות ברשומת אינדקס וצורת הדחיסה שלהם בצומתי העץ, גודל מצביע (מושפע מגודל כתובת בזיכרון), וגודל הדף.
בנוסף מוגדר סף מינימום של ערכים שיכול להיות בצומת כפרמטר שמקיים את התנאי .
הגדרת סף מינימום זה מאפשרת לאכוף תפוסה מסוימת של ערכים בצמתים והיא משפיעה על האיזון של העץ.
מצד אחד, אכיפה של תפוסה גבוהה מקטינה את כמות הצמתים ומשפיעה על גובה העץ להיות קטן, דבר שיוביל להקטנת כמות הקריאות של צמתים לזיכרון ולייעול הביצועים של חיפוש נתונים.
מצד שני, אכיפה של תפוסה גבוהה מגדילה את כמות הצעדים הממוצעת שמבוצעת בכל פעולת הכנסה ומחיקה בעץ (כי נדרש לבצע פיצול צמתים ומחיקה שלהם בתדירות גבוהה יותר), ובכך מייקרת את עלות הביצועים שלהם.
בכל צומת שאינו השורש יש בין ל- ערכים.
עבור עץ R שמכיל רשומות אינדקס, מתקיים שגובה העץ הוא לכל היותר .
הרעיון העיקרי בעץ R הוא לקבץ עצמים שסמוכים זה לזה במרחב n-ממדי, ולייצג אותם ברמה גבוהה יותר בעץ על ידי המלבן ה-n ממדי הקטן ביותר שמקיף אותם ומקביל לצירים.
מלבן זה מכונה גם מלבן חוסם מינימלי (Minimum Bounding Rectangle, MBR).
מידע יאוחסן בעץ בצורה הבאה:
ערך שמאוחסן בצומת עלה הוא זוג סדור שיכיל שני נתונים - עצם שמייצג נקודה או מלבן חוסם מינימלי במרחב n-ממדי, ומזהה ייחודי לאותו עצם בבסיס הנתונים.
ערך שמאוחסן בצומת פנימי שאינו עלה הוא זוג סדור שיכיל שני נתונים - מלבן במרחב n-ממדי שמכסה את המלבנים של הערכים בצומתי הבנים שלו, ומצביע לצומת בן שלו בעץ.
מלבנים יכולים לחפוף בשטח שלהם זה לזה (כלומר יש חיתוך גאומטרי ביניהם), זאת בניגוד למבני נתונים כמו עץ +B או עץ kd שם אין חפיפות בין ערכים שמייצגים תחום של נתונים שמאוחסנים בצמתים.
כדי להכניס ערך לעץ R, מבוצע מעבר על צמתים בעץ החל מצומת השורש.
בכל שלב נבחנים המלבנים בצומת, ועל ידי היוריסטיקה מסוימת נבחר מלבן מסוים שמייצג תת-עץ כמועמד מתאים להכנסת הערך תחתיו.
ייתכן שיהיו כמה מלבנים שיענו לקריטריון של ההיוריסטיקה ואלגוריתם ההכנסה יצטרך להכריע ביניהם.
לאחר בחירת צומת מתאים האלגוריתם ממשיך לבצע מעבר בצורה רקורסיבית בתוך צומתי הבנים שלו עד להגעה לצומת עלה מתאים.
אם צומת העלה מלא (יש בו כבר ערכים, ובשל כך מתרחשת גלישה - overflow), צריך לפצל אותו לפני שההכנסה תתבצע.
כאן מבוצע שימוש בהיוריסטיקה נוספת לפיצול הערכים לשתי קבוצות מתאימות.
בכל מקרה, לאחר הכנסה לצומת עלה, בודקים אם צריך לעדכן את הערך של המלבן בצומת האב, וכך הלאה בצורה רקורסיבית.
בדומה לעץ +B, גם כאן לאחר פיצול צומת עלה ההכנסה מפעפעת למעלה, כך שלאחר הפיצול מוכנס ערך חדש לצומת האב של העלה.
לאחר מכן אם נדרש גם צומת האב מפוצל, וכך האלגוריתם ממשיך לפי הצורך בצורה רקורסיבית עד הגעה לצומת השורש.
אם גם צומת השורש מלא ונדרש לפצל אותו, נוצר שורש חדש והגובה של העץ גדל בהתאמה.
בכל רמה בעץ, האלגוריתם צריך לבחור את תת-העץ שאליו יוכנס הערך - כלומר לבחור מלבן מתאים.
כשהערך שרוצים להכניס מוכל כולו בתוך אחד המלבנים, הוא נבחר מיידית.
אם יש כמה מלבנים שמכילים את הערך, הכרעה ביניהם נעשית בצורה אקראית.
כשהערך שרוצים להכניס חופף חלקית לכמה מלבנים או שאינו מוכל כלל באף אחד מהם, לבחירת המלבן המתאים יש השפעה על הביצועים של העץ.
הבחירה תלויה בקריטריונים של ההיוריסטיקה.
בעץ R קלאסי ההיוריסטיקה היא בחירת המלבן שמצריך הרחבה מינימלית של השטח שלו כדי להכניס בתוכו את הערך הנוסף, ובמקרה של שוויון ההכרעה היא על ידי בחירת המלבן שמייצג תת-עץ עם שטח קטן יותר.
קיימות וריאציות משופרות של עץ R בהן יש היוריסטיקות אחרות.
בעץ *R למשל נעשה שימוש בהיוריסטיקה משולבת: ברמת העלים נעשה ניסיון למזער את השטחים החופפים בין המלבנים (ובמקרה של שוויון ההכרעה היא על ידי שימוש בהיוריסטיקה של עץ R קלאסי), ואילו ברמות של צמתים פנימיים יותר בעץ נעשה ישירות שימוש בהיוריסטיקה של עץ R קלאסי.
המטרה היא לצמצם את השטח המשותף ששני המלבנים בצמתים החדשים יכסו.
מספר האפשרויות לחלוקה של ערכים מצומת אחד מלא לשני צמתים חדשים הוא אקספוננציאלי למספר הערכים שיש בצומת (סיבוכיות זמן ריצה של אלגוריתם נאיבי שממצה את כל האפשרויות יכולה להגיע ל- ), ולכן צריך להשתמש בהיוריסטיקה כדי למצוא חלוקה מיטבית ככל שאפשר.
גוטמן הציע שתי היוריסטיקות לפיצול צומת בעץ R קלאסי: פיצול ריבועי (quadratic split), ופיצול ליניארי (linear split).
בשתי שיטות אלו מוצאים בהתחלה גרעין מתאים לכל אחת משתי קבוצות הערכים, ולאחר מכן מחלקים את שאר הערכים בין שתי הקבוצות שנוצרו בהתבסס על קריטריונים מסוימים.
פיצול ריבועי (עם סיבוכיות זמן ריצה ריבועית):
האלגוריתם מחפש בהתחלה זוג מלבנים שהם הזוג הגרוע ביותר שאפשר לשבץ ביחד.
זוג מוגדר כגרוע ביותר לשיבוץ ביחד אם לאחר הפחתת שטח זוג המלבנים משטח המלבן החוסם המינימלי שלהם מתקבל השטח הריק הגדול ביותר שלא מנוצל לעומת מלבנים חוסמים מינימליים אחרים.
האלגוריתם משבץ את שני המלבנים שנבחרו כגרעינים לשתי קבוצות נפרדות בהתאמה.
בניסוח פורמלי יותר, בהינתן צומת שמכיל את קבוצת המלבנים , יש למצוא את זוג המלבנים עם המלבן החוסם המינימלי שממקסם את הערך .
לאחר מכן האלגוריתם עובר בלולאה על המלבנים שנותרו, ומוסיף מלבנים לשתי הקבוצות.
בכל פעם ייבחר להוספה מלבן שיש לו את 'ההעדפה החזקה ביותר' לאחת מהקבוצות בהקשרי הפרש בגידול של שטח.
עבור כל מלבן מחושב הגידול בשטח של כל אחת הקבוצות לאחר הוספה שלו אליהן בהתאמה, ומסמנים את המלבן שההפרש בין גידולי השטח בשתי הקבוצות עבורו יהיה הגדול ביותר.
בניסוח פורמלי יותר, בהינתן שני מלבנים חוסמים מינימליים של שתי קבוצות וקבוצת מלבנים שטרם שובצו, יש למצוא את המלבן שממקסם את הערך .
הקבוצה שהאלגוריתם ייבחר להוסיף אליה את המלבן שנבחר היא זו שגידול השטח בה יהיה קטן יותר.
במקרה של שוויון, ההכרעה תהיה הוספה לקבוצה שיש לה את השטח הכולל הקטן יותר; לאחר מכן ההכרעה על ידי בחירה בקבוצה עם מספר הערכים הקטן יותר, ולאחר מכן תהיה בחירה אקראית בין הקבוצות.
הלולאה מסתיימת אם התבצעה השמה של כל הערכים בשתי הקבוצות, או אם באחת הקבוצות יש כמות ערכים מינימלית מספקת.
במקרה האחרון מוסיפים את הערכים שנשארו לקבוצה שכמות הערכים בה קטנה יותר.
פיצול ליניארי (עם סיבוכיות זמן ריצה ליניארית):
האלגוריתם מחפש בהתחלה זוג של מלבנים שיש ביניהם את 'ההפרדה המנורמלת' הגדולה ביותר בין כל הממדים.
בכל אחד מהממדים בוחרים זוג מלבנים שאחד מהם הוא המלבן שהצלע הגבוהה שלו שמקבילה לציר היא הנמוכה ביותר מבין כל הצלעות של המלבנים, והשני הוא המלבן שהצלע הנמוכה שלו שמקבילה לציר היא הגבוהה ביותר מבין כל הצלעות של המלבנים.
בין שני מלבנים אלו יש את ההפרדה הגדולה ביותר באותו ממד.
מנרמלים את ההפרדה באותו ממד על ידי כך שמחלקים את גודל ההפרדה בגודל הצלע של המלבן החוסם בצומת המקורי שמקביל לאותו ציר.
לאחר מכן האלגוריתם בוחר בצורה אקראית את הערכים שנותרו, ומחלק אותם בין שתי הקבוצות.
בחירת הקבוצה שאליה האלגוריתם יוסיף את הערך שנבחר תעשה באופן דומה להיוריסטיקה של פיצול ריבועי.
קיימות אסטרטגיות נוספות לפיצול צמתים מלאים - כמו שיטת הפיצול של גרין, היוריסטיקת הפיצול של *R שכוללת מחיקה של צמתים והכנסה מחדש שלהם, שיטת הפיצול של אנג וטן,, ועוד.
אם מבוצע עדכון לעצם שמוצבע ידי העלים והוא מוביל לשינוי המלבן החוסם המינימלי שלו, צריך למחוק את רשומת האינדקס של אותו עצם מתוך העץ (ביצוע פעולת מחיקה), ולהכניס את האינדקס המעודכן מחדש (ביצוע פעולת הכנסה).
המשמעות היא שביצוע פעולות עדכון על נתונים בצורה תכופה בעץ R זה דבר יקר יחסית (דבר כזה יכול להידרש למשל עבור עצם שנע במהירות במרחב).
מחיקה של ערך מצומת בעץ R כרוכה תחילה במציאה של הצומת שמכיל את הערך שביקשו למחוק אותו (פעולת חיפוש), ואם נמצא צומת מתאים, מחיקה של הערך מאותו צומת.
המחיקה עלולה לגרור צורך בעדכון של ערך מלבן בצומת האב.
במהלך המחיקה ייתכן שיהיה צורך למחוק ערך מצומת השורש.
אם הערך היחיד שיש בצומת השורש הוא לא עלה, מתבצעת מחיקה של צומת השורש וסימון ערך הבן היחיד שלו כצומת שורש חדש.
פעולה כזו מקטינה את הגובה של העץ.
בנוסף, על עץ R מוגדר תנאי לכמות מינימום של ערכים בצומת, לכן יש להתייחס גם אליו במהלך מחיקה.
הטיפול בתנאי זה יתבצע בצורה שונה מזו שבה הוא מתבצע במבנה נתונים כמו עץ +B.
בעץ +B, אם מגיעים למצב שבו רמת התפוסה של ערכים בצומת מסוים היא מתחת למינימום הנדרש (מצב של חמיקה - underflow), ניתן לפי הצורך להפעיל אלגוריתם מיזוג לשני צומתי אחים - מכיוון שהעץ מכיל אינדקס חד־ממדי שהערכים ממוינים לפיו.
לעומת זאת, במידע רב ממדי, התכונה הזאת לא מתקיימת בהכרח.
לכן, במקום זאת, גוטמן הציע לבצע הכנסה מחדש של כל הערכים שנותרו בצומת שהיה בתת-תפוסה, ולמחוק אותו לחלוטין מהעץ.
שיטה זו מאפשרת מימוש פשוט יותר של האלגוריתם כי היא עושה שימוש באלגוריתם של פעולת ההכנסה ונמנעת מאלגוריתם מיזוג ייעודי.
כמו כן יש לה יתרון בעבודה עם בסיסי נתונים, מאחר שהדפים שדרושים להכנסה מחדש היו צריכים להיטען לחוצץ בזיכרון הפנימי כבר במהלך החיפוש של הרשומה שביקשו למחוק.