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