Binary search tree: Difference between revisions

Revision as of 16:39, 23 March 2023

Revision as of 16:59, 23 March 2023

Line 160:

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

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

&nbsp; &nbsp; &nbsp; [[File:AVL-tree-delete.svg|600px|The node <math>\text{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}}