Binary search tree: Difference between revisions

Revision as of 16:39, 11 February 2023

Revision as of 08:21, 12 February 2023

Line 155:

===Deletion===

Deletion of a node, say <math>\text{z}</math>, from a binary search tree <math>\text{T}</math> should abide three cases:{{r|algo_cormen|p=295}}

# If <math>\text{z}</math> is a leaf node, the parent node'snode′s pointer to <math>\text{z}</math> gets replaced with <math>\text{nil}</math> and consequently <math>\text{z}</math> gets removed from the tree.

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

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

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

##If <math>\text{y}</math> is not the immediate right child of <math>\text{z}</math>, deletion proceeds by replacing the position of <math>\text{y}</math> by its{{nowrap|<math>\text{y}</math>′s}} right child, and <math>\text{y}</math> takes the position of <math>\text{z}</math> in the BST, as shown in fig. 2 part (d).

The following pseudocode implements the deletion operation in a binary search tree.{{r|algo_cormen|p=296-298}}