Considere uma árvore binária de busca (BST) com n (n>3)
níveis (o nó raiz está no nível 1), 2n - 1 nós e todas as chaves
diferentes. Suponha, ainda, que algum dos pais de
duas folhas seja removido da árvore e, mais tarde, uma
chave com o mesmo valor da chave do nó removido seja
inserida na árvore.
Quantas são as comparações necessárias para fazer a
busca e encontrar o nó cuja chave foi removida e depois
reinserida?