Self-balancing trees deletion

Problem Description

Given a binary tree, delete a node from it by making sure that tree shrinks from the bottom.

Bounds Chart

Step Chart

Improvement Table

Complexity Classes	Algorithm Paper Links	Lower Bounds Paper Links
Exp/Factorial
Polynomial > 3
Cubic
Quadratic
nlogn
Linear
logn	[ 2-3 Tree (1970)] Guibas, Sedgewick Red-Black Tree (1972)