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