Деревья в java

В этой статье мы поговорим о деревьях и в частности о двоичных (бинарных) деревьях в программировании:

  • для чего нужны деревья;
  • что называют деревом в программировании;
  • закрепим теорию примером на языке java.

В статье о коллекциях в java я упоминал такое понятие как скорость вставки и поиска элемента в определенной структуре данных. Всем известно, что поиск элемента выполняется быстрее в массивах, чем в списках. Однако, вставка элемента в конец и в средину списка выполняется медленнее, чем в массиве. Если Вы этого не знали — будете знать. Конечно, не все так однозначно и просто как я написал в выше. Если интересна эта тема — можно поискать информацию на этот счет.

Такие структуры как деревья имеют преимущества как массивов, так и списков. Вставка и удаление в деревьях так же быстро как и в списках, а поиск работает как в массивах. Поэтому деревья заслужили уважение и широкое применение в информационных системах.

Дерево — одна из самых распространенных структур данных в программировании. Оно представляет собой древовидную структуру в виде корня и связанных узлов, соединенных ребрами.

дерево в java

Рисунок выше — пример дерева. Ребра это отношения между узлами. А если мы говорим на языке java — то ссылки. Узлы — это сущности или ближе к нашей теме — объекты.

Чтобы не плодить кучу слов с теорией я представлю Вам картинку с книги: Роберта Лафоре «Структуры данных и алгоритмы», которая наглядно демонстрирует всю сущность деревьев.

терминология деревьев

В программировании, когда говорят о деревьях, то часто имеют ввиду именно двоичные деревья. Это те, в которых каждый узел имеет не более двух потомков. Если не понял — смотреть картинку выше. На ней изображено двоичное дерево. С картинки выше видно, что два потомка именуются левым и правым в зависимости от стороны в которой они расположены от родителя. Узлы размещаются в дереве не просто так. Помимо того, что каждый узел хранит данные у него есть ключ. У бинарного дерева ключ левого потомка меньше, чем у родителя, а правого — больше или равно родительскому.

двоичное дерево

При изучении деревьев часто встречается такое понятие как сбалансированность дерева. Дерево считается сбалансированным если имеет примерно одинаковое количество элементов относительно корня. Тоже самое касается и поддерева. На рисунке ниже представлен пример несбалансированного дерева.

не сбалансированное дерево

Если дерево сбалансировано, операции с ним буду выполняться быстрее.

Теперь давайте попробуем сами написать реализацию этой замечательной структуры данных. Тем более, что на собеседованиях очень часто просят это сделать. Да и знать как это делается для себя будет очень полезно.

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

Код    
  1. public class Node {
  2.  
  3.     public int key; //ключ узла
  4.     public String data; //некоторые данные в узле
  5.     public Node leftChild; //левый потомок
  6.     public Node rightChild; //правый потомок
  7.  
  8.     /**
  9.      * Метод который выводит на экран содержимое узла
  10.      */
  11.     public void printNode(){
  12.         System.out.println("KEY " + key + " DATA: " + data);
  13.     }
  14. }

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

Код    
  1. public class Tree {
  2.  
  3.     Node root;
  4.  
  5.     /**
  6.      * Поиск элемента в дереве по ключу
  7.      * @param key
  8.      * @return
  9.      */
  10.     public Node find(int key){
  11.         Node current = root;
  12.         while(current.key!=key){
  13.             if(current.key<key){
  14.                 current = current.leftChild;
  15.             }else{
  16.                 current = current.rightChild;
  17.             }
  18.             if(current==null){
  19.                 return null;
  20.             }
  21.         }
  22.         return current;
  23.     }
  24.  
  25.     /**
  26.      * Вставка в дерево. Суть таже что и поиск
  27.      * Только вместо вывода элемента к нему левым или правым потомком
  28.      * добавляем новый элемент
  29.      * @param key
  30.      * @param data
  31.      */
  32.     public void insert(int key, String data){
  33.         Node node = new Node();
  34.         node.key = key;
  35.         node.data = data;
  36.         if(root==null){
  37.             root = node;
  38.         }else{
  39.             Node current = root;
  40.             Node prev = null;
  41.             while (true){
  42.                 prev = current;
  43.                 if(key<prev.key){
  44.                     current = current.leftChild;
  45.                     if(current==null){
  46.                         prev.leftChild = node;
  47.                         return;
  48.                     }
  49.                 }else{
  50.                     current = current.rightChild;
  51.                     if(current==null){
  52.                         prev.rightChild = node;
  53.                         return;
  54.                     }
  55.                 }
  56.             }
  57.         }
  58.     }
  59.  
  60.     /**
  61.      * Вывод всех элементов дерева методом асиметричного обхода
  62.      * @param startNode
  63.      */
  64.     public void print(Node startNode){
  65.         if(startNode != null){//условие сработает, когда мы достигним конца дерева и потомков не останется
  66.             print(startNode.leftChild);//рекурсивно вызываем левых потомков
  67.             startNode.printNode();//вызов метода принт
  68.             print(startNode.rightChild);//вызов правых
  69.         }
  70.     }
  71. }

Теперь попробуем протестировать работу нашего приложения.

Код    
  1. public class Main {
  2.  
  3.     public static void main(String[] args) {
  4.         Tree tree = new Tree();
  5.         tree.insert(3, "John");
  6.         tree.insert(8, "T1000");
  7.         tree.insert(1, "Sara");
  8.         tree.insert(2, "T800");
  9.  
  10.         Node findJohn = tree.find(3);
  11.         findJohn.printNode();
  12.  
  13.         tree.print(findJohn);
  14.     }
  15. }

Результат работы приложения:

результат работы приложения

Как видите, выводятся уже упорядоченные элементы. Это еще одна особенность деревьев.

Я сознательно упустил метод удаления элемента из дерева. Он довольно сложный и я не хотел делать материал обширным. Всю теорию и пример я взял из книги «Структуры данных и алгоритмы» Р. Лафоре. В ней Вы сможете найти очень подробное описание деревьев с полным примером кода на java. Данной статьи вполне достаточно чтобы понять деревья и быть готовым к вопросам по ним на собеседованиях. Как правило, спрашивают только вывод элементов дерева, который довольно простой. А в повседневной практике программирования пользуйтесь готовыми структурами данных: коллекциями и мапами.

One thought on “Деревья в java

Добавить комментарий