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

[יוספי]

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

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

רק לוודא...

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

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

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

תודה

[doker]

1.כן

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

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