deleting
There are 3 cases
- The item to be deleted is a leaf node (no children).
- Just find the node and keep track of it’s parent
- Remove the pointer to the child
- Free the child
- The item deleted has only 1 child
- The parent links to the child of the deleted node.
- The item deleted has two children.
- Find the node we wanna delete
- Find the successor of the node
- The node we were going to delete becomes the successor (copy the data from the successor into the deleted)
- Delete the successor node (either case a or b)