Структури даних: Двійкове дерево в Java

Привіт привіт! Важко бути потужним програмістом без базових знань. І тут мають на увазі як знання синтаксису рідної мови програмування, а й основ і концепцій програмування загалом. Одними з таких основ є алгоритми та структури даних. Як правило, у цьому питанні хтось обізнаний більше, хтось менше, але є деяка база, яку повинні знати всі. Серед баз структур даних обов'язково варто розібратися з деревами двійкового пошуку. Власне, сьогодні ми розглянемо саму структуру з її особливостями та дізнаємося, як можна реалізувати двійкове дерево Java . Спочатку давайте розберемося, що таке двійкове дерево. Двійкове дерево - структура даних, в якій коженвузол (батьківський) має трохи більше двох нащадків (правий і лівий спадкоємець). На практиці зазвичай використовуються два види двійкових дерев – двійкове дерево пошуку та піраміда (купа). Сьогодні ми розглянемо двійкове пошукове дерево.

Переваги двійкового дерева

У чому полягає перевага зберігання даних у вигляді двійкового дерева пошуку? Уявіть, що ми маємо довідник на 100 сторінок, і нам потрібно знайти певну сторінку, на якій буде записано необхідні нам дані. Також ми знаємо за змістом, яка саме сторінка нам потрібна. Якщо ми йтимемо звичайним шляхом, доведеться перегортати поспіль по одній сторінці, поки не дістанемося до необхідної нам. Тобто ми переберемо від 1 до 100 сторінок, поки не опинимося на потрібному місці. Наприклад, якщо нам потрібна 77 сторінка, то ми матимемо 77 переборів. Якщо говорити про тимчасову складність, то це буде О(N) . Але ж це можна зробити більш ефективно? Давайте спробуємо зробити те саме, але вже за допомогою двійкового пошуку :

1. Ділимо довідник на дві частини, перша - від 1 до 50, друга 51-100. Ми точно знаємо, в якій із цих частин наша сторінка: якщо знову ж таки брати 77 сторінку — у другій частині книги.
2. Далі розглядаємо другу частину і ділимо її на дві - від 51 до 75, від 76 до 100. У цьому випадку наша сторінка знову буде в другій половині, в проміжку 76-100.
3. Далі ділимо і цей проміжок на 2 і отримуємо 76-88 та 89-100. Сторінка входить у перший проміжок, тому другий відкидаємо.
4. Далі проміжки: 76-81 та 82-88, беремо перший.
5. 76-78 та 79-81, беремо перший.
6. 76 та 77-78, беремо другий.
7. 77 та 78, беремо перший і отримуємо нашу сторінку - 77.

Замість 77 кроків нам знадобилося лише 7! Тимчасова складність цього пошуку буде O(log(N)) .

Правила побудови дерева двійкового пошуку

Двійкове дерево пошуку будується за певними правилами:

• кожен вузол має трохи більше двох дітей;
• кожне значення, менше значення вузла, стає лівою дитиною або дитиною лівої дитини;
• кожне значення, більше чи рівне значенню вузла, стає правою дитиною чи дитиною правої дитини.

Наприклад, у нас є ряд із чисел від 1 до 10. Давайте подивимося, як виглядатиме дерево двійкового пошуку для цього ряду: Давайте подумаємо, чи дотримуються тут всі умови бінарного дерева:

• всі вузли мають не більше двох спадкоємців, перша умова дотримується;
• якщо ми розглянемо наприклад вузол зі значенням 7(або будь-який інший), то побачимо, що всі значення елементів у лівому піддереві будуть меншими, у правому — більшими. А це означає, що умови 2 та 3 дотримані.

Розберемо, як відбуваються основні операції — вставка, видалення, пошук.

Пошук елемента

При пошуку елемента із заданим значенням ми починаємо з кореневого елемента:

1. Якщо він дорівнює шуканому значенню, кореневий елемент і є шуканим, якщо ні - порівнюємо значення кореневого та шуканого.
2. Якщо потрібний елемент більший, ми переходимо до правого нащадка, якщо ні — до лівого.
3. Якщо елемент не знайдено, застосовуємо кроки 1 і 2, але вже до нащадка (правого або лівого) доти, доки елемент не буде знайдений.

Наприклад, у продемонстрованому вище дереві двійкового пошуку ми хочемо знайти елемент зі значенням 5:

• порівнюємо його з кореневим елементом, бачимо, що кореневий більше, тому ми переходимо до лівого нащадка, який має значення 3;
• порівнюємо шуканий і елемент зі значенням 3, бачимо, що шуканий більше, тому нам потрібен правий нащадок елемента, що розглядається, а саме - елемент зі значенням 5;
• порівнюємо цього нащадка з шуканим і бачимо, що значення рівні елемент знайдений.

Вставка елемента

Алгоритм вставки теж вельми простий:

1. Порівнюємо новий із кореневим (якщо його немає — новий елемент і є кореневим).

2. Якщо новий елемент:

   • менше, то переходимо до лівого спадкоємця, якщо його немає, новий елемент займає місце лівого спадкоємця, і алгоритм закінчено;
   • більше чи дорівнює кореневому, ми переходимо до правому спадкоємцю. І аналогічно, якщо даного елемента немає, новий елемент займе місце правого елемента і алгоритм закінчено.

3. Для нового аналізованого елемента, який був правим або лівим з попереднього кроку, повторюємо кроки 1 і 2 до тих пір, поки елемент, що вставляється, не стане на своє місце.

   Як приклад ми захочемо вставити в дерево, що розглядається вище, елемент зі значенням 11:

   • порівнюємо з кореневим елементом 7 і бачимо, що кореневий менше, тому переходимо до правого спадкоємця;
   • наступний аналізований елемент має значення 9, що менше ніж новий 11 тому переходимо до правого спадкоємцю;
   • правий спадкоємець має значення 10, що знову ж таки менше, тому ми переходимо до першого елементу, а оскільки його немає, то новий елемент зі значенням 11 і стає на це місце.
   ↓

Видалення елемента

Мабуть, із усіх операцій із деревами двійкового пошуку, видалення – найскладніша. У першу чергу відбувається пошук елемента, що видаляється, після знаходження якого слідує етап, у якого можуть бути три варіації:

1. Вузол, що видаляється, є листовим (не має нащадків).

   Мабуть, найпростіший. Все зводиться до того, що ми просто відсікаємо від дерева, без зайвих маніпуляцій. Наприклад, з нашого дерева ми видаляємо вузол зі значенням 8:

   ↓

2. Вузол, що видаляється, має одного нащадка.

   У такому разі ми видаляємо вибраний вузол, і на його місце ставимо його нащадка (по суті просто виріжемо вибраний вузол з ланцюжка). Як приклад видалимо з дерева вузол зі значенням 9:

   ↓

3. Вузол, що видаляється, має двох нащадків.

   Найцікавіша частина. Адже якщо вузол, що видаляється, має відразу двох нащадків, не можна просто так замінити його одним з цих нащадків (особливо якщо у нащадка є власні нащадки).

   Приклад: у цьому дереві, який вузол повинен бути лівим нащадком вузла 3?

   Якщо трохи замислитись, то стане очевидно, що це має бути вузол зі значенням 4. Ну а якщо дерево не буде таким простим? Якщо воно вміщуватиме сотні значень, чи так просто зрозуміти, хто буде наступником?

   Зрозуміло, що ні. Тому тут потрібний свій невеликий алгоритм пошуку приймача:

   1. Спочатку ми повинні перейти до правого нащадка обраного вузла, значення якого має бути більшим за значення вузла.
   2. Після цього ми переходимо до лівого нащадка правого нащадка (якщо такий існує), далі — до лівого нащадка лівого нащадка і т. д., прямуючи вниз ланцюгом лівих нащадків.
   3. Відповідно, останній лівий нащадок на цьому шляху і буде наступником вихідного вузла.

   Давайте трохи узагальним цей невеликий алгоритм: у піддереві правого нащадка вихідного вузла всі вузли більше віддаленого, що можна зрозуміти з основних правил дерева двійкового пошуку. У цьому піддереві ми шукаємо найменше значення.

   Іншими словами, ми шукаємо найменший вузол у наборі вузлів, більших за вихідний вузл. Цей найменший вузол серед великих і буде найбільш відповідним наступником.

   Як виглядатиме дерево після видалення вузла зі значенням 3:

   ↓

А тепер настав час перейти від практики до теорії. Давайте поглянемо, яким чином можна відобразити цю структуру даних в Java. Клас одного вузла:

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

   public void printNode() { // Вывод значения узла в консоль
       System.out.println(" Выбранный узел имеет значення :" + 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 +
               '}';
   }
}

Нічого особливо складного: кожен елемент має посилання на лівого та правого нащадка. А тепер, мабуть, найважливіший клас – клас дерева:

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

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

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

   public void insertNode(int value) { // метод вставки нового елемента
       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 { // або движение вправо?
               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; // элемент успешно удалён
   }

   // метод возвращает узел со следующим значенням после передаваемого аргументом.
   // для этого он сначала переходим к правому потомку, а затем
   // отслеживаем цепочку левых потомков этого узла.
   private Node receiveHeir(Node node) {
       Node parentNode = node;
       Node heirNode = node;
       Node currentNode = node.getRightChild(); // Переход к правому потомку
       while (currentNode != null) // Пока остаются левые потомки
       {
           parentNode = heirNode;// потомка задаём як текущий узел
           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; // начальное значення расстояния между елементами
       boolean isRowEmpty = false;
       String separator = "-----------------------------------------------------------------";
       System.out.println(separator);// черта для указания начала нового дерева
       while (isRowEmpty == false) {
           Stack localStack = new Stack(); // локальный стек для задания потомков елемента
           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()); // выводим его значення в консоли
                   localStack.push(temp.getLeftChild()); // соохраняем в локальный стек, наследники текущего елемента
                   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;// при переходе на следующий уровень расстояние между елементами каждый раз уменьшается
           while (localStack.isEmpty() == false)
               globalStack.push(localStack.pop()); // перемещаем все элементы из локального стека в глобальный
       }
       System.out.println(separator);// подводим черту
   }
}

Знову ж таки, нічого особливо складного. Існують операції для дерева двійкового пошуку, описані раніше, плюс метод для відображення дерева в консолі. Ну а тепер поглянемо на дерево у дії:

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

Операції пошуку/вставки/видалення в дереві двійкового пошуку мають тимчасову складність O(log(N)) . Але це у кращому випадку. Взагалі, тимчасова складність операцій варіюється від O(log(N)) до O(N) . Це від ступеня виродженості дерева.

Що таке вироджене дерево?

Це дерево, в якому елементи потрапляли при додаванні до позиції крайнього лівого вузла (найменше число) або крайнього більшого вузла (найбільші). Це може статися, якщо, наприклад, все ліве дерево порожнє на кожному рівні, є тільки праві дерева, і в такому випадку дерево вироджується до списку (що йде праворуч). Так, саме так вироджене дерево фактично стає однозв'язним списком, в якому кожен елемент знає лише про подальше за ним. У такому разі всі операції з цієї структури наближаються до тимчасової складності O(N) .

У якому разі дерево може стати виродженим?

Наприклад, якщо додавати список відсортованих елементів. Якщо список відсортований за зростанням, то коренем буде перший, відповідно найменший. Наступний після нього займе позицію правого нащадка. А той, який потрапить після, буде більшим за другий і займе позицію його правого наступника, і так далі… Якщо ж список буде за спаданням, то буде те саме, але вже з крайніми лівими елементами. Щоб уникнути цього, можна після отримання ряду елементів просто перемішати їх. Тоді сортованість зникне, і числа буде більш-менш рівномірно розкидані по дереву. На цьому у мене сьогодні все, дякую за приділену увагу!