Where it runs
1. The problem
In the last lesson the insert kept the tree balanced: add a value, then on the way back up level the node that tipped over. Delete works the same way, but its ending is harder. First you do an ordinary BST delete (the one from step 70: a leaf, one child, or two children through the in-order successor), and then you level the path back up. The difficulty: removing a node can make a whole subtree shorter. A shorter subtree can tip its parent off by 2. Repairing the parent can in turn tip its parent, and so on. So the insert stops after one repair, while the delete checks and rotates at every level up to the root.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedOn LeetCode
Problems that need a sorted set with deletions, such as taking the smallest free item or keeping only the last k values. AVL delete keeps every operation at O(log n).
Keep the free seats in the tree, reserve deletes the leftmost node and unreserve inserts the seat back.
Keep prices in the tree with a count each, and a correction deletes the old price and inserts the new one, so the minimum and maximum are the two ends.
Keep the last indexDiff values in the tree, delete the one that leaves the window, and search for the smallest value at least nums[i] minus valueDiff.