JavaRush /Java блог /Java Developer /Структуры данных: двоичное дерево в Java
Константин
36 уровень

Структуры данных: двоичное дерево в Java

Статья из группы Java Developer
Привет-привет! Сложно быть сильным программистом без базовых знаний. И здесь имеется в виду не только знание синтаксиса родного языка программирования, но и основ и концепций программирования в целом. Одними из таких основ являются алгоритмы и структуры данных. Как правило в данном вопросе кто-то осведомлен больше, кто-то меньше, но есть некоторая база, которую должны знать все. Среди баз для структур данных обязательно стоит разобраться с деревьями двоичного поиска. Структуры данных: двоичное дерево в Java - 1Собственно, сегодня мы рассмотрим саму структуру с её особенностями и узнаем, как можно реализовать двоичное дерево в Java. Для начала давайте же разберемся, что такое двоичное дерево. Двоичное де́рево — структура данных, в которой каждый узел (родительский) имеет не более двух потомков (правый и левый наследник).Структуры данных: двоичное дерево в Java - 2На практике обычно используются два вида двоичных деревьев — двоичное дерево поиска и пирамида (куча). Сегодня мы рассмотрим двоичное дерево поиска.

Преимущества двоичного дерева

В чем состоит преимущество хранения данных в виде двоичного дерева поиска? Представьте, что у нас есть справочник на 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. Давайте посмотрим, как будет выглядеть дерево двоичного поиска для этого ряда:Структуры данных: двоичное дерево в Java - 3Давайте подумаем, соблюдаются ли тут все условия бинарного дерева:
  • все узлы имеют не более двух наследников, первое условие соблюдается;
  • если мы рассмотрим к примеру узел со значением 7(или любой другой), то увидим что все значения элементов в левом поддереве будут меньше, в правом — больше. А это значит, что условия 2 и 3 соблюдены.
Разберем, каким образом происходят основные операции — вставка, удаление, поиск.

Поиск элемента

При поиске элемента с заданным значением мы начинаем с корневого элемента:
  1. Если он равен искомому значению, корневой элемент и есть искомый, если нет — сравниваем значения корневого и искомого.
  2. Если искомый элемент больше, мы переходим к правому потомку, если нет — к левому.
  3. Если элемент не найден, применяем шаги 1 и 2, но уже к потомку (правому или левому) до тех пор, пока элемент не будет найден.
К примеру, в продемонстрированном выше дереве двоичного поиска мы хотим найти элемент со значением 5:
  • сравниваем его с корневым элементом, видим, что корневой больше, поэтому мы переходим к левому потомку, который имеет значение 3;
  • сравниваем искомый и элемент со значением 3, видим, что искомый больше, поэтому нам нужен правый потомок рассматриваемого элемента, а именно — элемент со значением 5;
  • сравниваем этого потомка с искомым и видим, что значения равны — элемент найден.
  • Структуры данных: двоичное дерево в Java - 4

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

Алгоритм вставки тоже весьма и весьма прост:
  1. Сравниваем новый с корневым (если его нет — новый элемент и есть корневой).

  2. Если новый элемент:

    • меньше, то переходим к левому наследнику, если его нет, новый элемент и занимает место левого наследника, и алгоритм закончен;
    • больше или равен корневому, то мы переходим к правому наследнику. И аналогично, если данного элемента нет, то новый элемент займет место правого элемента и алгоритм закончен.

  3. Для нового рассматриваемого элемента, который был правым или левым из предыдущего шага, повторяем шаги 1 и 2 до тех пор, пока вставляемый элемент не станет на свое место.

    В качестве примера мы захотим вставить в рассматриваемое выше дерево, элемент со значением 11:

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

    Структуры данных: двоичное дерево в Java - 5
    Структуры данных: двоичное дерево в Java - 6

Удаление элемента

Пожалуй, из всех операций с деревьями двоичного поиска, удаление — наиболее сложная. В первую очередь происходит поиск удаляемого элемента, после нахождения которого следует этап, у которого могут быть три вариации:
  1. Удаляемый узел является листовым (не имеет потомков).

    Пожалуй, самый простой. Всё сводится к тому, что мы его просто отсекаем от дерева, без лишних манипуляций. К примеру, из нашего дерева мы удаляем узел со значением 8:

    Структуры данных: двоичное дерево в Java - 7
    Структуры данных: двоичное дерево в Java - 8
  2. Удаляемый узел имеет одного потомка.

    В таком случае мы удаляем выбранный узел, и на его место ставим его потомка (по сути просто вырежем выбранный узел из цепочки). В качестве примера удалим из дерева узел со значением 9:

    Структуры данных: двоичное дерево в Java - 9
    Структуры данных: двоичное дерево в Java - 10
  3. Удаляемый узел имеет двух потомков.

    Самая интересная часть. Ведь если удаляемый узел имеет сразу двух потомков, нельзя просто так заменить его одним из этих потомков (особенно если у потомка есть собственные потомки).

    Пример: в рассматриваемом выше дереве, какой узел должен быть левым потомком узла 3?

    Если немного задуматься, то станет очевидно, что это должен быть узел со значением 4. Ну а если дерево не будет таким простым? Если оно будет вмещать сотни значений, будет ли так просто понять, кто будет преемником?

    Понятное дело, что нет. Поэтому тут нужен свой небольшой алгоритм поиска приемника:

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

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

    Иными словами, мы ищем наименьший узел в наборе узлов, больших исходного узла. Этот наименьший узел среди больших и будет наиболее подходящим преемником.

    Как будет выглядеть дерево после удаления узла со значением 3:

    Структуры данных: двоичное дерево в Java - 11
    Структуры данных: двоичное дерево в Java - 12
А теперь пришло время перейти от практики к теории. Давайте взглянем, каким же образом можно отобразить данную структуру данных в 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).

В каком случае дерево может стать вырожденным?

Например, если добавлять список отсортированных элементов. Если список отсортирован по возрастанию, то корнем будет первый, соответственно, наименьший. Следующий после него займет позицию правого потомка. А тот, который попадет после, будет больше второго и займет позицию его правого преемника, и так далее… Если же список будет по убыванию, то будет то же самое, но уже с крайними левыми элементами. Чтобы избежать этого, можно после получения ряда элементов попросту их перемешать. Тогда сортированность пропадет, и числа будет более-менее равномерно разбросаны по дереву. Структуры данных: двоичное дерево в Java - 13На этом у меня сегодня всё, спасибо за уделенное внимание!Структуры данных: двоичное дерево в Java - 14
Комментарии (18)
ЧТОБЫ ПОСМОТРЕТЬ ВСЕ КОММЕНТАРИИ ИЛИ ОСТАВИТЬ КОММЕНТАРИЙ,
ПЕРЕЙДИТЕ В ПОЛНУЮ ВЕРСИЮ
Валерий Уровень 23
16 января 2024
В тексте небольшая ошибочка. От теории к практике...
Vlad V Уровень 35
4 февраля 2023
"Пример: в рассматриваемом выше дереве, какой узел должен быть левым потомком узла 3? Если немного задуматься, то станет очевидно, что это должен быть узел со значением 4." Наверное имеется ввиду какой узел должен заменить узел 3. Ведь левым потомком должно быть значение меньше чем 3.
odslkfhvad Уровень 0
30 июля 2022
1. В чем проблема рассказать про балансировку бинарного дерева? 2. Термин рекурсия вам о чём либо говорит?
Jan Уровень 47
3 мая 2022
Добрый день! В методе "receiveHeir(Node node)" в блоке условия "if (heirNode != node.getRightChild())" не хватает строчки "heirNode.setLeftChild(node.getLeftChild());" Тогда при удалении узла с двумя потомками сохранится левый потомок, который в текущем коде теряется.
Василь Уровень 28
29 октября 2021
Спасибо за статью!
Василь Уровень 28
29 октября 2021
здесь тоже опечатка: // метод возвращает узел со следующим значением после передаваемого аргументом. // для этого он сначала переходим к правому потомку, а затем // отслеживаем цепочку левых потомков этого узла. З.Ы. без обид за правки! Статья действительно толковая!
Василь Уровень 28
29 октября 2021
Если я правильно понимаю смысл который должно нести предложение, то: А теперь пришло время перейти от практики к теории. нужно заменить на: А теперь пришло время перейти от теории к практике.
Aleksey Grin Уровень 22
29 октября 2021
Зачем выводить адрес узла? Разве нас в данном случае не значение интересует? @Override public String toString() { return "Node{" + "value=" + value + ", leftChild=" + leftChild + ", rightChild=" + rightChild + '}'; }
Yulia A Уровень 13
31 июля 2021
Попробуйте удалять не 5, а 8 (чтобы были оба потомка) - левая ветвь от 8 теряется
gwin Уровень 14
14 декабря 2020
В бинарном дереве все значения элементов в левом поддереве будут меньше, в правом — больше. В Вашем примере корень с элементом 8 имеет потомка с элементом 8. Это нарушает принцип бинарного дерева. Только начал изучать Ваш курс и тут такие косяки...