Ta notatka dotyczy dość znanej i popularnej strukturze jaką jest drzewo binarne.

Co to jest drzewo binarne?

Drzewa posiadają korzeń, gałęzie oraz liście, w strukturze drzewa jest podobnie, z tym, że jest różne nazewnictwo poszczególnych elementów takiej struktury. Drzewo binarne wyróżnia się tym, że liczba gałęzi od każdego wierzchołka nie jest większa niż 2. Powiedzmy, że pierwszym wierzchołkiem jest korzeń, nie może mieć on więcej niż 2 dzieci, następnie schodzimy niżej i każde z jego dzieci też nie może mieć więcej niż 2 dzieci i tak dalej…

Jak widać na powyższym drzewie, wierzchołek może mieć maksymalnie 2 gałęzie, ale może mieć też 1.

Szukanie w drzewie binarnym

Aby wyszukiwać w drzewie binarnym powinno być ono prawidłowo poukładane/posortowane, gałąź po lewej stronie zawsze powinna mieć niższą wartość niż gałąź po prawej stronie. Jest to wtedy tak zwane Binarne Drzewo Poszukiwań (BST – Binary Search Tree). Sprawia to, że bardzo łatwo szukać elementu w takim drzewie. Powiedzmy, że w strukturze której zdjęcie jest wyżej, chcemy wyszukać liczbę 4. Idąc od góry sprawdzamy czy liczba 4 jest większa czy mniejsza niż root (8), jest mniejsza więc idziemy w lewą stronę, teraz czy liczba 4 jest większa czy mniejsza niż liczba 3? Jest większa więc idziemy w prawo, jesteśmy teraz przy liczbie 6 która jest większa niż 4 więc idziemy w lewo. I voila! Po 3 sprawdzeniach znaleźliśmy liczbę.

W Javie to będzie np. taki kod, samo sprawdzanie czy element istnieje w drzewie:

/* 
ten kod pochodzi z tego filmu: https://www.youtube.com/watch?v=oSWTXtMglKE 
aczkolwiek przepisałem go do IDE i w pełni go rozumiem 
*/
public class Node {

    private Node left, right;
    private final int data;

    public Node(int data) {
        this.data = data;
    }

    public boolean contains(int value) {
        if (value == data) {
            return true;
        } else if (value < data) {
            if (left == null) {
                return false;
            } else {
                return left.contains(value);
            }
        } else {
            if (right == null) {
                return false;
            } else {
                return right.contains(value);
            }
        }
    }
}

Dodawanie elementu do drzewa

Dodawanie odbywa się w taki sam sposób jak wyszukiwanie wartości z tym, że szukamy dogodnego miejsca do umieszczenia nowego elementu. Sprawdzamy czy wartość nowego elementu, jest mniejsza czy większa niż porównywany wierzchołek. Jeśli mniejsza to idziemy w lewo, jeśli większa to w prawo, i tak aż znajdziemy miejsce...

W Javie można to napisać z użyciem rekurencji:

/* 
ten kod pochodzi z tego filmu: https://www.youtube.com/watch?v=oSWTXtMglKE 
aczkolwiek przepisałem go do IDE i w pełni go rozumiem 
*/
public void insert(int value) {
    if (value <= data) {
        if (left == null) {
            left = new Node(value);
        } else {
            left.insert(value);
        }
    } else {
        if (right == null) {
            right = new Node(value);
        } else {
            right.insert(value);
        }
    }
}

Jaki jest problem z wyszukiwaniem i dodawaniem nowego elementu?

Jeśli dodajemy posortowane elementy, to po prostu robi nam się zwykła lista (taka jedna długa gałąź), co znacznie obniża efektywność takiego rozwiązania, w najgorszym przypadku wpadamy w złożoność obliczeniową O(n) czy to przy wyszukiwaniu z takiego "drzewa" czy przy dodawaniu. Zoptymalizowane drzewa mają tą złożoność na poziomie O(log n). Takie drzewo to np. drzewo czerwono-czarne.

Przechodzenie po drzewie - traversing

Są 3 sposoby przechodzenia po drzewie binarnym. Uporządkowane (inorder), ?przed uporządkowaniem? (preorder) i ?po uporządkowaniu? (postorder). Nie wiem jak to do końca dobrze przetłumaczyć więc tak to zostawię.

• Preorder - root, później lewa, później prawa
• Inorder - lewa, root, prawa
• Postorder - lewa, prawa, root

Najlepiej jest przechodzić w sposób inorder czyli uporządkowany wtedy idąc od lewej do prawej, wartości wierzchołków są w kolejności rosnącej.

Drukowanie inorder, pozostałem przechodzenia wyglądają tak samo tylko trzeba pozamieniać linie.

/* 
ten kod pochodzi z tego filmu: https://www.youtube.com/watch?v=oSWTXtMglKE 
aczkolwiek przepisałem go do IDE i w pełni go rozumiem 
*/
public void printInOrder() {
        if (left != null) {
            left.printInOrder();   // (1)
        }
        System.out.println(data); //(2)
        if (right != null) {
            right.printInOrder(); //(3)
        }
}

Jeśli chcemy wydrukować w kolejnośći preorder to będzie idąc od góry (2), (1), (3), a jeśli w kolejności postorder to: (1), (3), (2).

Zadanie z drzewem binarnym

Dana funkcja isBinaryTree(strArr) jako argument przyjmuje tablicę Stringów, tablica ta zawiera pary liczb w następującym formacie: (i1, i2), gdzie i1 reprezentuje gałąź dziecko, a i2 reprezentuje gałąź rodzica dla i1. Np. ["(1, 2)", "(2, 4)", "(7, 2)"], jest to wtedy poprawne drzewo binarne, ponieważ każda gałąź ma nie więcej niż dwoje dzieci. Program ma zwracać boolean true jeśli dane drzewo jest poprawnym drzewem binarnym, i false jeśli nie jest. Wszystkie dane gałęzie będą unikalne to znaczy będzie tylko jeden node z daną wartością np. 2.

Moje rozwiązanie:

public static boolean isBinaryTree(String[] nodeValuesArray) {
    //najpierw wyjąłbym sobie wartości liczbowe z typu String
    Integer[] numbers = convertToIntegerArray(nodeValuesArray);
    /* żaden node nie może być rodzicem więcej niż 2 razy,
        można wywnioskować że wystarczy po prostu sprawidzić czy liczba na drugiej pozycji występuje więcej
        niż 2 razy, jeśli nie, to będzie to poprawne drzewo binarne */
    Map collect = IntStream.range(0, numbers.length)
            .filter(i -> i % 2 == 0)
            .map(i -> numbers[i+1])
            .boxed()
            .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
    return collect.values().stream().noneMatch(occurrence -> occurrence > 2);
}

private static Integer[] convertToIntegerArray(String[] nodeValuesArray) {
    return Arrays.stream(nodeValuesArray)
            .map(string -> string.replaceAll("\\)|\\(", ""))
            .map(string -> string.split(","))
            .flatMap(Stream::of)
            .map(Integer::parseInt)
            .toArray(Integer[]::new);
}

public static void main(String[] args) {
        String[] firstTree = {"(1,2)", "(2,4)", "(5,7)", "(7,2)", "(9,5)"};
        String[] secondTree = {"(1,2)", "(3,2)", "(2,12)", "(5,2)"};
        String[] thirdTree = {"(3,8)", "(10,8)", "(1,3)", "(6,3)", "(4,6)", "(7,6)", "(14,10)", "(13,14)"};

        System.out.println(isBinaryTree(firstTree)); //output true
        System.out.println(isBinaryTree(secondTree)); //output false
        System.out.println(isBinaryTree(thirdTree)); //output true
    }

Trochę "shackowałem" system bo nie użyłem nigdzie algorytmu drzewa, sprawdziłem po prostu czy "rodzic" występuje w tablicy stringów więcej niż 2 razy, jeśli tak to drzewo nie jest poprawne bo może mieć maksymalnie dwoje dzieci. Jak widać trzy podane "testy" przeszły, jeśli jednak jest jakieś drzewo, które jest poprawne a mój algorytm zwraca zły wynik, skontaktuj się ze mną abym mógł poprawić rozwiązanie.

Linki:

https://pl.wikipedia.org/wiki/Drzewo_binarne

https://pl.wikipedia.org/wiki/Binarne_drzewo_poszukiwa%C5%84