Binary search tree: Difference between revisions

Revision as of 01:54, 11 July 2023

Revision as of 02:02, 11 July 2023

Line 155:

[[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, 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, taking <math>\text{Z}</math>'s position in the tree, by modifying the parent node of <math>\text{Z}</math> to the child node, 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 the following cases:

## If <math>\text{Y}</math> is <math>\text{Z}</math>'s right child, as shown in (cd), <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 (de), <math>\text{Y}</math> gets replaced by its own right child, and then it displaces <math>\text{Z}</math>'s position in the tree.

The following pseudocode implements the deletion operation in a binary search tree.{{r|algo_cormen|p=296-298}}