Binary search tree: Difference between revisions

Revision as of 04:21, 18 June 2023

Revision as of 15:31, 18 June 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}}

# If <math>\text{D}</math> is a leaf node, the parent node′snode'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.

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

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

##If <math>\text{E}</math> is {{nowrap|<math>\text{D}</math>′s's}} immediate right child, <math>\text{E}</math> gets elevated and <math>\text{E}</math>′s's left child pointer is made point to {{nowrap|<math>\text{D}</math>′s'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'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.

[[File:AVL-tree-delete.svg|600px|The node <math>\text{D}</math> to be deleted has 2 children]]

{{clear}}