Binary search tree: Difference between revisions

Revision as of 23:20, 7 July 2023

Revision as of 19:08, 10 July 2023

Line 154:

===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}}

<ol>

# 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.

#<li> 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.
<li> If <math>\text{D}</math> has a single child node, the child gets elevated as either left or right child of {{nowrap|<math>\text{D}</math>'s}} parent depending on the position of <math>\text{D}</math> within the BST, as shown in fig. 2 part (a) and part (b), and as a result, <math>\text{D}</math> gets removed from the tree.

#<li> If <math>\text{D}</math> has both a left and right child, the successor of <math>\text{D}</math> (let it be <math>\text{E}</math> which can not have a left child) takes the position of <math>\text{D}</math> in the tree. This depends on the position of <math>\text{E}</math> within <math>\text{BST}</math>:{{r|algo_cormen|p=296}}

<ul>

# 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{ED}</math>'s}} immediate right child (here, <math>\text{FE}</math>), gets elevated and <math>\text{E}</math>'s takesleft thechild positionpointer ofis made point to {{nowrap|<math>\text{D}</math>'s}} ininitial left <math>\text{BST}</math>sub-tree, as shown herein fig.<ref name="Algs4">According2 to Sedgewickpart ({{Cite bookc).

<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

Line 171 ⟶ 173:

|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]]