Struktury danych: drzewo binarne w Javie

Cześć cześć! Trudno być dobrym programistą bez podstawowej wiedzy. I mamy tutaj na myśli nie tylko znajomość składni natywnego języka programowania, ale także podstawy i koncepcje programowania w ogóle. Jednym z tych fundamentów są algorytmy i struktury danych. Z reguły jedni mają większą wiedzę w tym temacie, inni mniej, ale są pewne podstawowe informacje, które każdy powinien znać. Spośród baz danych dla struktur danych na pewno warto zapoznać się z drzewami wyszukiwania binarnego. Właściwie dzisiaj przyjrzymy się samej strukturze i jej funkcjom i dowiemy się, jak zaimplementować drzewo binarne w Javie . Najpierw zastanówmy się, czym jest drzewo binarne. Drzewo binarne to struktura danych, w której każdy węzeł (rodzic) ma co najwyżej dwoje dzieci (prawy i lewy spadkobierca). W praktyce powszechnie stosowane są dwa rodzaje drzew binarnych – drzewo wyszukiwania binarnego i piramida (sterta). Dzisiaj przyjrzymy się drzewu wyszukiwania binarnego.

Korzyści z drzewa binarnego

Jaka jest zaleta przechowywania danych w postaci drzewa wyszukiwania binarnego? Wyobraź sobie, że mamy 100-stronicowy podręcznik i musimy znaleźć konkretną stronę, która będzie zawierać potrzebne nam dane. Z treści wiemy też, jakiej konkretnej strony potrzebujemy. Jeśli pójdziemy zwykłą ścieżką, będziemy musieli przewracać jedną stronę na raz, aż dotrzemy do tej, której potrzebujemy. Oznacza to, że przejdziemy od 1 do 100 stron, aż znajdziemy się we właściwym miejscu. Na przykład, jeśli potrzebujemy strony 77, będziemy mieli 77 wyszukiwań. Jeśli mówimy o złożoności czasowej, to będzie to O(N) . Ale można to zrobić skuteczniej, prawda? Spróbujmy zrobić to samo, ale używając wyszukiwania binarnego :

1. Katalog dzielimy na dwie części, pierwsza - od 1 do 50, druga - 51-100. Wiemy dokładnie, w której z tych części znajduje się nasza strona: jeśli ponownie weźmiemy stronę 77, będzie to druga część książki.
2. Następnie rozważamy drugą część i dzielimy ją na dwie - od 51 do 75, od 76 do 100. W tym przypadku nasza strona ponownie znajdzie się w drugiej połowie, w przedziale 76-100.
3. Następnie dzielimy ten przedział przez 2 i otrzymujemy 76-88 i 89-100. Strona mieści się w pierwszą lukę, więc drugą odrzucamy.
4. Następne są przedziały: 76-81 i 82-88, weź pierwszy.
5. 76-78 i 79-81, weź pierwszy.
6. 76 i 77-78, weź drugi.
7. 77 i 78, weź pierwszy i zdobądź naszą stronę - 77.

Zamiast 77 kroków potrzebowaliśmy tylko 7! Złożoność czasowa tego wyszukiwania będzie wynosić O(log(N)) .

Zasady konstruowania drzewa poszukiwań binarnych

Drzewo wyszukiwania binarnego budowane jest według pewnych zasad:

• każdy węzeł ma co najwyżej dwoje dzieci;
• każda wartość mniejsza niż wartość węzła staje się lewym dzieckiem lub dzieckiem lewego dziecka;
• każda wartość większa lub równa wartości węzła staje się właściwym dzieckiem lub dzieckiem odpowiedniego dziecka.

Przykładowo mamy ciąg liczb od 1 do 10. Zobaczmy jak będzie wyglądało drzewo wyszukiwania binarnego dla tej serii: Zastanówmy się, czy spełnione są tutaj wszystkie warunki drzewa binarnego:

• wszystkie węzły mają nie więcej niż dwóch spadkobierców, pierwszy warunek jest spełniony;
• jeśli weźmiemy pod uwagę na przykład węzeł o wartości 7 (lub jakikolwiek inny), zobaczymy, że wszystkie wartości elementów w lewym poddrzewie będą mniejsze, a w prawym - większe. Oznacza to, że spełnione są warunki 2 i 3.

Przyjrzyjmy się, jak przebiegają podstawowe operacje - wstawianie, usuwanie, wyszukiwanie.

Wyszukaj element

Szukając elementu o podanej wartości zaczynamy od elementu głównego:

1. Jeśli jest równy żądanej wartości, element główny jest pożądany, jeśli nie, porównujemy wartości pierwiastka i pożądanego.
2. Jeśli szukany element jest większy, przechodzimy do prawego dziecka, jeśli nie, przechodzimy do lewego dziecka.
3. Jeśli element nie zostanie znaleziony, wykonaj kroki 1 i 2, ale do dziecka (prawego lub lewego), aż element zostanie znaleziony.

Przykładowo w pokazanym powyżej drzewie wyszukiwania binarnego chcemy znaleźć element o wartości 5:

• porównujemy go z elementem głównym, widzimy, że element główny jest większy, więc przechodzimy do lewego dziecka, które ma wartość 3;
• porównujemy ten, którego szukamy, z elementem o wartości 3, widzimy, że ten, którego szukamy, jest większy, więc potrzebny jest prawy potomek danego elementu, czyli elementu o wartości 5;
• Porównujemy tego potomka z tym, którego szukamy i widzimy, że wartości są równe – element zostaje znaleziony.

Wstawianie elementu

Algorytm wstawiania jest również bardzo, bardzo prosty:

1. Porównujemy nowy element z pierwotnym (jeśli nie istnieje, nowym elementem jest element główny).

2. Jeżeli nowy element:

   • jest mniejsza, to przechodzimy do lewego spadkobiercy, jeśli go nie ma, nowy element zajmuje miejsce lewego spadkobiercy i algorytm jest zakończony;
   • jest większa lub równa pierwiastkowi, wówczas przechodzimy do prawego spadkobiercy. I podobnie, jeśli tego elementu nie ma, to nowy element zajmie miejsce prawidłowego elementu i algorytm zostanie zakończony.

3. W przypadku nowego elementu, który w poprzednim kroku był prawy lub lewy, powtarzaj kroki 1 i 2, aż wstawiony element znajdzie się na swoim miejscu.

   Jako przykład będziemy chcieli wstawić do rozważanego powyżej drzewa element o wartości 11:

   • porównujemy z elementem głównym 7 i widzimy, że element główny jest mniejszy, więc przechodzimy do prawego spadkobiercy;
   • następny rozważany element ma wartość 9, czyli mniej niż nowe 11, więc przechodzimy do prawego spadkobiercy;
   • prawy spadkobierca ma wartość 10, czyli znowu mniej, więc przechodzimy do pierwszego elementu, a ponieważ go nie ma, w tym miejscu umieszczany jest nowy element o wartości 11.
   ↓

Usuwanie elementu

Być może ze wszystkich operacji na drzewach wyszukiwania binarnego usuwanie jest najtrudniejsze. W pierwszej kolejności następuje wyszukiwanie elementu do usunięcia, po czym następuje etap, który może mieć trzy warianty:

1. Węzeł do usunięcia jest węzłem liścia (nie ma dzieci).

   Być może najprostszy. Wszystko sprowadza się do tego, że po prostu odcinamy go od drzewa, bez zbędnych manipulacji. Przykładowo z naszego drzewa usuwamy węzeł o wartości 8:

   ↓

2. Usuwany węzeł ma jedno dziecko.

   W tym przypadku usuwamy wybrany węzeł i umieszczamy na jego miejscu jego potomka (w zasadzie po prostu wycinamy wybrany węzeł z łańcucha). Przykładowo usuńmy z drzewa węzeł o wartości 9:

   ↓

3. Usuwany węzeł ma dwoje dzieci.

   Najciekawsza część. W końcu, jeśli usuwany węzeł ma dwoje dzieci na raz, nie można go po prostu zastąpić jednym z tych dzieci (zwłaszcza jeśli dziecko ma własne dzieci).

   Przykład: który węzeł w powyższym drzewie powinien być lewym dzieckiem węzła 3?

   Jeśli się nad tym trochę zastanowić, staje się oczywiste, że powinien to być węzeł o wartości 4. Ale co, jeśli drzewo nie jest takie proste? Jeśli zawiera setki wartości, czy łatwo będzie ustalić, kto będzie następcą?

   To jasne, że nie. Dlatego potrzebujemy własnego algorytmu wyszukiwania małego odbiornika:

   1. Najpierw musimy udać się do prawego dziecka wybranego węzła, którego wartość musi być większa od wartości węzła.
   2. Następnie przechodzimy do lewego dziecka prawego dziecka (jeśli takie istnieje), następnie do lewego dziecka lewego dziecka itd., podążając w dół łańcucha lewych dzieci.
   3. W związku z tym ostatnie lewe dziecko na tej ścieżce będzie następcą pierwotnego węzła.

   Uogólnijmy trochę ten mały algorytm: w poddrzewie prawego dziecka węzła źródłowego wszystkie węzły są większe niż ten, który jest usuwany, co można zrozumieć z podstawowych zasad drzewa wyszukiwania binarnego. W tym poddrzewie szukamy najmniejszej wartości.

   Innymi słowy, szukamy najmniejszego węzła w zbiorze węzłów większym niż węzeł pierwotny. Ten najmniejszy węzeł spośród większych będzie najodpowiedniejszym następcą.

   Jak będzie wyglądać drzewo po usunięciu węzła o wartości 3:

   ↓

Teraz czas przejść od praktyki do teorii. Przyjrzyjmy się, jak możemy wyświetlić tę strukturę danych w Javie. Klasa pojedynczego węzła:

class Node {
   private int value; // ключ узла
   private Node leftChild; // Левый узел потомок
   private Node rightChild; // Правый узел потомок

   public void printNode() { // Вывод значения узла в консоль
       System.out.println(" Выбранный узел имеет oznaczający :" + value);
   }

   public int getValue() {
       return this.value;
   }

   public void setValue(final int value) {
       this.value = value;
   }

   public Node getLeftChild() {
       return this.leftChild;
   }

   public void setLeftChild(final Node leftChild) {
       this.leftChild = leftChild;
   }

   public Node getRightChild() {
       return this.rightChild;
   }

   public void setRightChild(final Node rightChild) {
       this.rightChild = rightChild;
   }

   @Override
   public String toString() {
       return "Node{" +
               "value=" + value +
               ", leftChild=" + leftChild +
               ", rightChild=" + rightChild +
               '}';
   }
}

Nic zbyt skomplikowanego: każdy element ma link do swojego lewego i prawego dziecka. A teraz być może najważniejszą klasą jest klasa drzewa:

class Tree {
   private Node rootNode; // корневой узел

   public Tree() { // Пустое дерево
       rootNode = null;
   }

   public Node findNodeByValue(int value) { // поиск узла по значению
       Node currentNode = rootNode; // начинаем поиск с корневого узла
       while (currentNode.getValue() != value) { // поиск покуда не будет найден элемент Lub не будут перебраны все
           if (value < currentNode.getValue()) { // движение влево?
               currentNode = currentNode.getLeftChild();
           } else { //движение вправо
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null) { // если потомка нет,
               return null; // возвращаем null
           }
       }
       return currentNode; // возвращаем найденный элемент
   }

   public void insertNode(int value) { // метод вставки нового element
       Node newNode = new Node(); // создание нового узла
       newNode.setValue(value); // вставка данных
       if (rootNode == null) { // если корневой узел не существует
           rootNode = newNode;// то новый элемент и есть корневой узел
       }
       else { // корневой узел занят
           Node currentNode = rootNode; // начинаем с корневого узла
           Node parentNode;
           while (true) // мы имеем внутренний выход из цикла
           {
               parentNode = currentNode;
               if(value == currentNode.getValue()) {   // если такой элемент в дереве уже есть, не сохраняем его
                    return;    // просто выходим из метода
                }
                else  if (value < currentNode.getValue()) {   // движение влево?
                   currentNode = currentNode.getLeftChild();
                   if (currentNode == null){ // если был достигнут конец цепочки,
                       parentNode.setLeftChild(newNode); //  то вставить слева и выйти из методы
                       return;
                   }
               }
               else { // Или направо?
                   currentNode = currentNode.getRightChild();
                   if (currentNode == null) { // если был достигнут конец цепочки,
                       parentNode.setRightChild(newNode);  //то вставить справа
                       return; // и выйти
                   }
               }
           }
       }
   }

   public boolean deleteNode(int value) // Удаление узла с заданным ключом
   {
       Node currentNode = rootNode;
       Node parentNode = rootNode;
       boolean isLeftChild = true;
       while (currentNode.getValue() != value) { // начинаем поиск узла
           parentNode = currentNode;
           if (value < currentNode.getValue()) { // Определяем, нужно ли движение влево?
               isLeftChild = true;
               currentNode = currentNode.getLeftChild();
           }
           else { // Lub движение вправо?
               isLeftChild = false;
               currentNode = currentNode.getRightChild();
           }
           if (currentNode == null)
               return false; // yзел не найден
       }

       if (currentNode.getLeftChild() == null && currentNode.getRightChild() == null) { // узел просто удаляется, если не имеет потомков
           if (currentNode == rootNode) // если узел - корень, то дерево очищается
               rootNode = null;
           else if (isLeftChild)
               parentNode.setLeftChild(null); // если нет - узел отсоединяется, от родителя
           else
               parentNode.setRightChild(null);
       }
       else if (currentNode.getRightChild() == null) { // узел заменяется левым поддеревом, если правого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getLeftChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getLeftChild());
           else
               parentNode.setRightChild(currentNode.getLeftChild());
       }
       else if (currentNode.getLeftChild() == null) { // узел заменяется правым поддеревом, если левого потомка нет
           if (currentNode == rootNode)
               rootNode = currentNode.getRightChild();
           else if (isLeftChild)
               parentNode.setLeftChild(currentNode.getRightChild());
           else
               parentNode.setRightChild(currentNode.getRightChild());
       }
       else { // если есть два потомка, узел заменяется преемником
           Node heir = receiveHeir(currentNode);// поиск преемника для удаляемого узла
           if (currentNode == rootNode)
               rootNode = heir;
           else if (isLeftChild)
               parentNode.setLeftChild(heir);
           else
               parentNode.setRightChild(heir);
       }
       return true; // элемент успешно удалён
   }

   // метод возвращает узел со следующим oznaczającyм после передаваемого аргументом.
   // для этого он сначала переходим к правому потомку, а затем
   // отслеживаем цепочку левых потомков этого узла.
   private Node receiveHeir(Node node) {
       Node parentNode = node;
       Node heirNode = node;
       Node currentNode = node.getRightChild(); // Переход к правому потомку
       while (currentNode != null) // Пока остаются левые потомки
       {
           parentNode = heirNode;// потомка задаём Jak текущий узел
           heirNode = currentNode;
           currentNode = currentNode.getLeftChild(); // переход к левому потомку
       }
       // Если преемник не является
       if (heirNode != node.getRightChild()) // правым потомком,
       { // создать связи между узлами
           parentNode.setLeftChild(heirNode.getRightChild());
           heirNode.setRightChild(node.getRightChild());
       }
       return heirNode;// возвращаем приемника
   }

   public void printTree() { // метод для вывода дерева в консоль
       Stack globalStack = new Stack(); // общий стек для значений дерева
       globalStack.push(rootNode);
       int gaps = 32; // начальное oznaczający расстояния между elementми
       boolean isRowEmpty = false;
       String separator = "-----------------------------------------------------------------";
       System.out.println(separator);// черта для указания начала нового дерева
       while (isRowEmpty == false) {
           Stack localStack = new Stack(); // локальный стек для задания потомков element
           isRowEmpty = true;

           for (int j = 0; j < gaps; j++)
               System.out.print(' ');
           while (globalStack.isEmpty() == false) { // покуда в общем стеке есть элементы
               Node temp = (Node) globalStack.pop(); // берем следующий, при этом удаляя его из стека
               if (temp != null) {
                   System.out.print(temp.getValue()); // выводим его oznaczający в консоли
                   localStack.push(temp.getLeftChild()); // соохраняем в локальный стек, наследники текущего element
                   localStack.push(temp.getRightChild());
                   if (temp.getLeftChild() != null ||
                           temp.getRightChild() != null)
                       isRowEmpty = false;
               }
               else {
                   System.out.print("__");// - если элемент пустой
                   localStack.push(null);
                   localStack.push(null);
               }
               for (int j = 0; j < gaps * 2 - 2; j++)
                   System.out.print(' ');
           }
           System.out.println();
           gaps /= 2;// при переходе на следующий уровень расстояние между elementми каждый раз уменьшается
           while (localStack.isEmpty() == false)
               globalStack.push(localStack.pop()); // перемещаем все элементы из локального стека в глобальный
       }
       System.out.println(separator);// подводим черту
   }
}

Powtórzę: nic zbyt skomplikowanego. Dostępne są opisane wcześniej operacje na drzewie wyszukiwania binarnego, a także metoda wyświetlania drzewa w konsoli. Cóż, teraz przyjrzyjmy się drzewu w akcji:

public class Application {
   public static void main(String[] args) {
       Tree tree = new Tree();
       // вставляем узлы в дерево:
       tree.insertNode(6);
       tree.insertNode(8);
       tree.insertNode(5);
       tree.insertNode(8);
       tree.insertNode(2);
       tree.insertNode(9);
       tree.insertNode(7);
       tree.insertNode(4);
       tree.insertNode(10);
       tree.insertNode(3);
       tree.insertNode(1);
       // отображение дерева:
       tree.printTree();

       // удаляем один узел и выводим оставшееся дерево в консоли
       tree.deleteNode(5);
       tree.printTree();

       // находим узел по значению и выводим его в консоли
       Node foundNode = tree.findNodeByValue(7);
       foundNode.printNode();
   }
}

Operacje wyszukiwania/wstawiania/usuwania w drzewie wyszukiwania binarnego mają złożoność czasową O(log(N)) . Ale to najlepszy scenariusz. Ogólnie rzecz biorąc, złożoność czasowa operacji waha się od O(log(N)) do O(N) . Zależy to od stopnia degeneracji drzewa.

Co to jest drzewo zdegenerowane?

Jest to drzewo, w którym elementy spadły po dodaniu do pozycji skrajnego lewego węzła (najmniejsza liczba) lub największego węzła najbardziej wysuniętego (największy). Może się to zdarzyć, jeśli na każdym poziomie całe lewe drzewo jest puste, są tylko prawe drzewa, w takim przypadku drzewo przeradza się w listę (idąc w prawo). Tak, w ten sposób zdegenerowane drzewo faktycznie staje się pojedynczo połączoną listą, w której każdy element wie tylko o następnym. W tym przypadku wszystkie operacje na tej strukturze zbliżają się do złożoności czasowej O(N) .

W jakim przypadku drzewo może się zdegenerować?

Na przykład, jeśli dodasz listę posortowanych elementów. Jeśli lista jest posortowana rosnąco, to pierwiastek będzie pierwszy, odpowiednio najmniejszy. Następny po nim zajmie pozycję odpowiedniego dziecka. A ta, która nastąpi później, będzie większa od drugiej i zajmie pozycję swojego prawego następcy, i tak dalej... Jeśli lista będzie w porządku malejącym, to stanie się to samo, ale z elementami skrajnie lewymi. Aby tego uniknąć, po otrzymaniu pewnej liczby elementów można je po prostu wymieszać. Wtedy sortowanie zniknie, a liczby będą mniej więcej równomiernie rozrzucone po całym drzewie. To wszystko na dziś, dziękujemy za uwagę!