Dla każdego węzła w zrównoważonym drzewie binarnym maksymalna różnica wysokości w lewym poddrzewie i prawym poddrzewie wynosi co najwyżej 1.

Wysokość drzewa binarnego to odległość od węzła głównego do potomka węzła, który jest najdalej od korzenia.

Poniżej znajduje się przykład:

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

Wysokość drzewa binarnego: 4

Poniżej przedstawiono drzewa binarne i raport o tym, czy są one zrównoważone:

Drzewo powyżej jest niezrównoważone .

Powyższe drzewo jest zrównoważone .

Napisz najkrótszy możliwy program, który przyjmuje jako dane wejściowe korzeń drzewa binarnego i zwraca wartość falsey, jeśli drzewo jest niezrównoważone, oraz wartość prawdy, jeśli drzewo jest zrównoważone.

Wejście

Korzeń drzewa binarnego. Może to mieć postać odwołania do obiektu głównego lub nawet listy, która jest prawidłową reprezentacją drzewa binarnego.

Wynik

Zwraca prawdziwą wartość: Jeśli drzewo jest zrównoważone

Zwraca wartość falsey: Jeśli drzewo nie jest zrównoważone.

Definicja drzewa binarnego

Drzewo to obiekt zawierający wartość oraz dwa inne drzewa lub wskaźniki do nich.

Struktura drzewa binarnego wygląda mniej więcej tak:

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

Jeśli używasz reprezentacji listy dla drzewa binarnego, może to wyglądać mniej więcej tak:

[root_value, left_node, right_node]

Galaretka , 11 bajtów

ḊµŒḊ€IỊ;߀Ạ

Wypróbuj online!

Puste drzewo jest reprezentowane przez [].

Prolog (SWI) , 49 bajtów

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

Wypróbuj online!

Reprezentuje drzewa jako Value/Left_Child/Right_Child, przy czym puste drzewo jest atomem e. Definiuje +/2, które dane wyjściowe są wynikiem sukcesu lub niepowodzenia, z niezwiązaną zmienną (lub taką, która jest już równa wysokości drzewa) po lewej stronie i drzewem po prawej stronie - jeśli argument wysokości jest niedopuszczalny, dodaj 9 bajtów do zdefiniowania -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 bajtów

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

Użyj Nulldla null, value[left, right]dla węzłów. Na przykład następujące drzewo jest zapisane jako 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

Wypróbuj online!

Python 3.8 (wersja wstępna) , 133 125 bajtów

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]

Wypróbuj online!

Staje drzewa w formacie „liście”: Węzeł jest [value, left, right]z lefti rightbędące węzłami.

Wywołaj funkcję h.

Zwraca 0lub Falsedla niezrównoważonego drzewa. Zwraca 1lub Truedla zrównoważonego drzewa.

Nie golfowany:

# 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: Odwrócona logika, aby pozbyć się nots

Jeśli dozwolone jest przyjmowanie argumentów w trakcie połączenia, można je skrócić do (115 bajtów)

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

z _byciem drzewem do sprawdzenia.

JavaScript (Node.js) , 49 bajtów

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

Wypróbuj online!

-9 bajtów autorstwa Arnaulda.

JavaScript, 58 bajtów

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

Wypróbuj online!

Użyj []dla null i [left, right, value]dla węzłów.

JavaScript, 162 bajty

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}

Wypróbuj online!

Format danych wejściowych jest obiektem

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

Wyjaśnienie

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

Wykonując pierwsze wyszukiwanie szerokości, znajdź głębokość pierwszego węzła, w którym brakuje jednej lub więcej gałęzi.

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

Kontynuując szerokość pierwszego wyszukiwania, zwróć zero, jeśli jakikolwiek element jest dwa głębszy niż głębokość brakujących gałęzi pierwszego węzła.

return 1}

Jeśli nie znaleziono takiego węzła, zwróć 1

Julia, 56 bajtów

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

Z następującą strukturą reprezentującą drzewo binarne:

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

c to krotka reprezentująca lewy i prawy węzeł oraz pusta krotka () służy do sygnalizowania braku węzła.

Wartość Falsey jest taka NaN, że każda liczba całkowita jest prawdziwa.

Kotlin , 67 bajtów

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

Gdzie

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

Wypróbuj online!

C, 117 bajtów

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

Implementacja struktury jest następująca:

 typedef struct T
    {
        struct T * l;

        struct T * r;

        int v;

    } T;

Wypróbuj to na JDoodle

Python 2 , 99 96 94 bajtów

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

Wypróbuj online!

3 bajty od Jo King .

Pobiera dane wejściowe jako: pusty węzeł jest [], a inne węzły są [<value>, <leftNode>, <rightNode>]. Dane wyjściowe 0/1dla False / True.