A prova para a profundidade da árvore de pesquisa balanceada

Question

Se T é um BST equilibrada com n elementos, L sua subárvore esquerda e R sua direita, como posso provar que a sua profundidade é inferior ou igual a 2log (n) + 1?

Há uma prova por indução que eu tenho, mas eu não consegui-lo.

(Eu entendo que stackoverflow é principalmente programação orientada, mas eu achei algumas perguntas sobre árvores de busca binária e decidiu dar-lhe uma tentativa, espero que eu não estou fazendo algo não é bom:).)

Answer 1

Por definição de "equilibrado", profundezas de cada subárvores esquerda e direita do mesmo nó diferem, no máximo, por um. "Profundidade" é normalmente definida como "número de passo de caminhada mais longa a partir da raiz da árvore para baixo a folha", de modo que por exemplo um BST com uma raiz e duas folhas (três elementos na única maneira que eles podem ser dispostos em um BST equilibrado) é disse ter uma profundidade (parece que você está usando uma definição ligeiramente diferente, que iria dar-lhe profundidade dois?), como seria um com uma raiz e uma folha (quer que folha é subárvore esquerda ou direita da raiz não faz diferença), enquanto um com apenas uma raiz que é também uma folha (um único elemento) teriam profundidade 0. (não há BST com zero elementos).

Assim, para n <= 3 elementos, chamando-D (n) a profundidade de árvore como acima definido, claramente D(n) < log(n) + 1 (com log significando logaritmo de base 2) por inspecção, uma vez que 1 = D(2) < log(2) + 1 = 2 (e também 1 = D(3) para que a RHS de desigualdade, log(3) + 1, é na verdade > 2) e 0 = D(1) < log(1) + 1 = 1 - isso nos dá a base de indução

.

Para completar a prova por indução temos que mostrar que se D(k) < log(k) + 1 para todos k < n, em seguida, segue-se também que D(n) < log(n) + 1.

Se n é ímpar, claramente à esquerda e subárvore direita têm elementos (n-1)/2 cada, e a árvore tem profundidade 1 mais do que os sub-árvores; mas então D(n) = 1 + D((n-1)/2) < 1 + 1 + log((n-1)/2) (pela hipótese de indução) = 1 + log(n-1) (desde log((n-1)/2) = log(n-1) - 1) e, portanto, uma < 1 + log(n) fortiori, QED.

Se n é mesmo que você siga apenas os mesmos passos com log(n) vez de log(n-1) e sem o acabamento "a fortiori", ea prova ainda se mantém.

Answer 2

A sua resposta é verdadeira se árvore binária equilibrada é completa o número de elementos na sub árvore direita e esquerda pode ser (n-1) / 2, mas se não é completo, número de elementos não precisa ser (n-1) / 2 como último nível pode ter elementos diferentes