Деревья в java

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

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

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

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

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

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

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

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

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

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

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

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

Код

public class Node {

    public int key; //ключ узла
    public String data; //некоторые данные в узле
    public Node leftChild; //левый потомок
    public Node rightChild; //правый потомок

    /**
     * Метод который выводит на экран содержимое узла
     */
    public void printNode(){
        System.out.println("KEY " + key + " DATA: " + data);
    }
}

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

Код

public class Tree {

    Node root;

    /**
     * Поиск элемента в дереве по ключу
     * @param key
     * @return
     */
    public Node find(int key){
        Node current = root;
        while(current.key!=key){
            if(current.key<key){
                current = current.leftChild;
            }else{
                current = current.rightChild;
            }
            if(current==null){
                return null;
            }
        }
        return current;
    }

    /**
     * Вставка в дерево. Суть таже что и поиск
     * Только вместо вывода элемента к нему левым или правым потомком
     * добавляем новый элемент
     * @param key
     * @param data
     */
    public void insert(int key, String data){
        Node node = new Node();
        node.key = key;
        node.data = data;
        if(root==null){
            root = node;
        }else{
            Node current = root;
            Node prev = null;
            while (true){
                prev = current;
                if(key<prev.key){
                    current = current.leftChild;
                    if(current==null){
                        prev.leftChild = node;
                        return;
                    }
                }else{
                    current = current.rightChild;
                    if(current==null){
                        prev.rightChild = node;
                        return;
                    }
                }
            }
        }
    }

    /**
     * Вывод всех элементов дерева методом асиметричного обхода
     * @param startNode
     */
    public void print(Node startNode){
        if(startNode != null){//условие сработает, когда мы достигним конца дерева и потомков не останется
            print(startNode.leftChild);//рекурсивно вызываем левых потомков
            startNode.printNode();//вызов метода принт
            print(startNode.rightChild);//вызов правых
        }
    }
}

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

Код

public class Main {

    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.insert(3, "John");
        tree.insert(8, "T1000");
        tree.insert(1, "Sara");
        tree.insert(2, "T800");

        Node findJohn = tree.find(3);
        findJohn.printNode();

        tree.print(findJohn);
    }
}

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

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

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