|
===Deletion===
Deletion of a node, say <math>\text{D}</math>, from a binary search tree <math>\text{BST}</math> should abide three cases.:{{r|algo_cormen|p=295}}
# If <math>\text{D}</math> is a leaf node, the parent node's pointer to <math>\text{D}</math> gets replaced with <math>\text{NIL}</math> and consequently <math>\text{D}</math> gets removed from the tree.
<ol>
<li># If <b><math>\text{D}</math> ishas a leafsingle child node.</b>, Thethe parentchild node'sgets pointerelevated toas either left or right child of {{nowrap|<math>\text{D}</math>'s}} getsparent depending on the replacedposition withof <math>\text{NILD}</math> within the BST, as shown in fig. 2 part (a) and consequentlypart (b), and as a result, <math>\text{D}</math> gets removed from the tree.
<li># If <b><math>\text{D}</math> has both a singleleft childand node.</b> Theright child, getsthe elevatedsuccessor asof either<math>\text{D}</math> left(let orit rightbe child of {{nowrap|<math>\text{DE}</math>'s}} parentwhich dependingcan onnot have a left child) takes the position of <math>\text{D}</math> withinin the BST, as shown in figtree. 2This partdepends (a)on andthe partposition (b), and as a result,of <math>\text{DE}</math> gets removedwithin from the tree.<math>\text{BST}</math>:{{r|algo_cormen|p=296}}
# If <limath> \text{E}<b/math> is {{nowrap|<math>\text{D}</math>'s}} has both a left andimmediate right child.</b> The successor of, <math>\text{DE}</math> (letgets itelevated beand <math>\text{E}</math> which can not have a's left child) takespointer theis positionmade ofpoint to {{nowrap|<math>\text{D}</math>'s}} ininitial theleft sub-tree., Thisas dependsshown onin thefig. position2 ofpart <math>\text{E}</math> within <math>\text{BST}</math>:{{r|algo_cormen|p=296}}(c).
<li># If <math>\text{E}</math> is not the immediate right child of <math>\text{D}</math>, deletion proceeds by replacing the position of <math>\text{E}</math> by {{nowrap|<math>\text{E}</math>'s}} right child (here <math>\text{F}</math>), and <math>\text{E}</math> takes the position of <math>\text{D}</math> in <math>\text{BST}</math>, as shown here.<ref name="Algs4">According to Sedgewick ({{Cite book ▼<ul>
<li>If <math>\text{E}</math> is {{nowrap|<math>\text{D}</math>'s}} immediate right child, <math>\text{E}</math> gets elevated and <math>\text{E}</math>'s left child pointer is made point to {{nowrap|<math>\text{D}</math>'s}} initial left sub-tree, as shown in fig. 2 part (c).
▲<li>If <math>\text{E}</math> is not the immediate right child of <math>\text{D}</math>, deletion proceeds by replacing the position of <math>\text{E}</math> by {{nowrap|<math>\text{E}</math>'s}} right child (here <math>\text{F}</math>), and <math>\text{E}</math> takes the position of <math>\text{D}</math> in <math>\text{BST}</math>, as shown here.<ref name="Algs4">According to Sedgewick ({{Cite book
|last1=Sedgewick
|first1=Robert
|url=http://algs4.cs.princeton.edu}})
the idea of this node exchange is due to T. Hibbard.</ref>
</ul>
</ol>
[[File:AVL-tree-delete.svg|600px|The node <math>\text{D}</math> to be deleted has 2 children]]
| 