Jak ustalić, czy drzewo binarne jest zrównoważone?


113

Minęło trochę czasu od tych lat szkolnych. Dostałem pracę jako informatyk w szpitalu. Próbuję teraz przejść do faktycznego programowania. Pracuję teraz nad drzewami binarnymi i zastanawiałem się, jaki byłby najlepszy sposób określenia, czy drzewo jest zrównoważone pod względem wysokości.

Myślałem o czymś w związku z tym:

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

Czy to dobra realizacja? czy coś mi brakuje?


Jeśli chcesz zobaczyć ascii drzewo binarne Donala Fellowsa z grafiką: i.imgur.com/97C27Ek.png
user7643681

1
Dobra odpowiedź, pomogła mi dostać się do USA. (żarty)
Henry

Odpowiedzi:


165

Natknąłem się na to stare pytanie, szukając czegoś innego. Zauważyłem, że nigdy nie otrzymałeś pełnej odpowiedzi.

Sposobem rozwiązania tego problemu jest rozpoczęcie od napisania specyfikacji funkcji, którą próbujesz napisać.

Specyfikacja: O dobrze uformowanym drzewie binarnym mówi się, że jest „zrównoważone wysokością”, jeśli (1) jest puste lub (2) jego lewe i prawe elementy potomne mają zrównoważoną wysokość, a wysokość lewego drzewa mieści się w zakresie 1 od wysokość prawego drzewa.

Teraz, gdy masz już specyfikację, napisanie kodu jest banalne. Wystarczy postępować zgodnie ze specyfikacją:

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

Przetłumaczenie tego na wybrany język programowania powinno być banalne.

Dodatkowe ćwiczenie : ten naiwny szkic kodu przemierza drzewo zbyt wiele razy podczas obliczania wysokości. Czy możesz uczynić to bardziej wydajnym?

Super dodatkowe ćwiczenie : załóżmy, że drzewo jest bardzo niezrównoważone. Na przykład milion węzłów po jednej stronie i trzy po drugiej. Czy istnieje scenariusz, w którym ten algorytm rozwala stos? Czy możesz naprawić implementację tak, aby nigdy nie wysadzała stosu, nawet jeśli otrzymujesz masowo niezrównoważone drzewo?

AKTUALIZACJA : Donal Fellows wskazuje w swojej odpowiedzi, że istnieją różne definicje „zrównoważonego”, które można wybrać. Na przykład, można by przyjąć bardziej rygorystyczną definicję „zrównoważonego wzrostu” i wymagać, aby długość ścieżki do najbliższego pustego dziecka znajdowała się w obrębie jednej ze ścieżek do najdalszego pustego dziecka. Moja definicja jest mniej surowa i dlatego dopuszcza więcej drzew.

Można też być mniej restrykcyjne niż moja definicja; można powiedzieć, że zrównoważone drzewo to takie, w którym maksymalna długość ścieżki do pustego drzewa na każdej gałęzi różni się nie więcej niż o dwa, trzy lub o jakąś inną stałą. Albo, że maksymalna długość ścieżki jest ułamkiem minimalnej długości ścieżki, na przykład pół lub ćwiartka.

Zwykle to naprawdę nie ma znaczenia. Celem każdego algorytmu równoważenia drzewa jest zapewnienie, że nie skończysz w sytuacji, w której masz milion węzłów po jednej stronie i trzy po drugiej. Definicja Donala jest w teorii dobra, ale w praktyce wymyślanie algorytmu równoważenia drzewa, który spełnia ten poziom ścisłości, jest uciążliwe. Oszczędności wydajności zwykle nie uzasadniają kosztów wdrożenia. Spędzasz dużo czasu wykonując niepotrzebne przestawianie drzew, aby osiągnąć poziom równowagi, który w praktyce nie ma większego znaczenia. Kogo to obchodzi, jeśli czasami potrzeba czterdziestu gałęzi, aby dostać się do najdalszego liścia w milionie węzłów niedoskonale zrównoważonym drzewie, podczas gdy teoretycznie w idealnie zrównoważonym drzewie może zajmować tylko dwadzieścia? Chodzi o to, że nigdy nie potrzeba miliona. Przejście od najgorszego przypadku miliona do najgorszego przypadku czterdziestki jest zwykle wystarczająco dobre; nie musisz dążyć do optymalnego przypadku.


19
+1 za tylko poprawną odpowiedź, nie wierzę, że nikt nie był w stanie odpowiedzieć przez 8 miesięcy ...
BlueRaja - Danny Pflughoeft

1
Odpowiedz na poniższe „ćwiczenia”…
Potatoswatter

Poniższe ćwiczenie dotyczące premii.
Brian

Odpowiedź sdk poniżej wydaje się być prawidłowa i umożliwia przechodzenie tylko przez 2 drzewa, więc jest O (n). Chyba że czegoś brakuje, czy to nie rozwiązuje przynajmniej twojego pierwszego pytania bonusowego. Możesz oczywiście użyć programowania dynamicznego i swojego rozwiązania do buforowania wysokości pośrednich
Aly

Teoretycznie nadal musiałbym stanąć po stronie definicji Donala Fellows.
Dhruv Gairola

26

Równowaga to naprawdę subtelna właściwość; myślisz, że wiesz, co to jest, ale tak łatwo jest się pomylić. W szczególności, nawet (dobra) odpowiedź Erica Lipperta jest wykluczona. To dlatego, że pojęcie wysokości nie wystarczy. Musisz mieć pojęcie minimalnej i maksymalnej wysokości drzewa (gdzie minimalna wysokość to najmniejsza liczba kroków od korzenia do liścia, a maksymalna to ... cóż, masz obraz). Biorąc to pod uwagę, możemy zdefiniować równowagę jako:

Drzewo, którego maksymalna wysokość dowolnej gałęzi nie przekracza jedną minimalną wysokość jakiejkolwiek gałęzi.

(W rzeczywistości oznacza to, że same gałęzie są zrównoważone; możesz wybrać tę samą gałąź zarówno dla maksimum, jak i minimum).

Wszystko, co musisz zrobić, aby zweryfikować tę właściwość, to proste przejście przez drzewo, które śledzi aktualną głębokość. Za pierwszym razem, gdy cofasz się, daje to podstawową głębokość. Za każdym razem, gdy cofasz się, porównujesz nową głębokość z linią bazową

  • jeśli jest równy linii bazowej, po prostu kontynuuj
  • jeśli jest więcej niż jeden, drzewo nie jest zrównoważone
  • jeśli jest jednorazowy, to znasz teraz zakres równowagi, a wszystkie kolejne głębokości (kiedy masz zamiar się cofnąć) muszą być albo pierwszą, albo drugą wartością.

W kodzie:

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

Przypuszczam, że można by to zrobić bez użycia wzorca Obserwator, ale wydaje mi się, że łatwiej jest to rozumować w ten sposób.


[EDYCJA]: Dlaczego nie możesz po prostu wziąć wysokości z każdej strony. Rozważ to drzewo:

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

OK, trochę brudny, ale każda strona z korzenia jest zrównoważony: Cjest głębokość 2, A, B, D, Eto głębokość 3, a F, G, H, Jto głębokość 4. Wysokość lewej gałęzi wynosi 2 (pamiętaj wysokość zmniejsza się wraz z ukośnymi gałąź), wysokość prawej gałęzi wynosi 3. Jednak całe drzewo nie jest zrównoważone, ponieważ istnieje różnica wysokości 2 między Ca F. Potrzebujesz specyfikacji minimax (chociaż rzeczywisty algorytm może być mniej złożony, ponieważ powinny istnieć tylko dwie dozwolone wysokości).


Ach, słuszna uwaga. Możesz mieć drzewo, które ma h (LL) = 4, h (LR) = 3, h (RL) = 3, h (RR) = 2. Zatem h (L) = 4 i h (R) = 3, więc wydaje się, że jest zrównoważony w stosunku do wcześniejszego algorytmu, ale przy maksymalnej / minimalnej głębokości 4/2 nie jest to zrównoważone. Miałoby to prawdopodobnie większy sens w przypadku obrazu.
Tim,

1
Właśnie to dodałem (z najgorszym na świecie drzewem graficznym ASCII).
Donal Fellows

@DonalFellows: wspomniałeś, że wysokość lewej gałęzi wynosi 2, ale lewa gałąź ma 4 węzły, w tym korzeń i liść A.W tym przypadku wysokość będzie wynosić 3
burza mózgów

22

To tylko określa, czy najwyższy poziom drzewa jest zrównoważony. Oznacza to, że możesz mieć drzewo z dwiema długimi gałęziami z lewej i prawej strony, bez niczego pośrodku, i to wróci prawdą. Musisz rekurencyjnie sprawdzić root.lefti root.rightsprawdzić, czy są one również wewnętrznie zrównoważone, zanim zwrócisz wartość true.


Jeśli jednak kod miałby metodę maksymalnej i minimalnej wysokości, jeśli jest globalnie zrównoważony, byłby również zrównoważony lokalnie.
Ari

22

Dodatkowa odpowiedź na ćwiczenie. Proste rozwiązanie. Oczywiście w prawdziwej implementacji można zawinąć to lub coś, aby uniknąć wymagania od użytkownika uwzględnienia wysokości w odpowiedzi.

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     

Jeśli drzewo jest większe niż kilkaset warstw, pojawi się wyjątek przepełnienia stosu. Zrobiłeś to wydajnie, ale nie obsługuje średnich ani dużych zestawów danych.
Eric Leschinski

Czy to pseudokod, który właśnie wymyśliłeś, czy jest to prawdziwy język? (Mam na myśli " out height" zmienną notację)
kap

@kap: to jest pseudokod, ale składnia wyjściowa jest pobierana z C #. Zasadniczo oznacza to, że parametr przemieszcza się z wywoływanej funkcji do wywołującego (w przeciwieństwie do standardowych parametrów, które przemieszczają się od obiektu wywołującego do wywoływanej funkcji lub parametrów ref, które wędrują od wywołującego do wywoływanej funkcji iz powrotem). To skutecznie umożliwia funkcjom zwracanie więcej niż jednej wartości.
Brian

20

Rozwiązanie po zamówieniu, przejdź przez drzewo tylko raz. Złożoność czasowa to O (n), przestrzeń to O (1), to lepsze niż rozwiązanie odgórne. Dam ci implementację wersji java.

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

4
fajne rozwiązanie, ale złożoność przestrzeni powinna wynosić O (H), gdzie H to wysokość drzewa. Dzieje się tak, ponieważ alokacja stosu dla rekursji.
legrass

Co to left == -1znaczy? Kiedy tak się stanie? Czy zakładamy, że rekurencyjne wywołanie implikuje, że left == -1to prawda, jeśli wszystkie poddrzewa lewych dzieci są niezrównoważone?
Aspen

left == 1oznacza, że ​​lewe poddrzewo jest niezrównoważone, a następnie całe drzewo jest niezrównoważone. Nie musimy już sprawdzać odpowiedniego poddrzewa i możemy wrócić -1.
od

Złożoność czasowa wynosi O (n), ponieważ musisz przejść przez wszystkie elementy. A jeśli masz x węzłów i sprawdzenie salda zajmie y czasu; jeśli masz 2x węzły, sprawdzenie salda zajmie 2 lata. To wszystko brzmi, prawda?
Jack

Cóż, wyjaśnienie z rysunkiem jest tutaj: algorytms.tutorialhorizon.com/ ...
Shir

15

Definicja drzewa binarnego o zrównoważonej wysokości to:

Drzewo binarne, w którym wysokość dwóch poddrzew każdego węzła nigdy nie różni się o więcej niż 1.

Zatem puste drzewo binarne jest zawsze zrównoważone wysokością.
Niepuste drzewo binarne jest zrównoważone wysokością, jeśli:

  1. Jego lewe poddrzewo jest zrównoważone wysokością.
  2. Jego prawe poddrzewo jest zrównoważone wysokością.
  3. Różnica między wysokościami lewego i prawego poddrzewa nie jest większa niż 1.

Rozważ drzewo:

    A
     \ 
      B
     / \
    C   D

Jak widać, lewe poddrzewo Ajest zrównoważone wysokością (ponieważ jest puste), podobnie jak jego prawe poddrzewo. Ale nadal drzewo nie jest zrównoważone pod względem wysokości, ponieważ warunek 3 nie jest spełniony, ponieważ wysokość lewego poddrzewa jest taka, jak 0wysokość prawego poddrzewa 2.

Kolejne drzewo nie jest zrównoważone pod względem wysokości, mimo że wysokość lewego i prawego poddrzewa jest równa. Twój istniejący kod zwróci dla niego wartość true.

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

Więc słowo każdy w def jest bardzo ważne.

To zadziała:

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


Więc ta odpowiedź bardzo mi pomogła. Jednak okazało się, że darmowy [MIT wprowadzenie do kursu algorytmów] wydaje się zaprzeczać warunkowi 3. Strona 4 pokazuje drzewo RB, w którym wysokość lewej gałęzi wynosi 2, a prawej - 4. Czy możesz mi zaoferować jakieś wyjaśnienie? Być może nie rozumiem definicji poddrzewa. [1]: ocw.mit.edu/courses/electrical-engineering-and-computer-science/…
i8abug

Różnica wydaje się wynikać z tej definicji w notatkach do kursu. Wszystkie proste ścieżki każdy węzeł X potomka liścia mają taką samą liczbę węzłów, czarny = czarny wysokość (x)
i8abug

Aby kontynuować, znalazłem definicję, która zmienia punkt (3) w Twojej odpowiedzi na to, że „każdy liść jest„ nie dalej niż w pewnej odległości ”od korzenia niż jakikolwiek inny liść”. Wydaje się, że spełnia to oba przypadki. Oto link z jakiegoś losowego kursu
i8abug

8

Jeśli drzewo binarne jest zbalansowane lub nie, można to sprawdzić za pomocą przemierzania kolejności poziomów:

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

1
Doskonała odpowiedź. Myślę, że spełnia wszystkie wymagania, które Eric opublikował w sprawie premii i super-premii. Jest iteracyjny (przy użyciu kolejki) i nie rekurencyjny - więc stos wywołań nie zostanie przepełniony, a wszystkie problemy z pamięcią przenosimy na stertę. Nie wymaga nawet przemierzania całego drzewa. Porusza się poziom po poziomie, więc jeśli drzewo jest rażąco niezrównoważone na 1 stronę, znajdzie je naprawdę szybko (najwcześniej? Dobrze wcześniej niż większość algorytmów rekurencyjnych, chociaż można zaimplementować iteracyjny algorytm przechodzenia po zamówieniu, który znajdzie ostatni poziom niewyważenia wcześniej, ale będą działać gorzej na pierwszych poziomach). Więc +1 :-)
David Refaeli

7

To jest o wiele bardziej skomplikowane niż w rzeczywistości.

Algorytm wygląda następująco:

  1. Niech A = głębokość węzła najwyższego poziomu
  2. Niech B = głębokość węzła najniższego poziomu

  3. Jeśli abs (AB) <= 1, to drzewo jest zrównoważone


Proste i proste!
Wasim Thabraze

3
Dwa problemy, to nie jest tak wydajne, jak mogłoby być, wykonujesz dwa przejścia po całym drzewie. A dla drzew, które mają jeden węzeł po lewej i tysiące po prawej, niepotrzebnie przechodzisz przez całą rzecz, podczas gdy mogłeś zatrzymać się po 3 sprawdzeniach.
Eric Leschinski

5

To, jakie zrównoważone środki, zależy w pewnym stopniu od posiadanej konstrukcji. Na przykład drzewo B nie może mieć węzłów znajdujących się dalej niż pewna głębokość od korzenia lub mniej, wszystkie dane żyją na ustalonej głębokości od korzenia, ale mogą być niezrównoważone, jeśli rozmieszczenie liści na liściach -ale jeden węzeł jest nierówny. Listy przeskoków Nie mają pojęcia o równowadze, polegają zamiast tego na prawdopodobieństwie osiągnięcia przyzwoitych wyników. Drzewa Fibonacciego celowo tracą równowagę, opóźniając przywrócenie równowagi, aby osiągnąć lepszą wydajność asymptotyczną w zamian za czasami dłuższe aktualizacje. Drzewa AVL i czerwono-czarne dołączają metadane do każdego węzła, aby uzyskać niezmiennik równowagi głębi.

Wszystkie te i nie tylko struktury są obecne w standardowych bibliotekach większości popularnych systemów programowania (z wyjątkiem Pythona, RAGE!). Wdrożenie jednego lub dwóch jest dobrą praktyką programistyczną, ale prawdopodobnie nie jest to dobre wykorzystanie czasu na toczenie własnych do produkcji, chyba że twój problem ma jakąś szczególną wydajność, której nie muszą zaspokajać żadne gotowe kolekcje.


4

Uwaga 1: Wysokość dowolnego poddrzewa obliczana jest tylko raz.

Uwaga 2: Jeśli lewe poddrzewo jest niezrównoważone, wówczas pomijane jest obliczanie prawego poddrzewa, które może zawierać miliony elementów.

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

3

Równoważenie zwykle zależy od długości najdłuższej ścieżki w każdym kierunku. Powyższy algorytm nie zrobi tego za Ciebie.

Co próbujesz wdrożyć? Dookoła rosną samobalansujące się drzewa (AVL / czerwono-czarne). W rzeczywistości drzewa Java są zrównoważone.



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

Myślę, że to rozwiązanie nie jest poprawne. Jeśli przekażesz drzewo, które ma pojedynczy węzeł, tj. Root, zwróci ono jako maxDepth 1(tak samo dla minDepth). Jednak poprawna głębokość powinna być 0. Korzeń drzewa zawsze ma 0głębię
Cratylus

3

Oto kompletne, przetestowane rozwiązanie w C # (przepraszam, nie mam programisty Java) (po prostu skopiuj wklej w aplikacji konsolowej). Wiem, że definicja zbalansowanego jest różna, więc nie każdemu mogą spodobać się moje wyniki testu, ale proszę spojrzeć na nieco inne podejście do sprawdzania głębokości / wysokości w pętli rekurencyjnej i wychodzenia z pierwszego niedopasowania bez zapisywania wysokości / poziomu / głębokości węzła na każdym węźle (tylko utrzymywanie go w wywołaniu funkcji).

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

Nie rozumiem, jak ktoś mógłby negatywnie zagłosować na tę odpowiedź w ciągu 2 minut od wysłania odpowiedzi? Głosowanie negatywne jest w porządku, ale czy mógłbyś wyjaśnić, co jest złego w tym rozwiązaniu?
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;
}

możesz dodać kilka komentarzy
jgauffin

2

RE: @ lucky's rozwiązanie wykorzystujące BFS do przechodzenia przez kolejność poziomów.

Przechodzimy przez drzewo i zachowujemy odniesienie do vars poziomu min / max, które opisują minimalny poziom, na którym węzeł jest liściem.

Uważam, że rozwiązanie @lucky wymaga modyfikacji. Zgodnie z sugestią @codaddict, zamiast sprawdzać, czy węzeł jest liściem, musimy sprawdzić, czy ALBO lewy lub prawy element potomny jest pusty (nie oba). W przeciwnym razie algorytm uznałby to za prawidłowe zrównoważone drzewo:

     1
    / \
   2   4
    \   \
     3   1

W Pythonie:

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

Rozwiązanie to powinno spełniać wszystkie wymagania zawarte w pytaniu wstępnym, operując w czasie O (n) i przestrzeni O (n). Przepełnienie pamięci byłoby skierowane na stertę, a nie przepełnienie rekurencyjnego stosu wywołań.

Alternatywnie możemy początkowo przejść przez drzewo, aby iteracyjnie obliczyć + cache maksymalne wysokości dla każdego poddrzewa głównego. Następnie w kolejnym iteracyjnym przebiegu sprawdź, czy w pamięci podręcznej wysokości lewego i prawego poddrzewa dla każdego katalogu głównego nigdy nie różnią się o więcej niż jeden. To również działałoby w O (n) czasie i O (n) przestrzeni, ale iteracyjnie, aby nie powodować przepełnienia stosu.


1

Cóż, potrzebujesz sposobu, aby określić wysokość lewej i prawej strony i czy lewa i prawa są zrównoważone.

A ja po prostu return height(node->left) == height(node->right);

Jeśli chodzi o pisanie heightfunkcji, przeczytaj: Zrozumienie rekurencji


3
Chcesz, aby lewa i prawa wysokość mieściły się w granicach 1, niekoniecznie równe.
Alex B

1

O jakim drzewie mówisz? Istnieje samobilansującymi drzewa tam. Sprawdź ich algorytmy, w których określą, czy muszą zmienić kolejność drzewa, aby zachować równowagę.


1

Oto wersja oparta na ogólnym przechodzeniu w pierwszej kolejności w głąb. Powinien być szybszy niż inna poprawna odpowiedź i poradzić sobie ze wszystkimi wspomnianymi „wyzwaniami”. Przepraszam za styl, naprawdę nie znam Javy.

Nadal możesz to znacznie przyspieszyć, wracając wcześniej, jeśli maks. I min są ustawione i mają różnicę> 1.

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

1
Niezła próba, ale najwyraźniej nie działa. Niech x będzie pustym węzłem. Niech niezerowy węzeł drzewa będzie oznaczony jako (LEWA WARTOŚĆ PRAWA). Rozważ drzewo (x A (x B x)). „root” wskazuje na węzły A, B, A, B, A, B… na zawsze. Chcesz spróbować ponownie? Wskazówka: w rzeczywistości jest to łatwiejsze bez wskazówek dla rodziców.
Eric Lippert

@Eric: Ups, naprawione (chyba). Cóż, próbuję to zrobić bez pamięci O (głębokość), a jeśli struktura nie ma wskaźników nadrzędnych (często tak jest), musisz użyć stosu.
Potatoswatter

Więc mówisz mi, że wolisz używać O (n) pamięci stałej we wskaźnikach nadrzędnych, aby uniknąć alokowania O (d) pamięci tymczasowej, gdzie log n <= d <= n? Wydaje się, że to fałszywa ekonomia.
Eric Lippert

Niestety, chociaż rozwiązałeś problem z przemierzaniem, jest tutaj znacznie większy problem. Nie sprawdza to, czy drzewo jest zrównoważone, ale sprawdza, czy drzewo ma wszystkie liście zbliżone do tego samego poziomu. To nie jest definicja „zrównoważonego”, którą podałem. Rozważmy drzewo ((((x D x) C x) B x) A x). Twój kod zgłasza, że ​​jest to „zrównoważone”, gdy oczywiście jest maksymalnie niezrównoważone. Chcesz spróbować ponownie?
Eric Lippert

@Eric odpowiedz 1: nie jest to fałszywa ekonomia, jeśli już używasz wskaźników nadrzędnych do czegoś innego. odpowiedź 2: jasne, czemu nie. To dziwny sposób debugowania… Nie powinienem ślepo pisać przemierzania czegokolwiek o 4 rano…
Potatoswatter,

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

1
Powinieneś dodać opis do swojej odpowiedzi i / lub komentarzy do próbki kodu.
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");
    }
}

0

Oto, czego próbowałem w dodatkowym ćwiczeniu Erica. Próbuję rozwinąć moje pętle rekurencyjne i wrócić, gdy tylko znajdę poddrzewo, które nie jest zrównoważone.

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
}

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

0

Puste drzewo ma równowagę wysokości. Niepuste drzewo binarne T jest równoważone, jeśli:

1) Lewe poddrzewo T jest zrównoważone

2) Prawe poddrzewo T jest zrównoważone

3) Różnica między wysokościami lewego i prawego poddrzewa jest nie większa niż 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;
}

Złożoność czasowa: O (n)


0

Aby uzyskać lepszą wydajność, szczególnie na dużych drzewach, możesz zapisać wysokość w każdym węźle, więc jest to kompromis między wydajnością przestrzeni a wydajnością:

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

Przykład wykonania dodawania i to samo w przypadku usuwania

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;

}

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

-2

Czy to nie zadziała?

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

Każde niezrównoważone drzewo zawsze by to zawiodło.


4
Wiele zbalansowanych drzew też to zawiedzie.
Brian
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.