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

Двоичное дерево поиска (binary search tree, BST) это структура данных, в которой у каждого узла не больше двух потомков, все значения в левом поддереве меньше значения узла, а в правом больше. Благодаря этому поиск, вставка и удаление на каждом шаге отбрасывают половину оставшихся элементов и в среднем занимают O(log n). В статье: зачем нужно такое дерево, правила построения, алгоритмы поиска, вставки и удаления с картинками, полная реализация на Java (классы Node и Tree) и случай, когда дерево вырождается в список.

Кратко

• У узла двоичного дерева поиска не больше двух потомков: слева значения меньше узла, справа больше. Корень делит все множество на две половины.
• Поиск, вставка и удаление идут от корня и на каждом шаге отбрасывают половину дерева: для сбалансированного дерева это O(log n).
• Удаление: лист просто отрезаем, узел с одним потомком заменяем этим потомком, узел с двумя потомками заменяем преемником, наименьшим узлом правого поддерева.
• Реализация в статье: класс Node (значение, левый и правый потомок) и класс Tree с методами findNodeByValue, insertNode, deleteNode и printTree; дубликаты при вставке отбрасываются.
• Если добавлять уже отсортированные значения, дерево вырождается в список и все операции становятся O(n); лечится перемешиванием данных или самобалансирующимся деревом.
• Готовое сбалансированное дерево в JDK это TreeMap и TreeSet: красно-черное дерево с гарантированным O(log n) на операцию.

Сложно быть сильным программистом без базовых знаний. И здесь имеется в виду не только знание синтаксиса родного языка программирования, но и основ и концепций программирования в целом. Одними из таких основ являются алгоритмы и структуры данных. Как правило в данном вопросе кто-то осведомлен больше, кто-то меньше, но есть некоторая база, которую должны знать все. Среди баз для структур данных обязательно стоит разобраться с деревьями двоичного поиска. Собственно, сегодня мы рассмотрим саму структуру с ее особенностями и узнаем, как можно реализовать двоичное дерево в 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

А теперь пришло время перейти от теории к практике. Давайте взглянем, каким же образом можно отобразить данную структуру данных в Java.

Класс узла Node

Класс одного узла:

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

Ничего особо сложного: каждый элемент имеет ссылку на левого и правого потомка.

Класс дерева Tree

А теперь, пожалуй, самый важный класс, класс дерева:

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

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

   public Node findNodeByValue(int value) { // поиск узла по значению
       if (rootNode == null) { // в пустом дереве искать нечего
           return null;
       }
       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) // Удаление узла с заданным ключом
   {
       if (rootNode == null) { // в пустом дереве удалять нечего
           return false;
       }
       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; // узел не найден
       }

       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);
           heir.setLeftChild(currentNode.getLeftChild()); // левое поддерево удаляемого узла переходит к преемнику
       }
       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<Node> globalStack = new Stack<>(); // общий стек для значений дерева
       globalStack.push(rootNode);
       int gaps = 32; // начальное значение расстояния между элементами
       boolean isRowEmpty = false;
       String separator = "-----------------------------------------------------------------";
       System.out.println(separator);// черта для указания начала нового дерева
       while (isRowEmpty == false) {
           Stack<Node> localStack = new Stack<>(); // локальный стек для задания потомков элемента
           isRowEmpty = true;

           for (int j = 0; j < gaps; j++)
               System.out.print(' ');
           while (globalStack.isEmpty() == false) { // покуда в общем стеке есть элементы
               Node temp = 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: самобалансирующиеся деревья. TreeMap и TreeSet реализованы как красно-черное дерево, которое перестраивает себя при каждой вставке и удалении и по документации Oracle гарантирует O(log n) на операцию при любом порядке добавления.

Сложность операций: сравнение структур

Как дерево двоичного поиска выглядит на фоне соседей: На этом у меня сегодня все, спасибо за уделенное внимание!

Вопросы и ответы

Что такое двоичное дерево поиска?

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

Чем двоичное дерево поиска отличается от обычного двоичного дерева и от кучи?

Обычное двоичное дерево требует только «не больше двух потомков», порядок значений не важен. Дерево поиска добавляет правило «слева меньше, справа больше». Куча (пирамида) тоже двоичное дерево, но с другим правилом: родитель больше (или меньше) обоих потомков, а порядок между левым и правым не задан; куча нужна для быстрого доступа к максимуму или минимуму, а не для поиска произвольного значения.

Какая сложность операций у двоичного дерева поиска?

Поиск, вставка и удаление занимают время, пропорциональное высоте дерева. Для сбалансированного дерева из n узлов высота около log n, поэтому операции O(log n). В худшем случае, когда значения добавляли по возрастанию или убыванию, дерево вырождается в цепочку высотой n и все операции становятся O(n). Самобалансирующиеся деревья (красно-черное, AVL) держат высоту O(log n) всегда.

Как удалить узел с двумя потомками?

Заменить его преемником: наименьшим узлом правого поддерева (идем в правого потомка, затем до упора влево). Преемник встает на место удаляемого, получает его левое поддерево, а свой правый потомок оставляет на прежнем месте в цепочке. Симметрично можно взять предшественника, наибольший узел левого поддерева. В коде статьи это делают receiveHeir и ветка «два потомка» в deleteNode.

Как обойти двоичное дерево и получить отсортированный список?

Обходом «в порядке» (in-order): сначала рекурсивно обходим левое поддерево, потом узел, потом правое. Для дерева поиска такой обход выдает значения по возрастанию. Есть еще прямой обход (узел, левое, правое), удобный для копирования дерева, и обратный (левое, правое, узел), удобный для удаления. Метод printTree из статьи делает обход по уровням через стек.

Есть ли готовое двоичное дерево в Java?

Класса «просто BST» в стандартной библиотеке нет, но есть TreeMap и TreeSet: это красно-черное дерево, которое само балансируется и гарантирует O(log n) для put, get, remove и contains. Они хранят элементы отсортированными, умеют искать ближайшие значения (floor, ceiling) и брать диапазоны (subMap, subSet). Свое дерево пишут в учебных целях или когда нужна нестандартная логика.

Читайте также

• Коллекции в Java: Java Collections Framework
• ArrayList в Java
• Comparator в Java