עבור לתוכן

שאלה בעץ בינארי ו AVL

Featured Replies

פורסם

שלום רב , 2שאלות קטנות בקשר לעצים

1, במידה והעץ ריק, (בלי שורש כלל) הגובה שלו -1 אם יש לו רק שורש הגובה 0 ואם יש לו שורש עם בן הגובה 1?

רק לוודא...

2.כאשר מוסיפים איבר ל AVL ייתכן שנצטרך לעשות גלגול 1 בלבד

אבל כאשר נמחק איבר מ AVL ייתכן שנצטרך לעשות יותר מגלגול 1, מקסימום LOG N גלגולים(N זה מספר האיברים בעץ)

מדוע יש הבדל בין המחיקה להוספה , שבהוספה מקסימום 1 ובמחיקה יותר?

תודה

פורסם

1.כן

2.בקצרה-כשמוסיפים איבר לAVL אם אני זוכר נכון לעיתים צרכים לעשות יותר מגלגול אחד. (מקסימום 2 אני חושב)

כשמוחקים איבר לעומת זאת יכול ליהיות שנהרוס את התכונה של הBST ולכן צריך לדאוג לכך שהתכונה תישמר. לכן עולים במעלה העץ כלומר (LOG(N

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים