Napisz najkrótszy program, aby sprawdzić, czy drzewo binarne jest zrównoważone

15

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:

Przypadek testowy 1

Drzewo powyżej jest niezrównoważone .

Przypadek testowy 2

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]
T. Salim
źródło
2
Czy dane wejściowe mogą być pustym drzewem?
tsh
1
Czy w początkowym przykładzie drzewa, jeśli usuniesz liść 4, pozostałe drzewo jest zrównoważone?
Neil,
Nie, nie ten przykład, miałem na myśli ten początkowy, wykorzystujący sztukę ASCII.
Neil,
Zgodnie z moją własną implementacją „C, 117 bajtów”: Nie, ponieważ wysokość prawego drzewa przedramionowego rozpoczynającego się od „5” wynosi 2, a wysokość lewego drzewa przedramionowego wynosi 0
T. Salim
Edycja zawiera co najmniej 6 znaków, ale proszę usunąć przecinek między „zrównoważonym” a „binarnym” - „drzewo binarne” to fraza rzeczownikowa, więc pisanie „zrównoważonego, binarnego drzewa” jest odpowiednikiem „czerwonego, śnieżnego telefonu” - przecinek nie jest wymagany.
Geza Kerecsenyi

Odpowiedzi:

8

Galaretka , 11 bajtów

ḊµŒḊ€IỊ;߀Ạ

Wypróbuj online!

Puste drzewo jest reprezentowane przez [].

Erik the Outgolfer
źródło
Dziękujemy Erikowi za to, że jako pierwszy odpowiedział na to pytanie. Jelly z pewnością jest bardzo popularnym językiem na tej stronie. Myślę, że powinienem skorzystać z możliwości wdrożenia tego języka. Dobrze jest uczyć się z solidnego języka skryptowego do gry w golfa.
T. Salim,
Gratulacje Erik the Outgolfer, jesteś zwycięzcą.
T. Salim,
3

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.
Niepowiązany ciąg
źródło
(Jeśli wartość każdego węzła można pominąć na wejściu, _/można ją wyjąć dla -2 bajtów.)
Niepowiązany ciąg
3

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!

alephalpha
źródło
To naprawdę ładne!
Greg Martin
3

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.

ar4093
źródło
2

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

Fəˈnɛtɪk
źródło
1
Prawdopodobnie jest jakiś sposób, aby lepiej przeprowadzić pierwsze wyszukiwanie, ale nie mogłem o tym myśleć.
fəˈnɛtɪk
1
Myślę, że to się nie udaje w niektórych ważnych przypadkach, takich jak pierwszy przykład, który powinien się wyrównać po usunięciu liścia 4.
Neil,
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.

użytkownik3263164
źródło
1
Zakładając, że kodowanie to UTF-8, w rzeczywistości jest to 57 bajtów z powodu , zgodnie z wbudowanym licznikiem bajtów TIO . W każdym razie witamy w CG&CC!
Niepowiązany ciąg
1
Tak, masz rację. Poprawiłem to, tak że teraz ma 56 bajtów
user3263164,
0

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!

Brojowski
źródło
0

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

T. Salim
źródło
Wydaje się, że to 117 bajtów, ale <2zamiast tego możesz zrobić to ostatnie sprawdzenie
Jo King
Nie jestem też pewien, czy jest to poprawne, ponieważ opiera się ono na strukturze danych zdefiniowanej poza przesłaniem
Jo King
0

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.

Chas Brown
źródło