Pour chaque nœud dans un arbre binaire équilibré, la différence maximale dans les hauteurs du sous-arbre enfant gauche et du sous-arbre enfant droit est au plus 1.

La hauteur d'un arbre binaire est la distance entre le nœud racine et le nœud enfant le plus éloigné de la racine.

Voici un exemple:

           2 <-- root: Height 1
          / \
         7   5 <-- Height 2
        / \   \
       2   6   9 <-- Height 3
          / \  /
         5  11 4 <-- Height 4 

Hauteur de l'arbre binaire: 4

Voici des arbres binaires et un rapport indiquant s'ils sont équilibrés ou non:

L'arbre ci-dessus est déséquilibré .

L'arbre ci-dessus est équilibré .

Écrivez le programme le plus court possible qui accepte en entrée la racine d'un arbre binaire et renvoie une valeur de falsey si l'arbre est déséquilibré et une valeur véridique si l'arbre est équilibré.

Contribution

La racine d'un arbre binaire. Cela peut être sous la forme d'une référence à l'objet racine ou même d'une liste qui est une représentation valide d'un arbre binaire.

Production

Renvoie une valeur véridique: si l'arbre est équilibré

Retourne la valeur de falsey: si l'arbre n'est pas équilibré.

Définition d'un arbre binaire

Un arbre est un objet qui contient une valeur et deux autres arbres ou pointeurs vers eux.

La structure de l'arbre binaire ressemble à ceci:

typedef struct T
{
   struct T *l;
   struct T *r;
   int v;
}T;

Si vous utilisez une représentation de liste pour un arbre binaire, elle peut ressembler à ceci:

[root_value, left_node, right_node]

Gelée , 11 octets

ḊµŒḊ€IỊ;߀Ạ

Essayez-le en ligne!

L'arbre vide est représenté par [].

Prolog (SWI) , 49 octets

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

Essayez-le en ligne!

Représente les arbres en tant que Value/Left_Child/Right_Child, l'arbre vide étant l'atome e. Définit +/2, qui génère un succès ou un échec, avec une variable indépendante (ou déjà égale à la hauteur de l'arborescence) à gauche et l'arborescence à droite - si l'argument hauteur est inacceptable, ajoutez 9 octets à définir -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.

Wolfram Language (Mathematica) , 50 octets

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

Utilisez Nullpour null, value[left, right]pour les nœuds. Par exemple, l'arborescence suivante s'écrit 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

Essayez-le en ligne!

Python 3.8 (pré-version) , 133 125 octets

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]

Essayez-le en ligne!

Prend un arbre au format "liste": Un nœud est [value, left, right]avec leftet rightétant des nœuds.

Appelez la fonction h.

Renvoie 0ou Falsepour un arbre déséquilibré. Renvoie 1ou Truepour un arbre équilibré.

Non golfé:

# 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: Logique inversée pour se débarrasser de nots

Si la prise d'arguments au milieu d'un appel est autorisée, cela pourrait être raccourci à (115 octets)

(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]

d' _être l'arbre à vérifier.

JavaScript (Node.js) , 49 octets

h=([l,r])=>l?(d=h(l)-h(r))*d<2?1+h(d>0?l:r):NaN:1

Essayez-le en ligne!

-9 octets par Arnauld.

JavaScript, 58 octets

h=([l,r])=>l?(l=h(l),r=h(r),m=l>r?l:r,m+m-l-r<2?m+1:NaN):1

Essayez-le en ligne!

Utilisez []pour null et [left, right, value]pour les nœuds.

JavaScript, 162 octets

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}

Essayez-le en ligne!

Le format de l'entrée est un objet

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

Explication

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

En effectuant une première recherche en largeur, trouvez la profondeur du premier nœud auquel il manque une ou plusieurs branches.

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])}

En poursuivant la première recherche de largeur, retournez zéro si un élément est plus profond de deux que la profondeur des branches manquantes du premier nœud.

return 1}

Si aucun tel nœud n'est trouvé, retournez 1

Julia, 56 octets

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

Avec la structure suivante représentant l'arbre binaire:

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

c est un tuple représentant les nœuds gauche et droit et le tuple vide () est utilisé pour signaler l'absence d'un nœud.

La valeur de Falsey est NaN, tout entier est vrai.

Kotlin , 67 octets

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

Où

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

Essayez-le en ligne!

C, 117 octets

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;}

La mise en œuvre de Struct est la suivante:

 typedef struct T
    {
        struct T * l;

        struct T * r;

        int v;

    } T;

Essayez ceci sur JDoodle

Python 2 , 99 96 94 octets

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:]))

Essayez-le en ligne!

3 octets de Jo King .

Prend l'entrée comme: le nœud vide est [], et les autres nœuds le sont [<value>, <leftNode>, <rightNode>]. Sorties 0/1pour False / True.