Binary search tree: Difference between revisions

Revision as of 11:08, 14 March 2024

Revision as of 18:11, 7 April 2024

Line 158:

# If <math>\text{Z}</math> is a leaf node, the parent node of <math>\text{Z}</math> gets replaced by <math>\text{NIL}</math> and consequently <math>\text{Z}</math> is removed from the <math>\text{BST}</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 childchildren, the 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.