Binarne drzewo poszukiwań (BST – binary search tree)

Cześć 🙂 w tym wpisie opiszę jak działa binarne drzewo 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.

Drzewo binarne – co to jest

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.

Binarne drzewo przeszukań - graficzna prezentacja drzewa. Drzewo posiada dwa węzły lewy i prawy.
Źródło: Drzewo binarne poszukiwań (BST- Binary Search Tree). 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.

Drzewo binarne i wstawianie wartości

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

Wyszukiwanie binarne

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

Przejście po drzewie binarnym

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.

Wynik przejścia po drzewie binarnym in-order. Wynik pokazuje kolejno wynik lewego węzła, głównego i prawego.
Źródło: Wynik przejścia po drzewie binarnym in-order. Archiwum własne

Zakres opisany tutaj zapoczątkowuje tylko tematykę struktur danych i binarnych drzew przeszukiwań i jest jednym z artykułów na temat algorytmów. Więcej informacji na temat drzewa binarnego w wersji anglojęzycznej znajdziesz pod: Binary tree.

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:
  • “Algorytmy struktury danych i techniki programowania dla programistów Java” – Piotr Wróblewski
  • “Algorytmy Ilustrowany przewodnik” – Aditya Y. Bhargava

2 thoughts on “Binarne drzewo poszukiwań (BST – binary search tree)”

  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.

    1. 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 🙂 .

Leave a Comment

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *