Wie kann festgestellt werden, ob der Binärbaum ausgeglichen ist?

113

Es ist eine Weile her von diesen Schuljahren. Ich habe einen Job als IT-Spezialist in einem Krankenhaus bekommen. Ich versuche mich jetzt zu bewegen, um etwas zu programmieren. Ich arbeite jetzt an binären Bäumen und habe mich gefragt, wie ich am besten feststellen kann, ob der Baum in der Höhe ausgeglichen ist.

Ich dachte an etwas dabei:

public boolean isBalanced(Node root){
    if(root==null){
        return true;  //tree is empty
    }
    else{
        int lh = root.left.height();
        int rh = root.right.height();
        if(lh - rh > 1 || rh - lh > 1){
            return false;
        }
    }
    return true;
}

Ist das eine gute Implementierung? oder fehlt mir etwas

user69514
quelle
Wenn Sie den ASCII-Binärbaum von Donal Fellows mit einer Grafik sehen möchten
user7643681
1
Gute Antwort, hat mir geholfen, in die USA zu kommen. (Witze)
Henry

Antworten:

165

Stolperte über diese alte Frage, während ich nach etwas anderem suchte. Ich stelle fest, dass Sie nie eine vollständige Antwort erhalten haben.

Um dieses Problem zu lösen, schreiben Sie zunächst eine Spezifikation für die Funktion, die Sie schreiben möchten.

Spezifikation: Ein wohlgeformter Binärbaum wird als "höhenausgeglichen" bezeichnet, wenn (1) er leer ist oder (2) seine linken und rechten untergeordneten Elemente höhenausgeglichen sind und die Höhe des linken Baums innerhalb von 1 liegt Höhe des rechten Baumes.

Nachdem Sie die Spezifikation haben, ist der Code trivial zu schreiben. Folgen Sie einfach der Spezifikation:

IsHeightBalanced(tree)
    return (tree is empty) or 
           (IsHeightBalanced(tree.left) and
            IsHeightBalanced(tree.right) and
            abs(Height(tree.left) - Height(tree.right)) <= 1)

Die Übersetzung in die Programmiersprache Ihrer Wahl sollte trivial sein.

Bonusübung : Diese naive Codeskizze durchläuft den Baum bei der Berechnung der Höhen viel zu oft. Können Sie es effizienter machen?

Super Bonus Übung : Angenommen, der Baum ist massiv unausgeglichen. Eine Million Knoten tief auf der einen Seite und drei tief auf der anderen Seite. Gibt es ein Szenario, in dem dieser Algorithmus den Stapel sprengt? Können Sie die Implementierung so korrigieren, dass sie den Stapel niemals sprengt, selbst wenn ein massiv unausgeglichener Baum angegeben wird?

UPDATE : Donal Fellows weist in seiner Antwort darauf hin, dass es verschiedene Definitionen von "ausgewogen" gibt, die man wählen könnte. Zum Beispiel könnte man eine strengere Definition von "höhenausgeglichen" nehmen und verlangen, dass die Pfadlänge zum nächsten leeren Kind innerhalb eines der Pfade zum am weitesten leeren Kind liegt. Meine Definition ist weniger streng und lässt daher mehr Bäume zu.

Man kann auch weniger streng sein als meine Definition; Man könnte sagen, dass ein ausgeglichener Baum einer ist, bei dem sich die maximale Pfadlänge zu einem leeren Baum in jedem Zweig um nicht mehr als zwei oder drei oder eine andere Konstante unterscheidet. Oder dass die maximale Pfadlänge ein Bruchteil der minimalen Pfadlänge ist, wie ein halbes oder ein Viertel.

Normalerweise spielt es keine Rolle. Der Sinn eines Baumausgleichsalgorithmus besteht darin, sicherzustellen, dass Sie nicht in der Situation landen, in der Sie eine Million Knoten auf der einen und drei auf der anderen Seite haben. Donals Definition ist theoretisch in Ordnung, aber in der Praxis ist es ein Schmerz, einen Baumausgleichsalgorithmus zu entwickeln, der diese Strenge erfüllt. Die Leistungseinsparungen rechtfertigen normalerweise nicht die Implementierungskosten. Sie verbringen viel Zeit damit, unnötige Baumumlagerungen vorzunehmen, um ein Gleichgewicht zu erreichen, das in der Praxis kaum einen Unterschied macht. Wen kümmert es, wenn manchmal vierzig Äste benötigt werden, um zum entferntesten Blatt in einem unvollständig ausbalancierten Baum mit Millionen Knoten zu gelangen, wenn es in einem perfekt ausbalancierten Baum theoretisch nur zwanzig dauern könnte? Der Punkt ist, dass es nie eine Million braucht. Es ist normalerweise gut genug, von einem schlimmsten Fall von einer Million auf einen schlimmsten Fall von vierzig zu kommen. Sie müssen nicht bis zum optimalen Fall gehen.

Eric Lippert
quelle
19
+1 für nur richtige Antwort, ich kann nicht glauben, dass niemand in der Lage war, dies für 8 Monate zu beantworten ...
BlueRaja - Danny Pflughoeft
1
Antwort auf die "Übungen" unten ...
Potatoswatter
Beantwortete Bonusübung unten.
Brian
Die Antwort von sdk unten scheint richtig zu sein und führt nur 2 Baumdurchquerungen durch, ebenso wie O (n). Wenn ich nichts vermisse, löst das nicht zumindest Ihre erste Bonusfrage. Sie können natürlich auch dynamische Programmierung und Ihre Lösung verwenden, um Zwischenhöhen zwischenzuspeichern
Aly
Theoretisch müsste ich mich immer noch auf die Seite der Definition von Donal Fellows stellen.
Dhruv Gairola
26

Balance ist eine wirklich subtile Eigenschaft; Sie denken, Sie wissen, was es ist, aber es ist so leicht, sich zu irren. Insbesondere ist sogar Eric Lipperts (gute) Antwort falsch. Das liegt daran, dass der Begriff der Höhe nicht ausreicht. Sie müssen das Konzept der minimalen und maximalen Höhe eines Baumes haben (wobei die minimale Höhe die geringste Anzahl von Schritten von der Wurzel bis zum Blatt ist und die maximale ... gut, Sie erhalten das Bild). In Anbetracht dessen können wir das Gleichgewicht wie folgt definieren:

Ein Baum, bei dem die maximale Höhe eines Zweigs nicht mehr als eins mehr als die minimale Höhe eines Zweigs beträgt.

(Dies bedeutet tatsächlich, dass die Zweige selbst ausgeglichen sind. Sie können denselben Zweig sowohl für das Maximum als auch für das Minimum auswählen.)

Alles, was Sie tun müssen, um diese Eigenschaft zu überprüfen, ist eine einfache Baumdurchquerung, die die aktuelle Tiefe verfolgt. Wenn Sie das erste Mal zurückverfolgen, erhalten Sie eine Basistiefe. Jedes Mal, wenn Sie danach zurückgehen, vergleichen Sie die neue Tiefe mit der Grundlinie

  • Wenn es gleich der Grundlinie ist, fahren Sie einfach fort
  • Wenn es mehr als einen Unterschied gibt, ist der Baum nicht ausgeglichen
  • Wenn es einmalig ist, kennen Sie jetzt den Bereich für das Gleichgewicht, und alle nachfolgenden Tiefen (wenn Sie zurückverfolgen möchten) müssen entweder der erste oder der zweite Wert sein.

In Code:

class Tree {
    Tree left, right;
    static interface Observer {
        public void before();
        public void after();
        public boolean end();
    }
    static boolean traverse(Tree t, Observer o) {
        if (t == null) {
            return o.end();
        } else {
            o.before();
            try {
                if (traverse(left, o))
                    return traverse(right, o);
                return false;
            } finally {
                o.after();
            }
        }
    }
    boolean balanced() {
        final Integer[] heights = new Integer[2];
        return traverse(this, new Observer() {
            int h;
            public void before() { h++; }
            public void after() { h--; }
            public boolean end() {
                if (heights[0] == null) {
                    heights[0] = h;
                } else if (Math.abs(heights[0] - h) > 1) {
                    return false;
                } else if (heights[0] != h) {
                    if (heights[1] == null) {
                        heights[1] = h;
                    } else if (heights[1] != h) {
                        return false;
                    }
                }
                return true;
            }
        });
    }
}

Ich nehme an, Sie könnten dies tun, ohne das Observer-Muster zu verwenden, aber ich finde es einfacher, auf diese Weise zu argumentieren.


[BEARBEITEN]: Warum Sie nicht einfach die Höhe jeder Seite nehmen können. Betrachten Sie diesen Baum:

        /\
       /  \
      /    \
     /      \_____
    /\      /     \_
   /  \    /      / \
  /\   C  /\     /   \
 /  \    /  \   /\   /\
A    B  D    E F  G H  J

OK, ein bisschen chaotisch, aber jede Seite der Wurzel ausgeglichen wird: Cwird Tiefe 2, A, B, D, Eist , Tiefe 3, und F, G, H, Jist Tiefe 4. Die Höhe des linken Zweiges 2 ( zur Erinnerung , die Höhe nimmt ab , wenn man traverse der Ast), die Höhe des rechten Astes beträgt 3. Der Gesamtbaum ist jedoch nicht ausgeglichen, da zwischen Cund ein Höhenunterschied von 2 besteht F. Sie benötigen eine Minimax-Spezifikation (obwohl der tatsächliche Algorithmus weniger komplex sein kann, da nur zwei zulässige Höhen vorhanden sein sollten).

Donal Fellows
quelle
Ah, guter Punkt. Sie könnten einen Baum haben, der h (LL) = 4, h (LR) = 3, h (RL) = 3, h (RR) = 2 ist. Somit ist h (L) = 4 und h (R) = 3, so dass es für den früheren Algorithmus ausgeglichen erscheint, aber bei einer maximalen / minimalen Tiefe von 4/2 ist dies nicht ausgeglichen. Dies wäre bei einem Bild wahrscheinlich sinnvoller.
Tim
1
Das habe ich gerade hinzugefügt (mit dem fiesesten ASCII-Grafikbaum der Welt).
Donal Fellows
@DonalFellows: Sie erwähnt die Höhe des linken Arms ist 2. aber der linke Zweig hat 4 Knoten einschließlich der Wurzel und Blatt A. Die Höhe 3 richtig in diesem Fall sein wird
Gehirn Sturm
22

Dies bestimmt nur, ob die oberste Ebene des Baums ausgeglichen ist. Das heißt, Sie könnten einen Baum mit zwei langen Ästen ganz links und ganz rechts haben, mit nichts in der Mitte, und dies würde wahr zurückkehren. Sie müssen die rekursiv überprüfen root.leftund prüfen root.right, ob sie auch intern ausgeglichen sind, bevor Sie true zurückgeben.

Jesse Rusak
quelle
Wenn der Code jedoch eine Max- und Min-Höhenmethode hätte, wäre er, wenn er global ausgeglichen ist, auch lokal ausgeglichen.
Ari
22

Bonus Übungsantwort. Die einfache Lösung. Offensichtlich könnte man in einer realen Implementierung dies oder etwas einschließen, um zu vermeiden, dass der Benutzer die Höhe in seine Antwort einbeziehen muss.

IsHeightBalanced(tree, out height)
    if (tree is empty)
        height = 0
        return true
    balance = IsHeightBalanced(tree.left, heightleft) and IsHeightBalanced(tree.right, heightright)
    height = max(heightleft, heightright)+1
    return balance and abs(heightleft - heightright) <= 1     
Brian
quelle
Wenn der Baum größer als einige hundert Ebenen ist, wird eine Stackoverflow-Ausnahme angezeigt. Sie haben es effizient gemacht, aber es verarbeitet keine mittleren oder großen Datensätze.
Eric Leschinski
Ist das ein Pseudocode, den Sie gerade erfunden haben, oder ist es eine echte Sprache? (Ich meine die " out height" variable Notation)
Kap
@kap: Dies ist ein Pseudocode, aber die Out-Syntax stammt aus C #. Grundsätzlich bedeutet dies, dass der Parameter von der aufgerufenen Funktion zum Aufrufer wechselt (im Gegensatz zu Standardparametern, die vom Aufrufer zur aufgerufenen Funktion übertragen werden, oder zu ref-Parametern, die vom Aufrufer zur aufgerufenen Funktion und zurück übertragen werden). Dadurch können Funktionen effektiv mehr als einen Wert zurückgeben.
Brian
20

Nachbestellungslösung, den Baum nur einmal durchlaufen. Die zeitliche Komplexität ist O (n), der Raum ist O (1), es ist besser als eine Top-Down-Lösung. Ich gebe Ihnen eine Java-Version Implementierung.

public static <T> boolean isBalanced(TreeNode<T> root){
    return checkBalance(root) != -1;
}

private static <T> int checkBalance(TreeNode<T> node){
    if(node == null) return 0;
    int left = checkBalance(node.getLeft());

    if(left == -1) return -1;

    int right = checkBalance(node.getRight());

    if(right == -1) return -1;

    if(Math.abs(left - right) > 1){
        return -1;
    }else{
        return 1 + Math.max(left, right);
    }
}
Jiaji Li
quelle
4
schöne Lösung, aber die Raumkomplexität sollte O (H) sein, wobei H die Höhe des Baumes ist. Dies liegt an der Stapelzuweisung für die Rekursion.
Legrass
Was heißt left == -1das Wann würde das jemals der Fall sein? Nehmen wir an, dass der rekursive Aufruf impliziert, dass dies left == -1wahr ist, wenn alle Teilbäume der linken Kinder unausgeglichen sind?
Aspen
left == 1bedeutet, dass der linke Teilbaum nicht ausgeglichen ist, dann ist der gesamte Baum nicht ausgeglichen. Wir müssen den richtigen Teilbaum nicht mehr überprüfen und können zurückkehren -1.
tning
Die zeitliche Komplexität ist O (n), da Sie alle Elemente durchgehen müssen. Und wenn Sie x Knoten hatten und es y Zeit braucht, um das Gleichgewicht zu überprüfen; Wenn Sie 2x Knoten hatten, dauert es 2y Zeit, um das Gleichgewicht zu überprüfen. Das klingt alles richtig?
Jack
Nun Erklärung mit Zeichnung ist hier: algorithm.tutorialhorizon.com/…
Shir
15

Die Definition eines höhenausgeglichenen Binärbaums lautet:

Binärer Baum, in dem sich die Höhe der beiden Teilbäume jedes Knotens nie um mehr als 1 unterscheidet.

Ein leerer Binärbaum ist also immer höhenausgeglichen.
Ein nicht leerer Binärbaum ist höhenausgeglichen, wenn:

  1. Sein linker Teilbaum ist höhenausgeglichen.
  2. Sein rechter Teilbaum ist höhenausgeglichen.
  3. Der Unterschied zwischen den Höhen des linken und rechten Teilbaums ist nicht größer als 1.

Betrachten Sie den Baum:

    A
     \ 
      B
     / \
    C   D

Wie zu sehen ist, ist der linke Teilbaum von Ahöhenausgeglichen (da er leer ist), ebenso wie der rechte Teilbaum. Der Baum ist jedoch immer noch nicht höhenausgeglichen, da Bedingung 3 nicht erfüllt ist, da die Höhe des linken Teilbaums 0und die Höhe des rechten Teilbaums gleich ist 2.

Auch der folgende Baum ist nicht höhenausgeglichen, obwohl die Höhe des linken und rechten Unterbaums gleich ist. Ihr vorhandener Code gibt dafür true zurück.

       A
     /  \ 
    B    C
   /      \
  D        G
 /          \
E            H

Das Wort jeder im Def ist also sehr wichtig.

Das wird funktionieren:

int height(treeNodePtr root) {
        return (!root) ? 0: 1 + MAX(height(root->left),height(root->right));
}

bool isHeightBalanced(treeNodePtr root) {
        return (root == NULL) ||
                (isHeightBalanced(root->left) &&
                isHeightBalanced(root->right) &&
                abs(height(root->left) - height(root->right)) <=1);
}

Ideone Link

Codaddict
quelle
Diese Antwort hat mir sehr geholfen. Ich fand jedoch, dass der kostenlose [MIT-Einführung in Algorithmen-Kurs] Bedingung 3 zu widersprechen scheint. Seite 4 zeigt einen RB-Baum, in dem die Höhe des linken Zweigs 2 und des rechten Zweigs 4 beträgt. Können Sie mir eine Klarstellung geben? Vielleicht verstehe ich die Definition eines Teilbaums nicht. [1]: ocw.mit.edu/courses/electrical-engineering-and-computer-science/…
i8abug
Der Unterschied scheint sich aus dieser Definition in den Kursnotizen zu ergeben. Alle einfachen Pfade von einem Knoten x zu einem Nachkommenblatt haben die gleiche Anzahl schwarzer Knoten = schwarze Höhe (x)
i8abug
Um dies weiterzuverfolgen, habe ich eine Definition gefunden, die Punkt (3) in Ihrer Antwort auf "Jedes Blatt ist nicht mehr als einen bestimmten Abstand von der Wurzel entfernt als jedes andere Blatt" ändert. Dies scheint beide Fälle zu befriedigen. Hier ist der Link von einer zufälligen
Kursware
8

Ob der Binärbaum ausgeglichen ist oder nicht, kann durch Durchlaufen der Ebenenreihenfolge überprüft werden:

private boolean isLeaf(TreeNode root) {
    if (root.left == null && root.right == null)
        return true;
    return false;
}

private boolean isBalanced(TreeNode root) {
    if (root == null)
        return true;
    Vector<TreeNode> queue = new Vector<TreeNode>();
    int level = 1, minLevel = Integer.MAX_VALUE, maxLevel = Integer.MIN_VALUE;
    queue.add(root);
    while (!queue.isEmpty()) {
        int elementCount = queue.size();
        while (elementCount > 0) {
            TreeNode node = queue.remove(0);
            if (isLeaf(node)) {
                if (minLevel > level)
                    minLevel = level;
                if (maxLevel < level)
                    maxLevel = level;
            } else {
                if (node.left != null)
                    queue.add(node.left);
                if (node.right != null)
                    queue.add(node.right);
            }
            elementCount--;
        }
        if (abs(maxLevel - minLevel) > 1) {
            return false;
        }
        level++;
    }

    return true;
}
Glücklich
quelle
1
Hervorragende Antwort. Ich denke, es erfüllt alle Anforderungen, die Eric in Bezug auf Bonus und Super-Bonus gestellt hat. Es ist iterativ (unter Verwendung einer Warteschlange) und nicht rekursiv - so wird der Aufrufstapel nicht überlaufen und wir verschieben alle Speicherprobleme auf den Heap. Es ist nicht einmal erforderlich, den gesamten Baum zu durchqueren. Es bewegt sich Level für Level. Wenn ein Baum also stark unausgeglichen zu einer Seite ist, wird er ihn sehr bald finden (am frühesten? Gut früher als die meisten rekursiven Algorithmen, obwohl Sie einen iterativen Traversal-Algorithmus nach der Bestellung implementieren könnten, der das letzte Level findet Ungleichgewichte früher, aber auf den ersten Ebenen schlechter). Also +1 :-)
David Refaeli
7

Dies wird viel komplizierter als es tatsächlich ist.

Der Algorithmus ist wie folgt:

  1. Sei A = Tiefe des Knotens der höchsten Ebene
  2. Sei B = Tiefe des Knotens der untersten Ebene

  3. Wenn abs (AB) <= 1 ist, ist der Baum ausgeglichen

Mike
quelle
Einfach und gerade!
Wasim Thabraze
3
Zwei Probleme, es ist nicht so effizient wie es sein könnte, Sie machen zwei Durchgänge über den gesamten Baum. Und für Bäume, die einen Knoten links und Tausende rechts haben, gehen Sie unnötigerweise durch das Ganze, wenn Sie nach drei Überprüfungen hätten anhalten können.
Eric Leschinski
5

Was ausgewogen bedeutet, hängt ein wenig von der jeweiligen Struktur ab. Zum Beispiel kann ein B-Baum keine Knoten mehr als eine bestimmte Tiefe von der Wurzel haben, oder weniger, alle Daten leben in einer festen Tiefe von der Wurzel, aber es kann aus dem Gleichgewicht geraten, wenn die Verteilung von Blättern zu Blättern -aber-ein Knoten ist ungleichmäßig. Überspringlisten Haben Sie überhaupt keine Ahnung von Balance, sondern verlassen Sie sich stattdessen auf die Wahrscheinlichkeit, eine anständige Leistung zu erzielen. Fibonacci-Bäume geraten absichtlich aus dem Gleichgewicht und verschieben das Gleichgewicht, um im Gegenzug für gelegentlich längere Aktualisierungen eine überlegene asymptotische Leistung zu erzielen. AVL- und Rot-Schwarz-Bäume fügen jedem Knoten Metadaten hinzu, um eine Invariante für das Tiefengleichgewicht zu erzielen.

Alle diese Strukturen und mehr sind in den Standardbibliotheken der meisten gängigen Programmiersysteme (außer Python, RAGE!) Vorhanden. Das Implementieren von einem oder zwei ist eine gute Programmierpraxis, aber es ist wahrscheinlich keine gute Zeit, um Ihre eigenen für die Produktion zu rollen, es sei denn, Ihr Problem weist eine besondere Leistung auf, die von keiner Standardkollektion erfüllt werden muss.

SingleNegationElimination
quelle
4

Hinweis 1: Die Höhe eines Teilbaums wird nur einmal berechnet.

Anmerkung 2: Wenn der linke Teilbaum nicht ausgeglichen ist, wird die Berechnung des rechten Teilbaums, der möglicherweise Millionen Elemente enthält, übersprungen.

// return height of tree rooted at "tn" if, and only if, it is a balanced subtree
// else return -1
int maxHeight( TreeNode const * tn ) {
    if( tn ) {
        int const lh = maxHeight( tn->left );
        if( lh == -1 ) return -1;
        int const rh = maxHeight( tn->right );
        if( rh == -1 ) return -1;
        if( abs( lh - rh ) > 1 ) return -1;
        return 1 + max( lh, rh );
    }
    return 0;
}

bool isBalanced( TreeNode const * root ) {
    // Unless the maxHeight is -1, the subtree under "root" is balanced
    return maxHeight( root ) != -1;
}
Arun
quelle
3

Das Ausbalancieren hängt normalerweise von der Länge des längsten Pfades in jeder Richtung ab. Der obige Algorithmus wird das nicht für Sie tun.

Was versuchst du zu implementieren? Es gibt selbstausgleichende Bäume (AVL / Rot-Schwarz). In der Tat sind Java-Bäume ausgeglichen.

Uri
quelle
3

Wenn dies für Ihren Job ist , schlage ich vor:

  1. Rad nicht neu erfinden und
  2. benutze / kaufe COTS anstatt mit Bits herumzuspielen.
  3. Sparen Sie Zeit und Energie bei der Lösung von Geschäftsproblemen.
Steven A. Lowe
quelle
3
public boolean isBalanced(TreeNode root)
{
    return (maxDepth(root) - minDepth(root) <= 1);
}

public int maxDepth(TreeNode root)
{
    if (root == null) return 0;

    return 1 + max(maxDepth(root.left), maxDepth(root.right));
}

public int minDepth (TreeNode root)
{
    if (root == null) return 0;

    return 1 + min(minDepth(root.left), minDepth(root.right));
}
sdk
quelle
Ich denke, diese Lösung ist nicht korrekt. Wenn Sie einen Baum übergeben, der einen einzelnen Knoten hat, dh eine Wurzel, wird er als maxDepth zurückgegeben 1(dasselbe gilt für minDepth). Die richtige Tiefe sollte jedoch sein 0. Die Wurzel eines Baumes hat immer 0Tiefe
Cratylus
3

Hier ist eine vollständig ausgearbeitete, getestete Lösung in C # (sorry, ich bin kein Java-Entwickler) (einfach kopieren, in die Konsolen-App einfügen). Ich weiß, dass die Definition von ausgeglichen unterschiedlich ist, so dass nicht jeder meine Testergebnisse mag. Schauen Sie sich jedoch bitte den etwas anderen Ansatz an, Tiefe / Höhe in einer rekursiven Schleife zu überprüfen und bei der ersten Nichtübereinstimmung zu beenden, ohne die Höhe / Ebene / Tiefe des Knotens auf jedem Knoten zu speichern (nur in einem Funktionsaufruf pflegen).

using System;
using System.Linq;
using System.Text;

namespace BalancedTree
{
    class Program
    {
        public static void Main()
        {
            //Value Gathering
            Console.WriteLine(RunTreeTests(new[] { 0 }));
            Console.WriteLine(RunTreeTests(new int[] { }));

            Console.WriteLine(RunTreeTests(new[] { 0, 1, 2, 3, 4, -1, -4, -3, -2 }));
            Console.WriteLine(RunTreeTests(null));
            Console.WriteLine(RunTreeTests(new[] { 10, 8, 12, 8, 4, 14, 8, 10 }));
            Console.WriteLine(RunTreeTests(new int[] { 20, 10, 30, 5, 15, 25, 35, 3, 8, 12, 17, 22, 27, 32, 37 }));

            Console.ReadKey();
        }

        static string RunTreeTests(int[] scores)
        {
            if (scores == null || scores.Count() == 0)
            {
                return null;
            }

            var tree = new BinarySearchTree();

            foreach (var score in scores)
            {
                tree.InsertScore(score);
            }

            Console.WriteLine(tree.IsBalanced());

            var sb = tree.GetBreadthWardsTraversedNodes();

            return sb.ToString(0, sb.Length - 1);
        }
    }

    public class Node
    {
        public int Value { get; set; }
        public int Count { get; set; }
        public Node RightChild { get; set; }
        public Node LeftChild { get; set; }
        public Node(int value)
        {
            Value = value;
            Count = 1;
        }

        public override string ToString()
        {
            return Value + ":" + Count;
        }

        public bool IsLeafNode()
        {
            return LeftChild == null && RightChild == null;
        }

        public void AddValue(int value)
        {
            if (value == Value)
            {
                Count++;
            }
            else
            {
                if (value > Value)
                {
                    if (RightChild == null)
                    {
                        RightChild = new Node(value);
                    }
                    else
                    {
                        RightChild.AddValue(value);
                    }
                }
                else
                {
                    if (LeftChild == null)
                    {
                        LeftChild = new Node(value);
                    }
                    else
                    {
                        LeftChild.AddValue(value);
                    }
                }
            }
        }
    }

    public class BinarySearchTree
    {
        public Node Root { get; set; }

        public void InsertScore(int score)
        {
            if (Root == null)
            {
                Root = new Node(score);
            }
            else
            {
                Root.AddValue(score);
            }
        }

        private static int _heightCheck;
        public bool IsBalanced()
        {
            _heightCheck = 0;
            var height = 0;
            if (Root == null) return true;
            var result = CheckHeight(Root, ref height);
            height--;
            return (result && height == 0);
        }

        private static bool CheckHeight(Node node, ref int height)
        {
            height++;
            if (node.LeftChild == null)
            {
                if (node.RightChild != null) return false;
                if (_heightCheck != 0) return _heightCheck == height;
                _heightCheck = height;
                return true;
            }
            if (node.RightChild == null)
            {
                return false;
            }

            var leftCheck = CheckHeight(node.LeftChild, ref height);
            if (!leftCheck) return false;
            height--;
            var rightCheck = CheckHeight(node.RightChild, ref height);
            if (!rightCheck) return false;
            height--;
            return true;
        }


        public StringBuilder GetBreadthWardsTraversedNodes()
        {
            if (Root == null) return null;
            var traversQueue = new StringBuilder();
            traversQueue.Append(Root + ",");
            if (Root.IsLeafNode()) return traversQueue;
            TraversBreadthWards(traversQueue, Root);
            return traversQueue;
        }

        private static void TraversBreadthWards(StringBuilder sb, Node node)
        {
            if (node == null) return;
            sb.Append(node.LeftChild + ",");
            sb.Append(node.RightChild + ",");
            if (node.LeftChild != null && !node.LeftChild.IsLeafNode())
            {
                TraversBreadthWards(sb, node.LeftChild);
            }
            if (node.RightChild != null && !node.RightChild.IsLeafNode())
            {
                TraversBreadthWards(sb, node.RightChild);
            }
        }
    }
}
sbp
quelle
Ich verstehe nicht, wie jemand diese Antwort innerhalb von 2 Minuten nach dem Posten der Antwort negativ bewerten könnte? Negative Abstimmung ist in Ordnung, aber können Sie bitte erklären, was mit dieser Lösung nicht stimmt?
sbp
2
#include <iostream>
#include <deque>
#include <queue>

struct node
{
    int data;
    node *left;
    node *right;
};

bool isBalanced(node *root)
{
    if ( !root)
    {
        return true;
    }

    std::queue<node *> q1;
    std::queue<int>  q2;
    int level = 0, last_level = -1, node_count = 0;

    q1.push(root);
    q2.push(level);

    while ( !q1.empty() )
    {
        node *current = q1.front();
        level = q2.front();

        q1.pop();
        q2.pop();

        if ( level )
        {
            ++node_count;
        }

                if ( current->left )
                {
                        q1.push(current->left);
                        q2.push(level + 1);
                }

                if ( current->right )
                {
                        q1.push(current->right);
                        q2.push(level + 1);
                }

        if ( level != last_level )
        {
            std::cout << "Check: " << (node_count ? node_count - 1 : 1) << ", Level: " << level << ", Old level: " << last_level << std::endl;
            if ( level && (node_count - 1) != (1 << (level-1)) )
            {
                return false;
            }

            last_level = q2.front();
            if ( level ) node_count = 1;
        }
    }

    return true;
}

int main()
{
    node tree[15];

    tree[0].left  = &tree[1];
    tree[0].right = &tree[2];
    tree[1].left  = &tree[3];
    tree[1].right = &tree[4];
    tree[2].left  = &tree[5];
    tree[2].right = &tree[6];
    tree[3].left  = &tree[7];
    tree[3].right = &tree[8];
    tree[4].left  = &tree[9];   // NULL;
    tree[4].right = &tree[10];  // NULL;
    tree[5].left  = &tree[11];  // NULL;
    tree[5].right = &tree[12];  // NULL;
    tree[6].left  = &tree[13];
    tree[6].right = &tree[14];
    tree[7].left  = &tree[11];
    tree[7].right = &tree[12];
    tree[8].left  = NULL;
    tree[8].right = &tree[10];
    tree[9].left  = NULL;
    tree[9].right = &tree[10];
    tree[10].left = NULL;
    tree[10].right= NULL;
    tree[11].left = NULL;
    tree[11].right= NULL;
    tree[12].left = NULL;
    tree[12].right= NULL;
    tree[13].left = NULL;
    tree[13].right= NULL;
    tree[14].left = NULL;
    tree[14].right= NULL;

    std::cout << "Result: " << isBalanced(tree) << std::endl;

    return 0;
}
Frank Raaj
quelle
Vielleicht möchten Sie einige Kommentare hinzufügen
jgauffin
2

RE: @ glückliche Lösung mit einem BFS für eine Durchquerung der Ebenenreihenfolge.

Wir durchlaufen den Baum und behalten einen Verweis auf vars min / max-level bei, der die minimale Ebene beschreibt, auf der ein Knoten ein Blatt ist.

Ich glaube, dass die @ glückliche Lösung eine Modifikation erfordert. Wie von @codaddict vorgeschlagen, müssen wir nicht prüfen, ob ein Knoten ein Blatt ist, sondern prüfen, ob entweder das linke oder das rechte untergeordnete Element null ist (nicht beide). Andernfalls würde der Algorithmus dies als einen gültigen ausgeglichenen Baum betrachten:

     1
    / \
   2   4
    \   \
     3   1

In Python:

def is_bal(root):
    if root is None:
        return True

    import queue

    Q = queue.Queue()
    Q.put(root)

    level = 0
    min_level, max_level = sys.maxsize, sys.minsize

    while not Q.empty():
        level_size = Q.qsize()

        for i in range(level_size):
            node = Q.get()

            if not node.left or node.right:
                min_level, max_level = min(min_level, level), max(max_level, level)

            if node.left:
                Q.put(node.left)
            if node.right:
                Q.put(node.right)

        level += 1

        if abs(max_level - min_level) > 1:
            return False

    return True

Diese Lösung sollte alle in der ursprünglichen Frage angegebenen Bestimmungen erfüllen und in O (n) Zeit und O (n) Raum arbeiten. Ein Speicherüberlauf würde auf den Heap geleitet, anstatt einen rekursiven Aufrufstapel zu sprengen.

Alternativ könnten wir zunächst den Baum durchlaufen, um die maximale Höhe + Cache für jeden Stammunterbaum iterativ zu berechnen. Überprüfen Sie dann in einem weiteren iterativen Lauf, ob sich die zwischengespeicherten Höhen der linken und rechten Teilbäume für jede Wurzel nie um mehr als eins unterscheiden. Dies würde auch in O (n) Zeit und O (n) Raum laufen, jedoch iterativ, um keinen Stapelüberlauf zu verursachen.

vikasnair
quelle
1

Nun, Sie brauchen einen Weg, um die Höhen von links und rechts zu bestimmen, und ob links und rechts ausgeglichen sind.

Und ich würde einfach return height(node->left) == height(node->right);

heightLesen Sie zum Schreiben einer Funktion: Rekursion verstehen

tpdi
quelle
3
Sie möchten, dass die linke und rechte Höhe innerhalb von 1 liegen und nicht unbedingt gleich sind.
Alex B
1

Von welcher Art von Baum sprichst du? Es gibt selbstausgleichende Bäume da draußen. Überprüfen Sie ihre Algorithmen, um festzustellen, ob sie den Baum neu anordnen müssen, um das Gleichgewicht aufrechtzuerhalten.

Lothar
quelle
1

Hier ist eine Version, die auf einer generischen Tiefenüberquerung basiert. Sollte schneller sein als die andere richtige Antwort und alle genannten "Herausforderungen" bewältigen. Entschuldigung für den Stil, ich kenne Java nicht wirklich.

Sie können es immer noch viel schneller machen, indem Sie früh zurückkehren, wenn sowohl max als auch min eingestellt sind und einen Unterschied> 1 haben.

public boolean isBalanced( Node root ) {
    int curDepth = 0, maxLeaf = 0, minLeaf = INT_MAX;
    if ( root == null ) return true;
    while ( root != null ) {
        if ( root.left == null || root.right == null ) {
            maxLeaf = max( maxLeaf, curDepth );
            minLeaf = min( minLeaf, curDepth );
        }
        if ( root.left != null ) {
            curDepth += 1;
            root = root.left;
        } else {
            Node last = root;
            while ( root != null
             && ( root.right == null || root.right == last ) ) {
                curDepth -= 1;
                last = root;
                root = root.parent;
            }
            if ( root != null ) {
                curDepth += 1;
                root = root.right;
            }
        }
    }
    return ( maxLeaf - minLeaf <= 1 );
}
Kartoffelklatsche
quelle
1
Ein schöner Versuch, aber es funktioniert eindeutig nicht. Sei x ein Nullknoten. Ein Nicht-Null-Baumknoten sei mit (LEFT VALUE RIGHT) bezeichnet. Betrachten Sie den Baum (x A (x B x)). "root" zeigt für immer auf die Knoten A, B, A, B, A, B ... Möchtest du es noch einmal versuchen? Ein Hinweis: Ohne übergeordnete Zeiger ist es tatsächlich einfacher .
Eric Lippert
@ Eric: Ups, behoben (glaube ich). Nun, ich versuche dies ohne O (Tiefen-) Speicher zu tun, und wenn die Struktur keine übergeordneten Zeiger hat (was häufig der Fall ist), müssen Sie einen Stapel verwenden.
Potatoswatter
Sie sagen mir also, dass Sie lieber O (n) permanenten Speicher in übergeordneten Zeigern verwenden möchten, um die Zuweisung von O (d) temporärem Speicher zu vermeiden, wobei log n <= d <= n? Dies scheint eine falsche Wirtschaft zu sein.
Eric Lippert
Obwohl Sie das Problem mit der Durchquerung behoben haben, gibt es hier leider ein weitaus größeres Problem. Dies testet nicht, ob ein Baum ausgeglichen ist, sondern ob alle Blätter eines Baumes in der Nähe des gleichen Niveaus liegen. Das ist nicht die Definition von "ausgewogen", die ich gegeben habe. Betrachten Sie den Baum ((((x D x) C x) B x) A x). Ihr Code meldet, dass dies "ausgeglichen" ist, wenn es offensichtlich maximal unausgeglichen ist. Möchtest du es noch einmal versuchen?
Eric Lippert
@ Eric Antwort 1: Keine falsche Wirtschaftlichkeit, wenn Sie die übergeordneten Zeiger bereits für etwas anderes verwenden. Antwort 2: Sicher, warum nicht. Dies ist eine bizarre Art des Debuggens… Ich sollte nicht blind um 4 Uhr
morgens
1
/* Returns true if Tree is balanced, i.e. if the difference between the longest path and the shortest path from the root to a leaf node is no more than than 1. This difference can be changed to any arbitrary positive number. */
boolean isBalanced(Node root) {
    if (longestPath(root) - shortestPath(root) > 1)
        return false;
    else
        return true;
}


int longestPath(Node root) {
    if (root == null);
        return 0;
    else {
        int leftPathLength = longestPath(root.left);
        int rightPathLength = longestPath(root.right);
        if (leftPathLength >= rightPathLength)
            return leftPathLength + 1;
        else
            return rightPathLength + 1;
    }
}

int shortestPath(Node root) {
    if (root == null);
        return 0;
    else {
        int leftPathLength = shortestPath(root.left);
        int rightPathLength = shortestPath(root.right);
        if (leftPathLength <= rightPathLength)
            return leftPathLength + 1;
        else
            return rightPathLength + 1;
    }
}
Intuiter
quelle
1
Sie sollten Ihrer Antwort eine Beschreibung und / oder Kommentare zu Ihrem Codebeispiel hinzufügen.
Brad Campbell
1
class Node {
    int data;
    Node left;
    Node right;

    // assign variable with constructor
    public Node(int data) {
        this.data = data;
    }
}

public class BinaryTree {

    Node root;

    // get max depth
    public static int maxDepth(Node node) {
        if (node == null)
            return 0;

        return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
    }

    // get min depth
    public static int minDepth(Node node) {
        if (node == null)
            return 0;

        return 1 + Math.min(minDepth(node.left), minDepth(node.right));
    }

    // return max-min<=1 to check if tree balanced
    public boolean isBalanced(Node node) {

        if (Math.abs(maxDepth(node) - minDepth(node)) <= 1)
            return true;

        return false;
    }

    public static void main(String... strings) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);


        if (tree.isBalanced(tree.root))
            System.out.println("Tree is balanced");
        else
            System.out.println("Tree is not balanced");
    }
}
Pranay
quelle
0

Folgendes habe ich für Erics Bonusübung versucht. Ich versuche, meine rekursiven Schleifen abzuwickeln und zurückzukehren, sobald ich feststelle, dass ein Teilbaum nicht ausgeglichen ist.

int heightBalanced(node *root){
    int i = 1;
    heightBalancedRecursive(root, &i);
    return i; 
} 

int heightBalancedRecursive(node *root, int *i){

    int lb = 0, rb = 0;

    if(!root || ! *i)  // if node is null or a subtree is not height balanced
           return 0;  

    lb = heightBalancedRecursive(root -> left,i);

    if (!*i)         // subtree is not balanced. Skip traversing the tree anymore
        return 0;

    rb = heightBalancedRecursive(root -> right,i)

    if (abs(lb - rb) > 1)  // not balanced. Make i zero.
        *i = 0;

    return ( lb > rb ? lb +1 : rb + 1); // return the current height of the subtree
}
Sudharsanan
quelle
0
public int height(Node node){
    if(node==null)return 0;
    else{
        int l=height(node.leftChild);
        int r=height(node.rightChild);
       return(l>r?l+1:r+1);

}}
public boolean balanced(Node n){

    int l= height(n.leftChild);
    int r= height(n.rightChild);

    System.out.println(l + " " +r);
    if(Math.abs(l-r)>1)
        return false;
    else 
        return true;
    }
immer
quelle
0

Ein leerer Baum ist höhenausgeglichen. Ein nicht leerer Binärbaum T ist ausgeglichen, wenn:

1) Der linke Teilbaum von T ist ausgeglichen

2) Der rechte Teilbaum von T ist ausgeglichen

3) Der Höhenunterschied zwischen dem linken und dem rechten Teilbaum beträgt nicht mehr als 1.

/* program to check if a tree is height-balanced or not */
#include<stdio.h>
#include<stdlib.h>
#define bool int

/* A binary tree node has data, pointer to left child
   and a pointer to right child */
struct node
{
  int data;
  struct node* left;
  struct node* right;
};

/* The function returns true if root is balanced else false
   The second parameter is to store the height of tree.  
   Initially, we need to pass a pointer to a location with value 
   as 0. We can also write a wrapper over this function */
bool isBalanced(struct node *root, int* height)
{
  /* lh --> Height of left subtree 
     rh --> Height of right subtree */   
  int lh = 0, rh = 0;  

  /* l will be true if left subtree is balanced 
    and r will be true if right subtree is balanced */
  int l = 0, r = 0;

  if(root == NULL)
  {
    *height = 0;
     return 1;
  }

  /* Get the heights of left and right subtrees in lh and rh 
    And store the returned values in l and r */   
  l = isBalanced(root->left, &lh);
  r = isBalanced(root->right,&rh);

  /* Height of current node is max of heights of left and 
     right subtrees plus 1*/   
  *height = (lh > rh? lh: rh) + 1;

  /* If difference between heights of left and right 
     subtrees is more than 2 then this node is not balanced
     so return 0 */
  if((lh - rh >= 2) || (rh - lh >= 2))
    return 0;

  /* If this node is balanced and left and right subtrees 
    are balanced then return true */
  else return l&&r;
}


/* UTILITY FUNCTIONS TO TEST isBalanced() FUNCTION */

/* Helper function that allocates a new node with the
   given data and NULL left and right pointers. */
struct node* newNode(int data)
{
    struct node* node = (struct node*)
                                malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;

    return(node);
}

int main()
{
  int height = 0;

  /* Constructed binary tree is
             1
           /   \
         2      3
       /  \    /
     4     5  6
    /
   7
  */   
  struct node *root = newNode(1);  
  root->left = newNode(2);
  root->right = newNode(3);
  root->left->left = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(6);
  root->left->left->left = newNode(7);

  if(isBalanced(root, &height))
    printf("Tree is balanced");
  else
    printf("Tree is not balanced");    

  getchar();
  return 0;
}

Zeitkomplexität: O (n)

Saqlain
quelle
0

Um eine bessere Leistung speziell bei großen Bäumen zu erzielen, können Sie die Höhe in jedem Knoten speichern, sodass ein Kompromiss zwischen Leistung und Leistung besteht:

class Node {
    Node left;
    Node right;
    int value;
    int height;
}

Beispiel für die Implementierung des Hinzufügens und des gleichen zum Löschen

void addNode(Node root,int v)
{    int height =0;
     while(root != null)
     {
         // Since we are adding new node so the height 
         // will increase by one in each node we will pass by
         root.height += 1;
         height++;
         else if(v > root.value){
            root = root.left();
            }
         else{
         root = root.right();
         }

     }

         height++;
         Node n = new Node(v , height);
         root = n;         
}
int treeMaxHeight(Node root)
{
 return Math.Max(root.left.height,root.right.height);
}

int treeMinHeight(Node root)
{
 return Math.Min(root.left.height,root.right.height);

}

Boolean isNodeBlanced(Node root)
{
   if (treeMaxHeight(root) - treeMinHeight(root) > 2)
       return false;

  return true;
}

Boolean isTreeBlanced (Node root)
{
    if(root == null || isTreeBalanced(root.left) && isTreeBalanced(root.right) && isNodeBlanced(root))
    return true;

  return false;

}
Maher Rezeq
quelle
-1
    static boolean isBalanced(Node root) {
    //check in the depth of left and right subtree
    int diff = depth(root.getLeft()) - depth(root.getRight());
    if (diff < 0) {
        diff = diff * -1;
    }
    if (diff > 1) {
        return false;
    }
    //go to child nodes
    else {
        if (root.getLeft() == null && root.getRight() == null) {
            return true;
        } else if (root.getLeft() == null) {
            if (depth(root.getRight()) > 1) {
                return false;
            } else {
                return true;
            }
        } else if (root.getRight() == null) {
            if (depth(root.getLeft()) > 1) {
                return false;
            } else {
                return true;
            }
        } else if (root.getLeft() != null && root.getRight() != null && isBalanced(root.getLeft()) && isBalanced(root.getRight())) {
            return true;
        } else {
            return false;
        }
    }
}
Saurabh
quelle
-2

Würde das nicht funktionieren?

return ( ( Math.abs( size( root.left ) - size( root.right ) ) < 2 );

Jeder unausgeglichene Baum würde dies immer scheitern lassen.

Sumit Kishore
quelle
4
Viele ausgeglichene Bäume werden es auch nicht schaffen.
Brian