# The Algorithm Design Manual (Steven S. Skiena)

Acordei no meio da noite pensando em como remover um elemento de uma árvore, aí eu desisti de criar minha própria solução. Baixei The Algorithm Design Manual e Cormen para aprender. Um lapso temporário.

Recortes

It is traditional for the author to magnanimously accept the blame for whatever deficiencies remain. I don’t. Any errors, deficiencies, or problems in this book are somebody else’s fault, but I would appreciate knowing about them so as to determine who is to blame.

Binary search requires that we have fast access to two elements—specifically the median elements above and below the given node. To combine these ideas, we need a “linked list” with two pointers per node. This is the basic idea behind binary search trees.

But what of a to-be-deleted node with two children? Our solution is to relabel this node with the key of its immediate successor in sorted order. This successor must be the smallest value in the right subtree, specifically the leftmost descendant in the right subtree (p). Moving this to the point of deletion results in a properly-labeled binary search tree, and reduces our deletion problem to physically removing a node with at most one child—

Unfortunately, bad things can happen when building trees through insertion. The data structure has no control over the order of insertion. Consider what happens if the user inserts the keys in sorted order. The operations insert(a), followed by insert(b), insert(c), insert(d),…will produce a skinny linear height tree where only right pointers are used.

There are three desirable properties for a good algorithm. We seek algorithms that are correct and efficient, while being easy to implement.

These goals may not be simultaneously achievable.

It is seldom obvious whether a given algorithm correctly solves a given problem. Correct algorithms usually come with a proof of correctness, which is an explanation of why we know that the algorithm must take every instance of the problem to the desired result.

Seeking counterexamples that break pretender algorithms is an important part of the algorithm design process. efficient algorithms are often lurking out there;

The heart of any algorithm is an idea. If your idea is not clearly revealed when you express an algorithm, then you are using too low-level a notation to describe it.