Binary search tree: Difference between revisions

Revision as of 15:33, 18 June 2023

Revision as of 13:04, 2 July 2023

Line 157:

# 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}} 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}} 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.<ref name="Algs4">According to Sedgewick ({{Cite book

|last1=Sedgewick

|first1=Robert

|author1-link=Robert Sedgewick (computer scientist)

|last2=Wayne

|first2=Kevin

|title=Algorithms

|edition=4th

|isbn=978-0-321-57351-3

|year=2011

|publisher=Addison-Wesley Professional

|url=http://algs4.cs.princeton.edu}})

the idea of this node exchange is due to T. Hibbard.</ref>

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

{{clear}}