Content deleted Content added
m Fix incorrect usage of plural |
→Deletion: More precise successor definition. |
||
Line 158:
# If <math>\text{Z}</math> is a leaf node, it is replaced by <math>\text{NIL}</math> as shown in (a).
# If <math>\text{Z}</math> has only one child, the child node of <math>\text{Z}</math> gets elevated by modifying the parent node of <math>\text{Z}</math> to point to the child node, consequently taking <math>\text{Z}</math>'s position in the tree, as shown in (b) and (c).
# If <math>\text{Z}</math> has both left and right children, the [[Tree_traversal#In-order,_LNR|in-order]] successor of <math>\text{Z}</math>, say <math>\text{Y}</math>, displaces <math>\text{Z}</math> by following the two cases:
## If <math>\text{Y}</math> is <math>\text{Z}</math>'s right child, as shown in (d), <math>\text{Y}</math> displaces <math>\text{Z}</math> and <math>\text{Y}</math>'s right child remain unchanged.
## If <math>\text{Y}</math> lies within <math>\text{Z}</math>'s right subtree but is not <math>\text{Z}</math>'s right child, as shown in (e), <math>\text{Y}</math> first gets replaced by its own right child, and then it displaces <math>\text{Z}</math>'s position in the tree.
# Alternatively, the in-order predecessor can also be used.
The following pseudocode implements the deletion operation in a binary search tree.{{r|algo_cormen|p=296-298}}
| |||