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]
4
, pozostałe drzewo jest zrównoważone?Odpowiedzi:
Galaretka , 11 bajtów
Wypróbuj online!
Puste drzewo jest reprezentowane przez
[]
.źródło
Prolog (SWI) , 49 bajtów
Wypróbuj online!
Reprezentuje drzewa jako
Value/Left_Child/Right_Child
, przy czym puste drzewo jest atomeme
. 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.
.źródło
_/
można ją wyjąć dla -2 bajtów.)Wolfram Language (Mathematica) , 50 bajtów
Użyj
Null
dla null,value[left, right]
dla węzłów. Na przykład następujące drzewo jest zapisane jako2[7[2[Null, Null], 6[5[Null, Null], 11[Null, Null]]], 5[Null, 9[4[Null, Null], Null]]]
.Wypróbuj online!
źródło
Python 3.8 (wersja wstępna) ,
133125 bajtówWypróbuj online!
Staje drzewa w formacie „liście”: Węzeł jest
[value, left, right]
zleft
iright
będące węzłami.Wywołaj funkcję
h
.Zwraca
0
lubFalse
dla niezrównoważonego drzewa. Zwraca1
lubTrue
dla zrównoważonego drzewa.Nie golfowany:
-10: Odwrócona logika, aby pozbyć się
not
sJeśli dozwolone jest przyjmowanie argumentów w trakcie połączenia, można je skrócić do (115 bajtów)
z
_
byciem drzewem do sprawdzenia.źródło
JavaScript (Node.js) , 49 bajtów
Wypróbuj online!
-9 bajtów autorstwa Arnaulda.
JavaScript, 58 bajtów
Wypróbuj online!
Użyj
[]
dla null i[left, right, value]
dla węzłów.źródło
JavaScript, 162 bajty
Wypróbuj online!
Format danych wejściowych jest obiektem
Wyjaśnienie
Wykonując pierwsze wyszukiwanie szerokości, znajdź głębokość pierwszego węzła, w którym brakuje jednej lub więcej gałęzi.
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.
Jeśli nie znaleziono takiego węzła, zwróć 1
źródło
4
.Julia, 56 bajtów
Z następującą strukturą reprezentującą drzewo binarne:
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.źródło
≢
, zgodnie z wbudowanym licznikiem bajtów TIO . W każdym razie witamy w CG&CC!Kotlin , 67 bajtów
Gdzie
Wypróbuj online!
źródło
C, 117 bajtów
Implementacja struktury jest następująca:
Wypróbuj to na JDoodle
źródło
<2
zamiast tego możesz zrobić to ostatnie sprawdzeniePython 2 ,
999694 bajtówWypró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ściowe0/1
dla False / True.źródło