Para cada nó em uma árvore binária balanceada, a diferença máxima nas alturas da subárvore filho esquerda e da subárvore filho direita são no máximo 1.
A altura de uma árvore binária é a distância do nó raiz ao filho do nó que está mais distante da raiz.
Abaixo está um exemplo:
2 <-- root: Height 1
/ \
7 5 <-- Height 2
/ \ \
2 6 9 <-- Height 3
/ \ /
5 11 4 <-- Height 4
Altura da árvore binária: 4
A seguir, são apresentadas árvores binárias e um relatório sobre se elas estão ou não equilibradas:
A árvore acima está desequilibrada .
A árvore acima está equilibrada .
Escreva o programa mais curto possível que aceite como entrada a raiz de uma árvore binária e retorne um valor de falsey se a árvore estiver desequilibrada e um valor de verdade se a árvore estiver equilibrada.
Entrada
A raiz de uma árvore binária. Isso pode estar na forma de uma referência ao objeto raiz ou mesmo de uma lista que é uma representação válida de uma árvore binária.
Resultado
Retorna o valor verdadeiro: se a árvore estiver equilibrada
Retorna o valor falsey: se a árvore não estiver equilibrada.
Definição de uma árvore binária
Uma árvore é um objeto que contém um valor e outras duas árvores ou ponteiros para eles.
A estrutura da árvore binária é semelhante à seguinte:
typedef struct T
{
struct T *l;
struct T *r;
int v;
}T;
Se estiver usando uma representação de lista para uma árvore binária, pode ser algo como o seguinte:
[root_value, left_node, right_node]
4
, a árvore restante está equilibrada?Respostas:
Gelatina , 11 bytes
Experimente online!
A árvore vazia é representada por
[]
.fonte
Prolog (SWI) , 49 bytes
Experimente online!
Representa árvores como
Value/Left_Child/Right_Child
, com a árvore vazia sendo o átomoe
. Define+/2
, que é gerado por sucesso ou falha, com uma variável não acoplada (ou uma já igual à altura da árvore) à esquerda e a árvore à direita - se o argumento da altura for inaceitável, adicione 9 bytes para definir-T:-_+T.
.fonte
_/
poderá ser retirado por -2 bytes.)Wolfram Language (Mathematica) , 50 bytes
Use
Null
para nulo,value[left, right]
para nós. Por exemplo, a seguinte árvore é escrita como2[7[2[Null, Null], 6[5[Null, Null], 11[Null, Null]]], 5[Null, 9[4[Null, Null], Null]]]
.Experimente online!
fonte
Python 3.8 (pré-lançamento) ,
133125 bytesExperimente online!
Toma uma árvore no formato "lista": um nó está
[value, left, right]
comleft
eright
sendo nós.Invoque a função
h
.Retorna
0
ouFalse
para uma árvore desequilibrada. Retorna1
ouTrue
para uma árvore equilibrada.Ungolfed:
-10: Lógica invertida para se livrar de
not
sSe a permissão de argumentos no meio de uma chamada for permitida, isso poderá ser reduzido para (115 bytes)
com
_
ser a árvore para verificar.fonte
JavaScript (Node.js) , 49 bytes
Experimente online!
-9 bytes por Arnauld.
JavaScript, 58 bytes
Experimente online!
Use
[]
para nulo e[left, right, value]
para nós.fonte
JavaScript, 162 bytes
Experimente online!
O formato da entrada é um objeto
Explicação
Ao executar a primeira pesquisa de largura, encontre a profundidade do primeiro nó em que um ou mais ramos estão ausentes.
Continuando a primeira pesquisa de largura, retorne zero se algum elemento for dois mais profundo que a profundidade do primeiro nó que está faltando ramificações.
Se nenhum nó for encontrado, retorne 1
fonte
4
.Julia, 56 bytes
Com a seguinte estrutura representando a árvore binária:
c
é uma tupla que representa os nós esquerdo e direito e a tupla vazia()
é usada para sinalizar a ausência de um nó.O valor de Falsey é
NaN
, qualquer número inteiro é verdadeiro.fonte
≢
, de acordo com o contador de bytes interno do TIO . De qualquer forma, bem-vindo ao CG&CC!Kotlin , 67 bytes
Onde
Experimente online!
fonte
C, 117 bytes
A implementação do Struct é a seguinte:
Experimente isso no JDoodle
fonte
<2
a última verificação em vez dissoPython 2 ,
999694 bytesExperimente online!
3 bytes de Jo King .
Recebe entrada como: nó vazio é
[]
e outros nós são[<value>, <leftNode>, <rightNode>]
. Saídas0/1
para Falso / Verdadeiro.fonte