Balanced Binary Tree

Q: Qual é a complexidade de tempo de uma árvore binária balanceada?

Uma passagem em pós-ordem visita cada nó uma vez: tempo O(n) e espaço de pilha O(h) para uma árvore de altura h . Recalcular as alturas em cada nó custa O(n·h) , o que se torna O(n²) em uma cadeia.

FácilPercurso em árvores Recursão

+10

O array root contém uma árvore binária. A raiz está no índice 0, os filhos do índice i estão em 2*i+1 (à esquerda) e 2*i+2 (à direita), -1 marca uma posição vazia, e entradas extras -1 podem aparecer no final.

Retorne true se a árvore for balanceada em altura, ou seja, se em cada nó as alturas das subárvores esquerda e direita diferirem em no máximo 1, e false caso contrário. A altura de uma subárvore é o número de nós em seu caminho descendente mais longo; uma subárvore vazia tem altura 0.

Função

isBalanced(root: integer-array) → boolean

rootinteger-array: a árvore binária em ordem por nível, com -1 para uma posição vazia
Retornaboolean: verdadeiro se as alturas das duas subárvores de cada nó diferirem em no máximo 1; falso caso contrário

Restrições

1 ≤ root.length ≤ 32767
Cada root[i] é -1 ou um valor com 0 ≤ root[i] ≤ 10⁵.
root[0] nunca é -1, portanto a árvore tem pelo menos um nó.
O array pode terminar com entradas extras -1 após o último nó.
Ambos os filhos de um espaço vazio também estão vazios, e a profundidade é no máximo 14.
Os valores dos nós são distintos.

Exemplos

Entrada: root = [5, 2, 9, -1, -1, 7, 11]
Saída: true
Explicação: A subárvore esquerda da raiz é o único nó 2, com altura 1. Sua subárvore direita, 9, 7, 11, tem altura 2. Elas diferem em 1, e todos os outros nós têm duas subárvores de mesma altura.

Entrada: root = [6, 3, 8, 1, -1, -1, 9, 0, -1, -1, -1, -1, -1, -1, 10]
Saída: false
Explicação: Ambos os lados da raiz têm altura 3, mas o nó 3 falha: sua subárvore esquerda 1, 0 tem altura 2 e a direita está vazia.

Entrada: root = [4, 2, -1, 1]
Saída: false
Explicação: A raiz tem a cadeia 2, 1 à sua esquerda, altura 2, e nada à sua direita, altura 0. Uma diferença de 2 é grande demais.

Para ir além

Você consegue verificar a árvore sem recursão, usando uma pilha explícita?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

A regra se aplica a cada nó, então uma árvore cuja raiz parece equilibrada ainda pode falhar mais abaixo, como acontece no segundo exemplo em 3. Uma passagem em pós-ordem calcula a altura de cada subárvore uma única vez e propaga uma falha assim que ela aparece, em O(n).

Recalcule as alturas em cada nó

Intuição

Transforme a definição em código. height(i) é 0 em uma posição vazia e 1 a mais que a altura do filho mais alto nos outros casos. Compare as alturas dos dois filhos em cada nó real; o primeiro nó em que elas diferirem por mais de 1 faz com que a resposta seja false.

Cada verificação percorre toda a subárvore abaixo do nó, então um nó é percorrido uma vez para cada nó acima dele: O(n·h). Com no máximo 14 níveis, uma árvore completa de 16,383 nós custa cerca de 2 × 10^5 etapas. Uma cadeia de n nós custaria O(n²).

Algoritmo

Defina height(i) como 0 para um índice além do fim ou um -1, e como 1 + max(height(2*i+1), height(2*i+2)) para um nó real.
Visite cada índice i que contém um nó real.
Se height(2*i+1) e height(2*i+2) diferirem em mais de 1, retorne false.
Se o loop terminar sem falhas, retorne true.

def isBalanced(root):
    n = len(root)

    def height(i):
        # The number of nodes on the longest downward path from index i.
        if i >= n or root[i] == -1:
            return 0
        return 1 + max(height(2 * i + 1), height(2 * i + 2))

    # Check every real node, measuring both subtrees from scratch.
    for i in range(n):
        if root[i] != -1 and abs(height(2 * i + 1) - height(2 * i + 2)) > 1:
            return False
    return True

Uma passagem em pós-ordem que informa a altura ou a falha

Intuição

A verificação em um nó precisa das alturas de suas duas subárvores, e elas também são o que o nó precisa para informar sua própria altura. Então, obtenha ambas em uma única visita em pós-ordem: cada chamada retorna a altura de sua subárvore depois que ambos os filhos retornaram.

Uma falha em um nível inferior também precisa ser propagada para cima. Uma altura real nunca é negativa, então use -1 para isso: uma chamada retorna -1 quando um filho retornou -1 ou quando as alturas dos filhos diferem em mais de 1. No segundo exemplo, o 3 vê as alturas 2 e 0 e retorna -1, e a raiz o propaga sem visitar seu lado direito.

Nenhum nó é visitado duas vezes, então o tempo é O(n), com O(h) chamadas na pilha.

Algoritmo

Escreva check(i). Para um índice além do fim ou um -1, retorne 0.
Calcule left = check(2*i+1). Se for -1, retorne -1.
Calcule right = check(2*i+2). Se for -1, ou se left e right diferirem em mais de 1, retorne -1.
Caso contrário, retorne 1 + max(left, right).
Retorne se check(0) não é -1.

def isBalanced(root):
    n = len(root)

    def check(i):
        # The height of the subtree at index i, or -1 if it is not balanced.
        if i >= n or root[i] == -1:
            return 0
        left = check(2 * i + 1)
        if left == -1:
            return -1
        right = check(2 * i + 2)
        if right == -1 or abs(left - right) > 1:
            return -1
        return 1 + max(left, right)

    return check(0) != -1

Armadilhas e casos extremos

Verificar apenas a raiz. No segundo exemplo, os dois lados da raiz têm altura 3, mas o nó 3 está desbalanceado em 2.
Comparar a folha mais superficial com a mais profunda. A menor árvore balanceada de altura 6 tem folhas nas profundidades 4 e 6, e todos os nós dela passam na verificação.
Perder uma falha no caminho de volta. Se um filho retorna -1 e o pai calcula 1 + max(-1, 2), a falha volta a ser uma altura.
Usar o comprimento do array como altura. As entradas -1 no final fazem o array ficar mais longo do que a profundidade da árvore.
Em Lua e R, os arrays começam em 1. Mantenha os índices dos nós baseados em 0 para 2*i+1 e leia root[i + 1].

Perguntas frequentes3

Qual é a complexidade de tempo de uma árvore binária balanceada?

Uma passagem em pós-ordem visita cada nó uma vez: tempo O(n) e espaço de pilha O(h) para uma árvore de altura h. Recalcular as alturas em cada nó custa O(n·h), o que se torna O(n²) em uma cadeia.

O que significa balanceada em altura para uma árvore binária?

Em cada nó, as alturas das subárvores esquerda e direita diferem em no máximo 1. As árvores AVL restauram essa propriedade após cada inserção e exclusão, o que mantém sua altura em O(log n).

Uma árvore binária completa é sempre balanceada?

Sim. Todos os níveis de uma árvore completa estão cheios, exceto possivelmente o último, que se preenche da esquerda para a direita; portanto, em qualquer nó, as alturas das duas subárvores diferem no máximo em 1. O inverso é falso: uma árvore balanceada pode ter lacunas à esquerda no último nível.

def isBalanced(root):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

root = [5, 2, 9, -1, -1, 7, 11]

Saída Esperada

true