Content deleted Content added
m →Deletion: Inside of the pseudocode the variable Y was always written in lowercase except in one line, I wrote it in lowercase there too. |
In the description of the deletion operation case where the node to be removed is a leaf, the text as written deletes the parent as well. The relevant diagram shows only the node being replaced by NIL |
||
Line 156:
[[File:BST node deletion.png|400px|right|The node <math>\text{D}</math> to be deleted has 2 children]]
The deletion of a node, say <math>\text{Z}</math>, from the binary search tree <math>\text{BST}</math> has three cases:{{r|algo_cormen|p=295-297}}
# If <math>\text{Z}</math> is a leaf node,
# 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 successor of <math>\text{Z}</math>, say <math>\text{Y}</math>, displaces <math>\text{Z}</math> by following the two cases:
| |||