Binary search tree: Difference between revisions

Revision as of 19:08, 10 July 2023

Revision as of 19:11, 10 July 2023

Line 153:

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

<li> If <b><math>\text{D}</math> is a leaf node,.</b> theThe 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 <b><math>\text{D}</math> has a single child node,.</b> theThe 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 <b><math>\text{D}</math> has both a left and right child,.</b> theThe 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>

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