Binary search tree: Difference between revisions

Revision as of 02:06, 11 July 2023

Revision as of 02:13, 11 July 2023

Line 156:

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, 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 itspoint 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 child, 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.