AVL Tree/Discussion: Difference between revisions

Deleting entries from a Binary Search Tree turns out to be quite tricky. When a node has only one child it is easy, just go to the parent and link the child of the node to be deleted in place of the node itself. The main problem arises when the node to be deleted has two children. For example, the following tree will be built, and node 6 will be deleted.

 

 

Node 6 has two children. To delete it, node 6 will be swapped with node 4, then deleted. The tree that remains is shown below.