Schreiben Sie das kürzeste Programm, um zu überprüfen, ob ein Binärbaum ausgeglichen ist

15

Für jeden Knoten in einem ausgeglichenen Binärbaum beträgt der maximale Höhenunterschied zwischen dem linken untergeordneten Teilbaum und dem rechten untergeordneten Teilbaum höchstens 1.

Die Höhe eines Binärbaums ist der Abstand vom Wurzelknoten zum untergeordneten Knoten, der am weitesten von der Wurzel entfernt ist.

Unten ist ein Beispiel:

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

Höhe des Binärbaums: 4

Die folgenden sind Binärbäume und ein Bericht darüber, ob sie ausgeglichen sind oder nicht:

Testfall 1

Der Baum darüber ist unausgeglichen .

Testfall 2

Der obige Baum ist ausgeglichen .

Schreiben Sie das kürzestmögliche Programm, das die Wurzel eines Binärbaums als Eingabe akzeptiert und einen falschen Wert zurückgibt, wenn der Baum unausgeglichen ist, und einen wahren Wert, wenn der Baum ausgeglichen ist.

Eingang

Die Wurzel eines binären Baumes. Dies kann in Form eines Verweises auf das Stammobjekt oder sogar einer Liste erfolgen, die eine gültige Darstellung eines Binärbaums darstellt.

Ausgabe

Gibt den Wahrheitswert zurück: Wenn der Baum ausgeglichen ist

Gibt einen falschen Wert zurück: Wenn der Baum nicht ausgeglichen ist.

Definition eines binären Baumes

Ein Baum ist ein Objekt, das einen Wert und entweder zwei andere Bäume oder Zeiger darauf enthält.

Die Struktur des Binärbaums sieht ungefähr so ​​aus:

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

Wenn Sie eine Listendarstellung für einen Binärbaum verwenden, sieht diese möglicherweise folgendermaßen aus:

[root_value, left_node, right_node]
T. Salim
quelle
2
Darf die Eingabe ein leerer Baum sein?
6.
1
Wenn Sie in Ihrem ersten Beispiel eines Baumes das Blatt entfernen 4, ist der verbleibende Baum ausgeglichen?
Neil
Nein, nicht dieses Beispiel, ich meinte das erste mit ASCII-Kunst.
Neil
Nach meiner eigenen Implementierung "C, 117 Bytes": Nein, da die Höhe des rechten Unterarmbaums ab "5" 2 und die Höhe des linken Unterarmbaums 0 beträgt.
T. Salim
Die Bearbeitungen müssen aus mindestens 6 Zeichen bestehen. Entfernen Sie jedoch das Komma zwischen "Ausgeglichen" und "Binär" - "Binärbaum" ist eine Nominalphrase. Die Angabe "Ausgeglichener Binärbaum" entspricht also "Rot, Schneemobil" Komma ist nicht erforderlich.
Geza Kerecsenyi

Antworten:

8

Jelly , 11 Bytes

ḊµŒḊ€IỊ;߀Ạ

Probieren Sie es online!

Der leere Baum wird durch dargestellt [].

Erik der Outgolfer
quelle
Vielen Dank an Erik, dass er zu den Ersten gehört, die diese Frage beantwortet haben. Jelly ist sicherlich eine sehr beliebte Sprache auf dieser Seite. Ich denke, ich sollte mir die Freiheit nehmen, diese Sprache zu implementieren. Gut, aus einer soliden Golf-Skriptsprache zu lernen.
T. Salim
Herzlichen Glückwunsch Erik der Outgolfer, Sie sind Sieger.
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.

Probieren Sie es online!

Stellt Bäume als dar Value/Left_Child/Right_Child, wobei der leere Baum das Atom ist e. Definiert +/2, welche Ergebnisse durch Erfolg oder Misserfolg ausgegeben werden , wobei sich links eine ungebundene Variable (oder eine Variable, die bereits der Höhe des Baums entspricht) und rechts der Baum befinden. Wenn das Argument height nicht akzeptabel ist, fügen Sie 9 Bytes zur Definition hinzu -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.
Nicht verwandte Zeichenfolge
quelle
(Wenn der Wert jedes Knotens in der Eingabe weggelassen werden _/könnte , könnte er für -2 Byte herausgenommen werden.)
Nicht verwandte
3

Wolfram Language (Mathematica) , 50 Byte

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

Verwenden Sie Nullfür null value[left, right]für Knoten. Beispielsweise wird der folgende Baum als geschrieben 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

Probieren Sie es online!

Alephalpha
quelle
Das ist wirklich hübsch!
Greg Martin
3

Python 3.8 (Vorabversion) , 133 bis 125 Byte

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]

Probieren Sie es online!

Nimmt einen Baum im "Listen" -Format: Ein Knoten ist [value, left, right]mit leftund rightals Knoten.

Rufen Sie die Funktion auf h.

Gibt 0oder Falsefür einen unausgeglichenen Baum zurück. Gibt 1oder Truefür einen ausgeglichenen Baum zurück.

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: Umgekehrte Logik, um nots loszuwerden

Wenn die Übernahme von Argumenten in der Mitte eines Aufrufs zulässig ist, kann dies auf (115 Byte) verkürzt werden.

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

mit _ dem Baum zu überprüfen.

ar4093
quelle
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}

Probieren Sie es online!

Das Format der Eingabe ist ein Objekt

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

Erläuterung

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

Wenn Sie eine Breitensuche durchführen, ermitteln Sie die Tiefe des ersten Knotens, dem ein oder mehrere Zweige fehlen.

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

Setzen Sie die breiteste erste Suche fort und geben Sie Null zurück, wenn ein Element zwei tiefer ist als die Tiefe des ersten Knotens, in dem Verzweigungen fehlen.

return 1}

Wenn kein solcher Knoten gefunden wird, geben Sie 1 zurück

fəˈnəˈtɛk
quelle
1
Es gibt wahrscheinlich eine Möglichkeit, die erste Suche in der Breite zu verbessern, aber ich konnte mir nichts dabei vorstellen.
5.
1
Ich denke, dass dies für einige gültige Fälle wie das allererste Beispiel, das ausgeglichen werden sollte, wenn Sie das Blatt entfernen, fehlschlägt 4.
Neil
1

Julia, 56 Bytes

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

Mit der folgenden Struktur, die den Binärbaum darstellt:

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

cist ein Tupel, das den linken und den rechten Knoten darstellt, und das leere Tupel ()wird verwendet, um die Abwesenheit eines Knotens anzuzeigen.

Falscher Wert ist NaN, jede ganze Zahl ist wahr.

user3263164
quelle
1
Unter der Annahme, dass die Codierung UTF-8 ist, sind dies aufgrund des integrierten Byte-Zählers von TIO tatsächlich 57 Byte . Wie auch immer, herzlich willkommen bei CG & CC!
Nicht verwandte
1
Ja, du hast Recht. Ich habe es korrigiert, so dass es jetzt tatsächlich 56 Bytes sind
user3263164
0

Kotlin , 67 Bytes

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

Wo

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

Probieren Sie es online!

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

Strukturelle Implementierung ist die folgende:

 typedef struct T
    {
        struct T * l;

        struct T * r;

        int v;

    } T;

Versuchen Sie dies auf JDoodle

T. Salim
quelle
Dies scheint 117 Bytes zu sein, obwohl Sie dies <2stattdessen für die letzte Überprüfung tun können
Jo King,
Ich bin mir auch nicht sicher, wie gültig dies ist, da es sich auf eine Datenstruktur stützt, die außerhalb der
Jo King,
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:]))

Probieren Sie es online!

3 Bytes von Jo King .

Nimmt die Eingabe als: leerer Knoten ist [], und andere Knoten sind [<value>, <leftNode>, <rightNode>]. Ausgänge 0/1für False / True.

Chas Brown
quelle