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

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?

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.

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).

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.

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     

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

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

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

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

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.

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

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.

Jeśli to do Twojej pracy , proponuję:

1. nie wymyślaj na nowo koła i
2. używaj / kup COTS zamiast bawić się bitami.
3. Oszczędzaj czas / energię na rozwiązywanie problemów biznesowych.

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

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

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

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.

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

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ę.

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

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

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

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
}

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

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)

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;

}

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

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.