Editing Binary search tree (section)

===Deletion===
[[File:BST node deletion.png|thumb|400px|right|Binary search tree node deletion process.]]
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, 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}}
{|
|- style="vertical-align:top"
|
 1    BST-Delete(BST, z)
 2      '''if''' z.left = NIL '''then'''
 3        Shift-Nodes(BST, z, z.right)
 4      '''else if''' z.right = NIL '''then'''
 5        Shift-Nodes(BST, z, z.left)
 6      '''else'''
 7        y := BST-Successor(z)
 8        '''if''' y.parent &ne; z '''then'''
 9          Shift-Nodes(BST, y, y.right)
 10         y.right := z.right
 11         y.right.parent := y
 12       '''end if'''
 13       Shift-Nodes(BST, z, y)
 14       y.left := z.left
 15       y.left.parent := y
 16     '''end if'''
|-
|
 1    Shift-Nodes(BST, u, v)
 2      '''if''' u.parent = NIL '''then'''
 3        BST.root := v
 4      '''else if''' u = u.parent.left '''then'''
 5        u.parent.left := v
 5      '''else'''
 6        u.parent.right := v
 7      '''end if'''
 8      '''if''' v &ne; NIL '''then'''
 9        v.parent := u.parent
 10     '''end if'''
|}
The <math>\text{BST-Delete}</math> procedure deals with the 3 special cases mentioned above. Lines 2-3 deal with case 1; lines 4-5 deal with case 2 and lines 6-16 for case 3. The [[helper function]] <math>\text{Shift-Nodes}</math> is used within the deletion algorithm for the purpose of replacing the node <math>\text{u}</math> with <math>\text{v}</math> in the binary search tree <math>\text{BST}</math>.{{r|algo_cormen|p=298}} This procedure handles the deletion (and substitution) of <math>\text{u}</math> from <math>\text{BST}</math>.