Escreva o programa mais curto para verificar se uma árvore binária está equilibrada

15

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:

Caso de teste 1

A árvore acima está desequilibrada .

Caso de teste 2

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]
T. Salim
fonte
2
A entrada pode ser uma árvore vazia?
tsh
1
No seu exemplo inicial de uma árvore, se você remover a folha 4, a árvore restante está equilibrada?
Neil
Não, não esse exemplo, eu quis dizer o inicial, usando arte ASCII.
Neil
De acordo com minha própria implementação "C, 117 bytes": Não, uma vez que a altura da subárvore direita a partir de "5" é 2 e a altura da subárvore esquerda é 0.
T. Salim
As edições têm pelo menos 6 caracteres, mas remova a vírgula entre 'balanceado' e 'binário' - 'árvore binária' é uma frase substantiva; portanto, escrever 'árvore binária equilibrada' é o equivalente a 'móvel móvel de neve' - o vírgula não é necessária.
Geza Kerecsenyi 7/08/19

Respostas:

8

Gelatina , 11 bytes

ḊµŒḊ€IỊ;߀Ạ

Experimente online!

A árvore vazia é representada por [].

Erik, o Outgolfer
fonte
Obrigado Erik por estar entre os primeiros a responder a esta pergunta. Jelly certamente é uma linguagem muito popular neste site. Eu acho que deveria ter a liberdade de implementar essa linguagem. É bom aprender com uma linguagem robusta de script de golfe.
T. Salim
Parabéns Erik, o Outgolfer, você é o vencedor.
T. Salim
3

Prolog (SWI) , 49 bytes

N+_/B/C:-X+B,Y+C,abs(X-Y)<2,N is max(X,Y)+1.
0+e.

Experimente online!

Representa árvores como Value/Left_Child/Right_Child, com a árvore vazia sendo o átomo e. 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..

N + _/B/C :-            % If the second argument is a tree of the form _Value/B/C,
    X+B,                % X is the height of its left child which is balanced,
    Y+C,                % Y is the height of its right child which is balanced,
    abs(X-Y) < 2,       % the absolute difference between X and Y is strictly less than 2,
    N is max(X,Y)+1.    % and N is the height of the full tree.
0 + e.                  % If, on the other hand, the second argument is e, the first is 0.
String não relacionada
fonte
(Se o valor de cada nó puder ser omitido da entrada, _/poderá ser retirado por -2 bytes.)
String não relacionada
3

Wolfram Language (Mathematica) , 50 bytes

f@_[x_,y_]:=f@x&&f@y&&-2<Depth@x-Depth@y<2;f@_=1>0

Use Nullpara nulo, value[left, right]para nós. Por exemplo, a seguinte árvore é escrita como 2[7[2[Null, Null], 6[5[Null, Null], 11[Null, Null]]], 5[Null, 9[4[Null, Null], Null]]].

    2
   / \
  7   5
 / \   \
2   6   9
   / \  /
  5  11 4

Experimente online!

alefalpha
fonte
Isso é muito bonito!
Greg Martin
3

Python 3.8 (pré-lançamento) , 133 125 bytes

b=lambda t:((max(l[0],r[0])+1,abs(l[0]-r[0])<2)if(l:=b(t[1]))[1]and(r:=b(t[2]))[1]else(0,0))if t else(0,1)
h=lambda t:b(t)[1]

Experimente online!

Toma uma árvore no formato "lista": um nó está [value, left, right]com lefte rightsendo nós.

Invoque a função h.

Retorna 0ou Falsepara uma árvore desequilibrada. Retorna 1ou Truepara uma árvore equilibrada.

Ungolfed:

# Returns tuple (current height, subtrees are balanced (or not))
def balanced(tree):
  if tree: # [] evaluates to False
    left = balanced(tree[1])
    right = balanced(tree[2])
    # If  the subtrees are not both balanced, nothing to do, just pass it up
    if left[1] and right[1]:
      height = max(left[0], right[0]) + 1
      subtrees_balanced = abs(left[0] - right[0]) < 2
    else:
      height = 0 # Value doesn't matter, will be ignored
      subtrees_balanced = False
  else:
    height = 0
    subtrees_balanced = True
  return (height, subtrees_balanced)

def h(tree):
  return balanced(tree)[1]

-10: Lógica invertida para se livrar de nots

Se a permissão de argumentos no meio de uma chamada for permitida, isso poderá ser reduzido para (115 bytes)

(b:=lambda t:((max(l[0],r[0])+1,abs(l[0]-r[0])<2)if(l:=b(t[1]))[1]and(r:=b(t[2]))[1]else(0,0))if t else(0,1))(_)[1]

com _ser a árvore para verificar.

ar4093
fonte
2

JavaScript, 162 bytes

f=x=>{for(f=0,s=[[x,1]];s[0];){if(!((d=(t=s.pop())[0]).a&&d.b||f))f=t[1];if(f&&t[1]-f>1)return 0;if(d.a)s.push([d.a,t[1]+1]);if(d.b)s.push([d.b,t[1]+1])}return 1}

Experimente online!

O formato da entrada é um objeto

root={a:{node},b:{node},c:value}

Explicação

for(f=0,s=[[x,1]];s[0];){if(!((d=(t=s.pop())[0]).a&&d.b||f))f=t[1]

Ao executar a primeira pesquisa de largura, encontre a profundidade do primeiro nó em que um ou mais ramos estão ausentes.

if(f&&t[1]-f>1)return 0;if(d.a)s.push([d.a,t[1]+1]);if(d.b)s.push([d.b,t[1]+1])}

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.

return 1}

Se nenhum nó for encontrado, retorne 1

fəˈnɛtɪk
fonte
1
Provavelmente, existe uma maneira de fazer a primeira pesquisa de largura melhor, mas não consegui pensar nisso.
fənɛtɪk
1
Eu acho que isso falha em alguns casos válidos, como o primeiro exemplo, que deve ficar equilibrado quando você remove a folha 4.
214 Neil
1

Julia, 56 bytes

f(t)=t!=()&&(-(f.(t.c)...)^2<2 ? maximum(f,t.c)+1 : NaN)

Com a seguinte estrutura representando a árvore binária:

struct Tree
    c::NTuple{2,Union{Tree,Tuple{}}}
    v::Int
end

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.

user3263164
fonte
1
Supondo que a codificação seja UTF-8, na verdade, são 57 bytes devido a isso , de acordo com o contador de bytes interno do TIO . De qualquer forma, bem-vindo ao CG&CC!
String não relacionada
1
Sim, você está certo. Eu o corrigi, de modo que agora ele tenha 56 bytes
#
0

Kotlin , 67 bytes

fun N.c():Int=maxOf(l?.c()?:0,r?.c()?:0)+1
fun N.b()=l?.c()==r?.c()

Onde

data class N(val l: N? = null, val r: N? = null, val v: Int = 0)

Experimente online!

Brojowski
fonte
0

C, 117 bytes

h(T*r){r=r?1+h(h(r->l)>h(r->r)?r->l:r->r):0;}b(T*r){return r->l&&!b(r->l)||r->r&&!b(r->r)?0:abs(h(r->l)-h(r->r))<=1;}

A implementação do Struct é a seguinte:

 typedef struct T
    {
        struct T * l;

        struct T * r;

        int v;

    } T;

Experimente isso no JDoodle

T. Salim
fonte
Parece ser 117 bytes, mas você pode fazer <2a última verificação em vez disso
Jo King
Além disso, eu não sei como válida esta é, uma vez que se baseia em uma estrutura fora de dados definido da submissão
Jo Rei
0

Python 2 , 99 96 94 bytes

lambda A:A==[]or(abs(D(A[1])-D(A[2]))<2)*f(A[1])*f(A[2])
D=lambda A:A>[]and-~max(map(D,A[1:]))

Experimente online!

3 bytes de Jo King .

Recebe entrada como: nó vazio é []e outros nós são [<value>, <leftNode>, <rightNode>]. Saídas 0/1para Falso / Verdadeiro.

Chas Brown
fonte