Binary search tree: Difference between revisions

Revision as of 16:11, 23 February 2023

Revision as of 15:36, 23 March 2023

Line 157:

# If <math>\mathsf{D}</math> is a leaf node, the parent node′s pointer to <math>\mathsf{D}</math> gets replaced with <math>\mathsf{NIL}</math> and consequently <math>\mathsf{D}</math> gets removed from the tree.

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

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

##If <math>\mathsf{E}</math> is {{nowrap|<math>\mathsf{D}</math>′s}} immediate right child, <math>\mathsf{E}</math> gets elevated and <math>\mathsf{E}</math>′s left child pointer is made point to {{nowrap|<math>\mathsf{D}</math>′s}} initial left sub-tree, as shown in fig. 2 part (c).

##If <math>\mathsf{E}</math> is not the immediate right child of <math>\mathsf{D}</math>, deletion proceeds by replacing the position of <math>\mathsf{E}</math> by {{nowrap|<math>\mathsf{E}</math>′s}} right child (here <math>\mathsf{F}</math>), and <math>\mathsf{E}</math> takes the position of <math>\mathsf{D}</math> in <math>\mathsf{BST}</math>, as shown here.