עץ חיפוש בינארי - מחיקת איבר

תחילה נמצא את הצומת A בעל הערך אותו אנו רוצים למחוק על ידי אלגוריתם החיפוש.
אם לצומת A אין בנים: ניתן למחוק אותו מיידית מהעץ (על ידי החלפת המצביע אליו מאביו ב-NIL).
אם לצומת A יש בן אחד: נחליף את המצביע מאביו של הצומת A כך שיצביע אל הבן של A.
אם לצומת A יש שני בנים: נמצא את הצומת B בעל הערך המינימלי בתת העץ הימני של A. נחליף את ערכו של A בערכו של B ואז נמחק את B באותה שיטה. בכל צעד אנו מתרחקים משורש העץ ולכן מספר הצעדים המקסימלי הוא גובה העץ.

זמן פעולה: כגובה העץ: (O(logn בממוצע, (O(n במקרה הגרוע.

function bst_delete(node)
   if (node.right == nil)
      replace node with node.left
   else if (node.left == nil)
      replace node with node.right
   else
      next <- node.right
      while (next.left != nil) next <- next.left
      node.data <- next.data
      bst_delete(next)