Binarne drzewo poszukiwań (BST – binary search tree)

Cześć 🙂 w tym wpisie opiszę działanie binarnego drzewa przeszukań. Zajmę się wstawieniem oraz znalezieniem najmniejszej i największej wartości. Na zakończenie przejdziemy przez drzewo w sposób poprzeczny czyli in-order.

W uproszczeniu drzewo to struktura danych która składa się z węzłów (wierzchołków) i krawędzi. W tej strukturze danych występuje tylko jedna droga która łączy dwa wierzchołki. Tą droga jest właśnie krawędź. Węzeł początkowy nazywany jest korzeniem ponieważ od niech rozchodzą się pozostałe węzły. W drzewach binarnych od jednego wierzchołka wychodzą dwa inne węzły: lewy i prawy (inaczej potomek). Węzły od których wychodzą kolejne węzły nazywamy wewnętrznymi. Natomiast wierzchołki które nie posiadają kolejnych odgałęzień nazywamy końcowymi.

Źródło: Archiwum własne

Wartość przechowywana w węźle jest nazywana kluczem. W drzewie binarnym opartym na kluczach lewy potomek posiada klucz mniejszy od swojego rodzica (przodka). Natomiast prawy większy lub równy.

Zobaczmy teraz w jaki sposób wstawiać wartości do binarnego drzewa poszukiwań. W tym celu została zdefiniowana klasa BinaryNode wraz z zdefiniowanymi potomkami, konstruktorem oraz metodą wypisującą dane.

public class BinaryNode {
public int nodeKey;   // wartość klucza 
 BinaryNode left;  // lewy potomek
 BinaryNode right; // prawy potomek

//konstruktor
...

public void pisz() {..}
}

Aby móc wstawić wartość w węzeł należy utworzyć nowy nowy węzeł new BinaryNode i poszukać odpowiednie miejsce do wstawienia nowego potomka. Jeżeli nasz korzeń mainNode jest pusty to wstawiamy potomka. W przeciwnym razie szukamy wolnego miejsca poprzez porównywanie wartości (value) którą chcemy wstawić z wartościami kluczy. Wykorzystamy do tego zmienną tymczasowa tmp która przechowa nam wartość mainNode oraz zdefiniujemy przodka czyli parent. Wykorzystamy do tego również pętle while w której będziemy porównywać wartości. I jeżeli nasza wartość jest mniejsza od korzenia wówczas idziemy na lewo i sprawdzamy czy jest tam wolne miejsce if(tmp == null) i jeśli tak to wstawiamy element. Jeżeli nie to analogicznie kierujemy się na prawo i powtarzamy procedurę.

public class BinaryTree {

    public BinaryNode mainNode; // korzeń główny drzewa BST

    public BinaryTree(){
     mainNode = null; 
} 
public void putIntoTree(int value) {
BinaryNode bn = new BinaryNode(value); 

if(mainNode == null) 
mainNode = bn;
    else{                   
        BinaryNode tmp = mainNode;
        BinaryNode parent;
        while(true) { 
            parent = tmp;
            if(value < tmp.nodeKey) { // na lewo
                tmp = tmp.left;
                if(tmp == null){ 
                    parent.left = bn;
                    break;
                }
            } else // na prawo
            {
                tmp = tmp.right;
                if(tmp == null) {  
                    parent.right = bn;
                    break;
                }
            }
        } 
    }
}

Ok. Więc teraz przyszedł czas na wyszukanie wartości np. najmniejszej lub największej. Wykorzystajmy do tego wiedze już posiadaną. Skoro najmniejszy element oznacza to więc wyszukiwanie tylko po lewej stronie drzewa. Dla uproszczenia metoda searchMin również znajduje się w klasie BinaryTree. Jeżeli szukana wartość jest różna od null to szukaj na lewo. Następnie wydrukuj ten element.

public void searchMin() { 
BinaryNode tmp = mainNode;
       while (tmp.left != null) { 
        tmp = tmp.left;
}
 tmp.printT();
 System.out.println();
}

Analogicznie będzie wyglądać metoda na znalezienie największego elementu. Jedyna różnicą jest tutaj przeszukiwanie drzewa po prawej stronie.

public void searchMax() { 
BinaryNode tmp = mainNode;
       while (tmp.right != null) { 
        tmp = tmp.right;
}
 tmp.printT();
 System.out.println();
}

Teraz pozostało już przejście po naszym drzewie in-order czyli w sposób poprzeczny. W ten sposób najpierw otrzymamy wartości lewych potomków, głównego węzła oraz prawego drzewa. Przy czym przechodząc przez drzewo w taki sposób realizowane jest jednocześnie sortowanie. Do napisania tej metody została wykorzystana rekurencja. Sprawdzamy czy węzeł jest różny od null i jeśli tak właśnie jest drukujemy kolejno wartości w sposób rosnący.

public void inOrder(BinaryNode bn) {
    if(bn != null) {
        inOrder(bn.left); bn.printT(); inOrder(bn.right);
    }
}

Poniżej zamieściłam wynik z wykonanych metod. Dane liczbowe wprowadziłam dokładnie takie same jakie znajdują się na początkowym rysunku drzewa czyli 10, 5, 20, 25, 8, 3, 17, 6, 9, 15, 19. W związku z czym korzeniem drzewa jest liczba 10.

Źródło: Archiwum własne

Zakres opisany tutaj zapoczątkowuje tylko tematykę struktur danych i binarnych drzew przeszukiwań.

Jeśli uważasz powyższy tekst za pomocny, będę wdzięczna za podanie go dalej oraz zapraszam do subskrypcji. Do zobaczenia w kolejnym wpisie 🙂 🙂 !!

Źródła z których korzystałam:

  • “Algorytmy struktury danych i techniki programowania dla programistów Java” – Piotr Wróblewski
  • “Algorytmy Ilustrowany przewodnik” – Aditya Y. Bhargava

2 Komentarze

  1. Twój rysunek (o ile jest to drzewo BST) nie jest do końca poprawny. Wartość 7 powinna być w lewym poddrzewie, bo jest mniejsza niż wartość korzenia. BST nie musi być zbalansowane.

    • Tak jest to drzewo binarne. Dodałam dodatkowe węzły. Mam nadzieje że rysunek będzie to teraz lepiej przedstawiał. Przyznaje że łatwiej było mi to narysować w kwadratach nich w kołach. Dziękuje za tą uwagę. Tak masz racje 7 powinno być po lewej stronie już poprawiłam 🙂 . Tak dokładnie drzewo nie musi być zrównoważone jednak jest ono wtedy mniej efektywne podczas przeszukiwań. Występują również drzewa samo równoważące się. Myślę że mogę to rozwinąć w jednym z kolejnych wpisów 🙂 .

Dodaj komentarz

Twój adres email nie zostanie opublikowany.


*