|
===Deletion===
Deletion of a node, say <math>\textmathsf{zD}</math>, from a binary search tree <math>\textmathsf{TBST}</math> should abide three cases:{{r|algo_cormen|p=295}}
# If <math>\textmathsf{zD}</math> is a leaf node, the parent node′s pointer to <math>\textmathsf{zD}</math> gets replaced with <math>\textmathsf{nilNIL}</math> and consequently <math>\textmathsf{zD}</math> gets removed from the tree.
# If <math>\textmathsf{zD}</math> has a single child node, the child gets elevated as either left or right child of {{nowrap| <math>\textmathsf{zD}</math>′s}} parent depending on the position of <math>\textmathsf{zD}</math> within the BST, as shown in fig. 2 part (a) and part (b), and as a result, <math>\textmathsf{zD}</math> gets removed from the tree.
# If <math>\textmathsf{zD}</math> has both a left and right child, the successor of <math>\textmathsf{zD}</math> (let it be <math>\textmathsf{yE}</math> which does not have a left child)) takes the position of <math>\textmathsf{zD}</math> in the tree. This depends on the position of <math>\textmathsf{yE}</math> within the <math>\mathsf{BST}</math>:{{r|algo_cormen|p=296}}
##If <math>\textmathsf{yE}</math> is {{nowrap|<math>\textmathsf{zD}</math>′s}} immediate right child, <math>\textmathsf{yE}</math> gets elevated and <math>\textmathsf{yE}</math>′s left child pointer is made point to {{nowrap|<math>\textmathsf{zD}</math>′s}} initial left sub-tree, as shown in fig. 2 part (c).
##If <math>\textmathsf{yE}</math> is not the immediate right child of <math>\textmathsf{zD}</math>, deletion proceeds by replacing the position of <math>\textmathsf{yE}</math> by {{nowrap|<math>\textmathsf{yE}</math>′s}} right child (here <math>\mathsf{F}</math>), and <math>\textmathsf{yE}</math> takes the position of <math>\textmathsf{zD}</math> in the <math>\mathsf{BST}</math>, as shown in fig. 2 part (d)here.
[[File:AVL-tree-delete.svg|600px|The node <math>\mathsf{D}</math> to be deleted has 2 children]]
{{clear}}
The following pseudocode implements the deletion operation in a binary search tree.{{r|algo_cormen|p=296-298}}
{|
|- style="vertical-align:top"
|
1 BST-DeleteBST_Delete(TBST, zD)
2 '''if''' zD.left = NIL '''then'''
3 Shift-NodesShift_Nodes(TBST, zD, zD.right)
4 '''else if''' zD.right = NIL '''then'''
5 Shift-NodesShift_Nodes(TBST, zD, zD.left)
6 '''else'''
7 yE := Tree-SuccessorTree_Successor(zD)
8 '''if''' yE.parent ≠ zD '''then'''
9 Shift-NodesShift_Nodes(TBST, yE, yE.right)
10 yE.right := zD.right
11 yE.right.parent := yE
12 '''end if'''
13 Shift-NodesShift_Nodes(TBST, zD, yE)
14 yE.left := zD.left
15 yE.left.parent := yE
16 '''end if'''
|
1 Shift-NodesShift_Nodes(TBST, u, v)
2 '''if''' u.parent = NIL '''then'''
3 TBST.root := v
4 '''else if''' u = u.parent.left '''then'''
5 u.parent.left := v
10 '''end if'''
|}
The <math>\textmathsf{Tree-Delete\_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>\textmathsf{Shift-Nodes\_Nodes}</math> is used within the deletion algorithm for the purpose of replacing the node <math>\textmathsf{u}</math> with <math>\textmathsf{v}</math> in the binary search tree <math>\textmathsf{TBST}</math>.{{r|algo_cormen|p=298}} This procedure handles the deletion (and substitution) of <math>\textmathsf{u}</math> from the <math>\mathsf{BST}</math>.
==Traversal==
| 