Бинарное дерево — двоичное дерево поиска. Основные операции с бинарными деревьями (C#, Java)

Что такое бинарное дерево

Бинарное дерево представляет собой иерархическую структуру данных, в которой каждый узел имеет не более двух дочерних узлов. Как правило, первый называется родительским узлом или корнем дерева (root), а дочерние узлы называются левым и правым наследниками.

Бинарное дерево либо является пустым, либо состоит из данных и двух поддеревьев, каждое из которых может быть пустым. Каждое поддерево в свою очередь тоже является деревом. Узлы без наследников принято называть листьями.

Для такого дерева должны выполняться следующие условия:

  1. Левое и правое поддерево так же являются бинарными деревьями;
  2. У всех узлов левого поддерева произвольного узла x значения ключей данных меньше значения ключа данных самого узла x;
  3. У всех узлов правого поддерева произвольного узла x значения ключей данных больше либо равны значению ключа данных самого узла x.

Основные операции с бинарным деревом

Основными операциями с бинарными деревьями являются добавление элемента в дерево, удаление элемента и поиск элемента в дереве. Сложность каждой из этих операций O(log\,n) в лучшем случае, и O(n) в худшем. Зависит от сбалансированности дерева.

Пример сбалансированного бинарного дерева (лучший случай):

Пример несбалансированного бинарного дерева (худший случай):Добавление элемента в дерево

При добавлении элемента x в дерево проверяем значение текущего узла.

  • Если значение добавляемого элемента x меньше значения текущего узла, спускаемся к левому поддереву. Если его не существует, то создаем его и присваиваем значение x. Если существует, то обозначим левое поддерево как текущий узел и повторим сначала.
  • Если значение добавляемого элемента x больше или равно значению текущего узла, спускаемся к правому поддереву. Если его не существует, то создаем его и присваиваем значение x. Если существует, то обозначим правое поддерево как текущий узел и повторим сначала.

Пример добавления элемента в двоичное дерево

Создадим бинарное дерево с корневым элементом 33 и добавим в него элементы в следующей последовательности: 5, 35, 1, 20, 99, 17, 18, 19, 31, 4. Получим бинарное дерево такого вида:

BinaryTree

Поиск элемента в бинарном дереве

Поиск начинаем с родительского элемента. Допустим, мы ищем значение 18 (обозначим его за x). Алгоритм поиска будет иметь следующий вид:

  1. x<33 — спускаемся в левое поддерево;
  2. x>5 — спускаемся в правое поддерево;
  3. x<20 — спускаемся в левое поддерево;
  4. x>17 — спускаемся в правое поддерево;
  5. x=18 — мы нашли элемент.

Добавление элемента в бинарное дерево

Поиск несуществующего элемента сведется к тому, что вы нарветесь на несуществующий узел и это будет означать, что искомого элемента в дереве нет.

Удаление элемента из бинарного дерева

Удаление листьев

Если удаляемый элемент является листом, то просто удаляем у его родителя ссылку на этот элемент (например на значение 31). Удалим его.

Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева

После удаления 31 элементом, имеющим левое поддерево, но не имеющим правого поддерева является элемент 20. Удалим его из дерева:

  1. Указываем, что родителем элемента 17 теперь будет элемент 5.
  2. Указываем, что правым потомком элемента 5 теперь является элемент 17.

После удаления значений 31 и 20 дерево приобретает такой вид:

Бинарное дерево на C#

Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева

  1. Удалим элемент 17. Присвоим его правому поддереву в качестве родителя элемент 5.
  2. Элементу 5 укажем, что его правым поддеревом теперь является элемент 18.

Получим следующую картину:Удаление элемента из бинарного дерева

Удаляем узел, имеющий поддеревья с обеих сторон

Первый случай

Правое поддерево не имеет потомка.

Чтобы иметь возможность рассмотреть этот случай, добавим элемент 34 в дерево:BinaryTreeУдалим элемент 35. Для этого:

  1. Правому поддереву (99) присвоим в качестве родителя элемент 33;
  2. Ему же в качестве левого поддерева присваиваем элемент 34;
  3. Элементу 34 указываем нового родителя — 99;
  4. Родителю удаляемого элемента (33) указываем, что его правым поддерево теперь является элемент 99.

Получим такое дерево:Бинарное дерево

Второй случай

Правое поддерево имеет своих потомков.

Удаляем элемент 5. Первым потомком (одновременно самым левым — минимальным в его поддереве) элемента 5 является элемент 18:

  1. Элементу 18 в качестве левого узла присвоим элемент 1;
  2. Элементу 1 присвоим 18 как родителя;
  3. Элементу 33 (родителю удаляемого элемента) укажем в качестве левого дочернего узла элемент 18;
  4. Элементу 18 указываем в качестве родителя элемент 33 (родитель удаляемого элемента).

Дерево приобретает такой вид:

Если минимальный левый элемент имеет правых потомков и при это не является первым потомком удаляемого элемента, то его правый потомок присваивается родителю минимального элемента правого поддерева.

В своем коде я использовал нерекурсивный механизм удаления.

Существуют и другие механизмы удаления. Визуализировать свое дерево вы можете на ресурсе usfca.edu. Вы заметите, что алгоритм удаления там отличается от описанного выше.

Код класса дерева на Java в моем исполнении имеет следующий вид:

package main;

import java.util.ArrayList;
import java.util.List;

public class Tree<T extends Comparable<T>> {
    private T val;
    private Tree left;
    private Tree right;
    private Tree parent;
    private List<T> listForPrint = new ArrayList<>();

    public T val() {
        return val;
    }

    public Tree left() {
        return left;
    }

    public Tree right() {
        return right;
    }

    public Tree parent() {
        return parent;
    }

    public Tree(T val, Tree parent) {
        this.val = val;
        this.parent = parent;
    }


    public void add(T...vals){
        for(T v : vals){
            add(v);
        }
    }

    public void add(T val){
        if(val.compareTo(this.val) < 0){
            if(this.left==null){
                this.left = new Tree(val, this);
            }
            else if(this.left != null)
                this.left.add(val);
        }
        else{
            if(this.right==null){
                this.right = new Tree(val, this);
            }
            else if(this.right != null)
                this.right.add(val);
        }
    }

    private Tree<T> _search(Tree<T> tree, T val){
        if(tree == null) return null;
        switch (val.compareTo(tree.val)){
            case 1: return _search(tree.right, val);
            case -1: return _search(tree.left, val);
            case 0: return tree;
            default: return null;
        }
    }

    public Tree<T> search(T val){
        return _search(this, val);
    }

    public boolean remove(T val){
        //Проверяем, существует ли данный узел
        Tree<T> tree = search(val);
        if(tree == null){
            //Если узла не существует, вернем false
            return false;
        }
        Tree<T> curTree;

        //Если удаляем корень
        if(tree == this){
            if(tree.right!=null) {
                curTree = tree.right;
            }
            else curTree = tree.left;

            while (curTree.left != null) {
                curTree = curTree.left;
            }
            T temp = curTree.val;
            this.remove(temp);
            tree.val = temp;

            return true;
        }

        //Удаление листьев
        if(tree.left==null && tree.right==null && tree.parent != null){
            if(tree == tree.parent.left)
                tree.parent.left = null;
            else {
                tree.parent.right = null;
            }
            return true;
        }

        //Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева
        if(tree.left != null && tree.right == null){
            //Меняем родителя
            tree.left.parent = tree.parent;
            if(tree == tree.parent.left){
                tree.parent.left = tree.left;
            }
            else if(tree == tree.parent.right){
                tree.parent.right = tree.left;
            }
            return true;
        }

        //Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева
        if(tree.left == null && tree.right != null){
            //Меняем родителя
            tree.right.parent = tree.parent;
            if(tree == tree.parent.left){
                tree.parent.left = tree.right;
            }
            else if(tree == tree.parent.right){
                tree.parent.right = tree.right;
            }
            return true;
        }

        //Удаляем узел, имеющий поддеревья с обеих сторон
        if(tree.right!=null && tree.left!=null) {
            curTree = tree.right;

            while (curTree.left != null) {
                curTree = curTree.left;
            }

            //Если самый левый элемент является первым потомком
            if(curTree.parent == tree) {
                curTree.left = tree.left;
                tree.left.parent = curTree;
                curTree.parent = tree.parent;
                if (tree == tree.parent.left) {
                    tree.parent.left = curTree;
                } else if (tree == tree.parent.right) {
                    tree.parent.right = curTree;
                }
                return true;
            }
            //Если самый левый элемент НЕ является первым потомком
            else {
                if (curTree.right != null) {
                    curTree.right.parent = curTree.parent;
                }
                curTree.parent.left = curTree.right;
                curTree.right = tree.right;
                curTree.left = tree.left;
                tree.left.parent = curTree;
                tree.right.parent = curTree;
                curTree.parent = tree.parent;
                if (tree == tree.parent.left) {
                    tree.parent.left = curTree;
                } else if (tree == tree.parent.right) {
                    tree.parent.right = curTree;
                }

                return true;
            }
        }
        return false;
    }


    private void _print(Tree<T> node){
        if(node == null) return;
        _print(node.left);
        listForPrint.add(node.val);
        System.out.print(node + " ");
        if(node.right!=null)
            _print(node.right);
    }

    public void print(){
        listForPrint.clear();
        _print(this);
        System.out.println();
    }

    @Override
    public String toString() {
        return val.toString();
    }
}

Поработать с классом можно следующим образом:

public static void main(String[] args) {
  //Создадим дерево с корневым элементом 33
  Tree<Integer> tree = new Tree<>(33, null);
  tree.add(5, 35, 1, 20, 4, 17, 31, 99, 18, 19);
  //Распечатаем элементы дерева
  tree.print();
  //Удалим корень
  tree.remove(33);
  tree.remove(17);

  tree.print();

  //Проверяем элементы дерева
  System.out.println(tree);
  System.out.println(tree.left());
  System.out.println(tree.left().left());
  System.out.println(tree.right().left());
}

Получим такой вывод:

Java Binary Tree Class Output

К слову, на Java такой код особого смысла писать нет, т.к. там существуют классы TreeSet и TreeMap, представляющие собой деревья.

На C# код класса бинарного дерева может иметь такой вид:

/*
 * User: Николай Разиов
 * Date: 29.10.2018
 */
using System;
using System.Collections.Generic;

namespace Trees
{
  public class BinaryTree<T> where T : IComparable<T>
  {
    private BinaryTree<T> parent, left, right;
    private T val;
    private List<T> listForPrint = new List<T>();
    
    public BinaryTree(T val, BinaryTree<T> parent)
    {
      this.val = val;
      this.parent = parent;
    }
    
    public void add(T val)
    {
          if(val.CompareTo(this.val) < 0){
              if(this.left==null){
                  this.left = new BinaryTree<T>(val, this);
              }
              else if(this.left != null)
                  this.left.add(val);
          }
          else{
              if(this.right==null){
                  this.right = new BinaryTree<T>(val, this);
              }
              else if(this.right != null)
                  this.right.add(val);
          }
    }
    
    private BinaryTree<T> _search(BinaryTree<T> tree, T val)
    {
          if(tree == null) return null;
          switch (val.CompareTo(tree.val)){
              case 1: return _search(tree.right, val);
              case -1: return _search(tree.left, val);
              case 0: return tree;
              default: return null;
          }
    	}
    
    public BinaryTree<T> search(T val)
    {
        	return _search(this, val);
    	}
    
    public bool remove(T val)
    {
          //Проверяем, существует ли данный узел
          BinaryTree<T> tree = search(val);
          if(tree == null){
              //Если узла не существует, вернем false
              return false;
          }
          BinaryTree<T> curTree;
  
          //Если удаляем корень
          if(tree == this){
              if(tree.right!=null) {
                  curTree = tree.right;
              }
              else curTree = tree.left;
  
              while (curTree.left != null) {
                  curTree = curTree.left;
              }
              T temp = curTree.val;
              this.remove(temp);
              tree.val = temp;
  
              return true;
          }
  
          //Удаление листьев
          if(tree.left==null && tree.right==null && tree.parent != null){
              if(tree == tree.parent.left)
                  tree.parent.left = null;
              else {
                  tree.parent.right = null;
              }
              return true;
          }
  
          //Удаление узла, имеющего левое поддерево, но не имеющее правого поддерева
          if(tree.left != null && tree.right == null){
              //Меняем родителя
              tree.left.parent = tree.parent;
              if(tree == tree.parent.left){
                  tree.parent.left = tree.left;
              }
              else if(tree == tree.parent.right){
                  tree.parent.right = tree.left;
              }
              return true;
          }
  
          //Удаление узла, имеющего правое поддерево, но не имеющее левого поддерева
          if(tree.left == null && tree.right != null){
              //Меняем родителя
              tree.right.parent = tree.parent;
              if(tree == tree.parent.left){
                  tree.parent.left = tree.right;
              }
              else if(tree == tree.parent.right){
                  tree.parent.right = tree.right;
              }
              return true;
          }
  
          //Удаляем узел, имеющий поддеревья с обеих сторон
          if(tree.right!=null && tree.left!=null) {
              curTree = tree.right;
  
              while (curTree.left != null) {
                  curTree = curTree.left;
              }
  
              //Если самый левый элемент является первым потомком
              if(curTree.parent == tree) {
                  curTree.left = tree.left;
                  tree.left.parent = curTree;
                  curTree.parent = tree.parent;
                  if (tree == tree.parent.left) {
                      tree.parent.left = curTree;
                  } else if (tree == tree.parent.right) {
                      tree.parent.right = curTree;
                  }
                  return true;
              }
              //Если самый левый элемент НЕ является первым потомком
              else {
                  if (curTree.right != null) {
                      curTree.right.parent = curTree.parent;
                  }
                  curTree.parent.left = curTree.right;
                  curTree.right = tree.right;
                  curTree.left = tree.left;
                  tree.left.parent = curTree;
                  tree.right.parent = curTree;
                  curTree.parent = tree.parent;
                  if (tree == tree.parent.left) {
                      tree.parent.left = curTree;
                  } else if (tree == tree.parent.right) {
                      tree.parent.right = curTree;
                  }
  
                  return true;
              }
          }
          return false;
      }
    
      private void _print(BinaryTree<T> node)
      {
          if(node == null) return;
          _print(node.left);
          listForPrint.Add(node.val);
          Console.Write(node + " ");
          if(node.right!=null)
              _print(node.right);
    	}

      public void print()
      {
          listForPrint.Clear();
          _print(this);
          Console.WriteLine();
      }
      
      public override string ToString()
    {
      	return val.ToString();
    }

  }
}

Код примерно такой же, только для C# он будет гораздо полезнее.

Исходники проектов можно взять здесь:

Github Java Binary Tree Github C# csharp Binary Tree

Задача о покрытии отрезков точками на Java

Решим задачу о покрытии отрезков точками.

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

На обучающих ресурсах эта задача имеет следующую формулировку:

Given n intervals. Find the set of points having the minimum size (cardinality), for which each of the given intervals contains at least one of the points.
The first line given 1\leq n \leq 100 – number of intervals. Each of the next n lines contains two 0\leq l \leq r \leq 10^9 numbers, setting the beginning and the end of the interval. Output the minimum size of the set m and the m points themselves. If there are several such sets, output any of them.

Пример решения задачи

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

№ отрезка 1 2 3 4 5 6
Края L:4; R:7 L:1; R:3 L:2; R:5 L:5; R:6 L:6; R:8 L:3; R:4

Да графике данные отрезки имеют следующий вид (на самом деле все они строятся на одной прямой, но лучше их начертить раздельно, чтобы видеть, с чем мы работаем):

Отрезки

Алгоритм покрытия отрезков точками

Берем все концы отрезков (как левые, так и правые) и сортируем их. Для каждой точки сохраним номер отрезка. Также каким концом его она является (левым или правым). Учтем, что если есть несколько точек с одной координатой, то сначала будут идти левые концы, потом правые.

Заведём коллекцию, в которой будут храниться номера отрезков, рассматриваемых в данный момент. Идем по точкам в отсортированном порядке. Если текущая точка — левый конец, то добавляем номер её отрезка в коллекцию. Иначе если она является правым концом, то проверяем, не был ли покрыт этот отрезок (был ли он добавлен в коллекцию). Если он уже был покрыт (его нет в коллекции), то ничего не делаем и переходим к следующей точке. Иначе если же он ещё не был покрыт (находится в коллекции), то мы добавляем текущую точку в ответ, и замечаем, что все текущие отрезки (которые в коллекции) становятся покрытыми. Опустошаем коллекцию.

По окончании работы алгоритма все отрезки будут покрыты наименьшим числом точек.

Таким образом, результатом обработки входных данных из таблицы выше являются две точки — 3 и 6:

Решенная задача

Показать текст ->

Заметим, что соединив эти точки в отрезок, мы «захватим» им все отрезки, которые у нас есть.

В результате точка может быть одна, захватывающая все отрезки.

Пример входных отрезков, которые захватывает одна точка

Предположим, у нас есть следующие входные данные:

№ отрезка 1 2 3
Края L:1; R:3 L:2; R:5 L:3; R:6

На графике решение будет иметь такой вид:

Все отрезки покрыты одной точкой

Нетрудно догадаться, что ответом является точка 3.

Реализация алгоритма покрытия отрезков на Java

Код Java в моем исполнении имеет следующий вид:

import java.util.*;

class Spot implements Comparable{
    int numOtrezok, spotval;
    char side;

    public Spot(int numOtrezok, int spotval, char side) {
        this.numOtrezok = numOtrezok;
        this.spotval = spotval;
        this.side = side;
    }

    @Override
    public int compareTo(Object o) {
        Spot spot = (Spot)o;
        int numres = this.spotval > spot.spotval ? 1 : this.spotval < spot.spotval ? -1 : 0;
        switch (numres){
            case 0: return side == 'R' ? 1 : -1;
            default: return numres;
        }
    }
}

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //Количество отрезков
        int n = sc.nextInt();
        int [][] otr = new int[n][];
        sc.nextLine();
        List<Spot> listSpots = new ArrayList<>();
        List<Integer> stack = new ArrayList<>();
        List<Integer> result = new ArrayList<>();

        //Получаем края отрезков и записываем в массив
        for (int i = 0; i < n; i++) {
            String[] split = sc.nextLine().split(" ");
            otr[i] = new int[2];
            otr[i][0] = Integer.parseInt(split[0]);
            otr[i][1] = Integer.parseInt(split[1]);
        }

        //Заполняем массив точек
        for (int i = 0; i < n; i+=1) {
            listSpots.add(new Spot(i + 1, otr[i][0], 'L'));
            listSpots.add(new Spot(i + 1, otr[i][1], 'R'));
        }

        //Сортируем массив точек
        listSpots.sort(Comparator.naturalOrder());

        //Следуем алгоритму, описанному в статье
        for (int i = 0; i < listSpots.size(); i++) {
            if(listSpots.get(i).side == 'L')
                stack.add(listSpots.get(i).numOtrezok);
            else if(stack.contains(listSpots.get(i).numOtrezok)){
                result.add(listSpots.get(i).spotval);
                stack.clear();
            }
        }

        System.out.println(result.size());
        result.forEach(integer -> System.out.print(integer + " "));
    }   
}

На вход подается количество отрезков и их края. Создан специальный класс Spot, имплементирующий интерфейс Comparable для правильной сортировки. Сложности только в заполнении коллекций. Остальное все по алгоритму.

В результате работы программы будет выведено количество точек и сами точки.

Подключаемся к базе данных с помощью JDBC. Выборка данных (Java)

В данной статье рассматриваем возможность подключение к БД с помощью JDBC.

Что такое JDBC

JDBC — это стандарт взаимодействия Java с различными СУБД, входящий в пакет java.sql.

Позволяет использовать один интерфейс для подключения к любым базам данных, для которых созданы JDBC коннекторы.

java-jdbc

Пример:

package Database;

import java.sql.*;

public class DB {
    private Connection connection;

    public DB(String driver, String conString, String user, String pass) throws SQLException, ClassNotFoundException {
        if(this.connection == null) {
            Class.forName(driver);
            this.connection = DriverManager.getConnection(conString, user, pass);

        }
    }

    public ResultSet select(String q) throws SQLException {
        Statement stmt = connection.createStatement();
        ResultSet rs = stmt.executeQuery(q);
        return rs;
    }

    public void close() throws SQLException{
        if(this.connection!=null)
            if(!this.connection.isClosed())
                this.connection.close();
    }
}

Здесь реализован конструктор, в котором осуществляется подключение к базе, метод select, выполняющий запрос и возвращающий результат в виде объекта ResultSet, и метод close, закрывающий соединение.

Так же мы избежали обработку исключений в конструкторе с помощью throws SQLException, ClassNotFoundException.

Можно поступить иначе: в блоке try создать подключение, а в блоке catch обработать исключения, выброшенные JDBC.

Я часто использую multicatch, имеющий следующий вид:

catch (SQLException | ClassNotFoundException ex){....}

Чтобы использовать multicatch необходимо в среде разработки поднять уровень языка до 8.

Если используете Maven, подойдет следующая конструкция:

<build>
        <plugins>
            <plugin>
                <artifactId>maven-assembly-plugin</artifactId>
                <configuration>
                    <archive>
                        <manifest>
                            <mainClass>Main.Main</mainClass>
                        </manifest>
                    </archive>
                    <descriptorRefs>
                        <descriptorRef>jar-with-dependencies</descriptorRef>
                    </descriptorRefs>
                </configuration>
            </plugin>
            <plugin>
                <groupId>org.apache.maven.plugins</groupId>
                <artifactId>maven-compiler-plugin</artifactId>
                <configuration>
                    <source>1.8</source>
                    <target>1.8</target>
                </configuration>
            </plugin>
        </plugins>
    </build>

Здесь говориться о том, что используется Main класс с именем Main, собираться проект будет в единый jar, уровень языка — 8.

Работать с объектом ResultSet можно следующим образом:

while (rs.next()){
    rs.getString(1);
    rs.getString(2);
    rs.getString(3);
}
rs.getStatement().close();

То есть считываем значения, пока они не закончатся. С помощью команды rs.getString(1) считываем значение из 1 колонки текущего кортежа в виде текста. Счет колонок начинается с единицы. То же касается с имен столбцов таблицы, считать которые можно так:

for (int i = 0; i < rs.getMetaData().getColumnCount(); i++) {
    rs.getMetaData().getColumnLabel(i + 1);
}

Примеры строк подключения

Oracle

jdbc:oracle:thin:@127.0.0.1:1521/serviceName

Имя драйвера: oracle.jdbc.OracleDriver

MySQL

jdbc:mysql://127.0.0.1:3306/DatabaseName

Имя драйвера: com.mysql.jdbc.Driver

Microsoft Sql Server

jdbc:sqlserver://127.0.0.1:1433;instanceName=DataBaseName

Имя драйвера: com.microsoft.sqlserver.jdbc.SQLServerDriver

Postgree

jdbc:postgresql://127.0.0.1:5432/DatabaseName

Имя драйвера: org.postgresql.Driver

Создаем Spring Boot Hello World приложение в Intellij IDEA

Самый простой способ создать Spring Boot приложение, на мой взгляд — это воспользоваться официальным сайтом Spring.

Открываем Intellij IDEA и создаем новый Maven проект:

Maven проект IDEA

После создания проекта идем на сайт Spring в раздеп Guides:

Spring Guides

Далее в строке поиска пишем MVC и получаем такой результат:

Spring Guides MVC

Заходим по этой ссылке и делаем все, что там написано (далее по тексту).

Конфигурация pom.xml для Spring Boot

Чтобы сконфигурировать Spring Boot проект нам надо прописать build script:

<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0"
         xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
         xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>HelloWorldSpring</groupId>
    <artifactId>HelloWorldSpring</artifactId>
    <version>1.0-SNAPSHOT</version>

    <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>2.0.2.RELEASE</version>
    </parent>

    <dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-thymeleaf</artifactId>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-devtools</artifactId>
            <optional>true</optional>
        </dependency>
    </dependencies>

    <properties>
        <java.version>1.8</java.version>
    </properties>


    <build>
        <plugins>
            <plugin>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-maven-plugin</artifactId>
            </plugin>
        </plugins>
    </build>

</project>

Создаем файлы проекта Spring Boot

Далее по инструкции создаем пакет hello и в нем класс GreetingController:

Controller in hello package

Содержимой класса выглядит следующим образом:

package hello;

import org.springframework.stereotype.Controller;
import org.springframework.ui.Model;
import org.springframework.web.bind.annotation.GetMapping;
import org.springframework.web.bind.annotation.RequestParam;

@Controller
public class GreetingController {

    @GetMapping("/greeting")
    public String greeting(@RequestParam(name="name", required=false, defaultValue="World") String name, Model model) {
        model.addAttribute("name", name);
        return "greeting";
    }

}

Далее в ресурсах создаем папку templates и в ней файл greeting.html, имеющий следующее содержимое:

<!DOCTYPE HTML>
<html xmlns:th="http://www.thymeleaf.org">
<head>
    <title>Getting Started: Serving Web Content</title>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
</head>
<body>
<p th:text="'Hello, ' + ${name} + '!'" />
</body>
</html>

Далее в пакете hello создадим класс Application:

package hello;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;

@SpringBootApplication
public class Application {

    public static void main(String[] args) {
        SpringApplication.run(Application.class, args);
    }

}

Далее создаем папку static в ресурсах и в ней создаем файл index.html:

<!DOCTYPE HTML>
<html>
<head>
    <title>Getting Started: Serving Web Content</title>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
</head>
<body>
<p>Get your greeting <a href="/greeting">here</a></p>
</body>
</html>

Запуск Spring Boot приложения

Чтобы запустить приложение, надо перейти в класс Application и выполнить действия, показанные на скриншоте:

Run Spring Boot Application

Наше приложение доступно по адресу http://127.0.0.1:8080

Создание WAR архива Spring Boot приложения и deploy на Apache Tomcat

Чтобы задеплоить написанное приложение на tomcat необходимо выполнить следующие действия:

Класс Application должен приобрести следующий вид:

package hello;

import org.springframework.boot.SpringApplication;
import org.springframework.boot.autoconfigure.SpringBootApplication;
import org.springframework.boot.builder.SpringApplicationBuilder;
import org.springframework.boot.web.servlet.support.SpringBootServletInitializer;

@SpringBootApplication
public class Application extends SpringBootServletInitializer {

    @Override
    protected SpringApplicationBuilder configure(SpringApplicationBuilder application) {
        return application.sources(Application.class);
    }

    public static void main(String[] args) {
        SpringApplication.run(Application.class, args);
    }

}

В файл pom.xml дописываем <packaging>war</packaging> после тега version в начале файла.

Далее создаем war архив (View/Tool Windows/Maven Projects):

WAR package

В проекте создалась папка target и в ней файл war.

Останавливаем проект и запускаем Apache Tomcat.

Заходим в Application List и деплоим наш файл, предварительно переименовав его, как вам удобно:

Deploy to Apache tomcat

В моем случае приложение доступно по адресу http://127.0.0.1:8080/HelloWorldSpring/ т.к. имя моего файла HelloWorldSpring.

Шифрование данных с помощью алгоритма AES-256 на Java

В данной статье говорится о том, как осуществить шифрование с помощью алгоритма AES-256 на Java.

Как уже говорилось ранее, AES-256 представляет собой алгоритм шифрования с симметричным ключом. Это означает, что для шифрования и дешифрования используется один и тот же криптографический ключ.

Алгоритм используется в военных целях, используется для шифрования передачи сообщений по открытым каналам, для шифрования файлов. Так же с помощью AES-256 злоумышленники шифруют файлы на компьютерах «жертв», используя его в целях вымогательства денег (программы-вымогатели). Расшифровать данные возможно только лишь зная ключ.

Как зашифровать и дешифровать с помощью AES-256 средствами Java

Класс для шифрования и дешифрования потока байт на Java может выглядеть следующим образом:

package Crypto;

import javax.crypto.Cipher;
import javax.crypto.KeyGenerator;
import javax.crypto.SecretKey;
import java.security.NoSuchAlgorithmException;

/**
 * Created by administrator on 16.03.2018.
 */
public class Aes256Class {

    private SecretKey secretKey;

    public Aes256Class() {
        try {
            KeyGenerator keyGenerator = KeyGenerator.getInstance("AES");
            keyGenerator.init(256);

            this.secretKey = keyGenerator.generateKey();

        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        }
    }

    public byte[] makeAes(byte[] rawMessage, int cipherMode){
        try {
            Cipher cipher = Cipher.getInstance("AES");
            cipher.init(cipherMode, this.secretKey);
            byte [] output = cipher.doFinal(rawMessage);
            return output;

        } catch (Exception e){
            e.printStackTrace();
            return null;
        }
    }
}

В конструкторе Aes256Class() инициализируется объект keyGenerator, которому задается размер ключа 256 бит. Далее с помощью функции generateKey() генерируется случайный ключ с заданным размером (256 бит).

В функцию makeAes передается исходный массив байт и режим работы объекта класса Cipher:

Cipher.ENCRYPT_MODE либо Cipher.DECRYPT_MODE.

В классе с функцией main можем вызвать описанные выше методы следующим образом:

package Main;

import Crypto.Aes256Class;

import javax.crypto.Cipher;

/**
 * Created by administrator on 16.03.2018.
 */
public class Main {
    public static void main(String[] args) {
        Aes256Class aes256 = new Aes256Class();

        String mes = "Hello";

        for (int i = 0; i < 3; i++) {
            byte[] shifr = aes256.makeAes(mes.getBytes(), Cipher.ENCRYPT_MODE);
            System.out.println(new String(shifr));
            byte[] src = aes256.makeAes(shifr, Cipher.DECRYPT_MODE);
            System.out.println(new String(src));
        }
    }
}

Получаем следующий результат:

Java AES

Объясняю, зачем я зациклил выполнение функции makeAes.

Благодаря шифрованию и дешифрованию одного и того же текста несколько раз, можно увидеть, что шифр получается один и тот же, что не есть хорошо.

Это уже может дать злоумышленнику какую-то информацию. Представьте себе, что ваша система отправляет в канал сообщение, например, «Опасность». И отправляет его 10 раз подряд.

Если каким-то образом сеть будет прослушиваться, перехваченное сообщение будет иметь 10 раз подряд один и тот же шифр.

Для того, чтобы одно и то же сообщение имело разный шифр, можно использовать соль.

Не смотря на то, что AES-256 не поддерживает концепцию соли, ничего не мешает сгенерировать случайный массив байт из, например, 8 элементов (получим 8 байтовую соль) и добавить к сообщению.

При дешифрации сообщения можно просто выбросить эти самые последние 8 байт.

Функция приобретет следующий вид:

public byte[] makeAes(byte[] rawMessage, int cipherMode){
    try {
        Cipher cipher = Cipher.getInstance("AES");
        cipher.init(cipherMode, this.secretKey);
        byte [] output = cipher.doFinal(rawMessage);
        if(cipherMode == Cipher.DECRYPT_MODE){
            byte[]result = new byte[output.length-8];
            //Выбрасываем последние 8 байт
            System.arraycopy(output, 0, result, 0, output.length-8);
            return result;
        }
        return output;

    } catch (Exception e){
        e.printStackTrace();
        return null;
    }
}

Вызываем функцию makeAes в методе main:

package Main;

import Crypto.Aes256Class;

import javax.crypto.Cipher;
import java.security.SecureRandom;

/**
 * Created by administrator on 16.03.2018.
 */
public class Main {
    public static void main(String[] args)  {
        Aes256Class aes256 = new Aes256Class();

        //Массив для соли
        byte[] salt = new byte[8];
        //Исходное сообщение
        String mes = "Опасность";

        //Выполним операцию 10 раз
        for (int i = 0; i < 10; i++) {
            //Генерация соли
            SecureRandom random = new SecureRandom();
            random.nextBytes(salt);

            //Преобразуем исходный текст в поток байт и добавим полученную соль
            byte[]srcMessage = mes.getBytes();
            byte[]fullsrcMessage = new byte[srcMessage.length+8];
            System.arraycopy(srcMessage, 0, fullsrcMessage, 0, srcMessage.length);
            System.arraycopy(salt, 0, fullsrcMessage, srcMessage.length, salt.length);

            //Шифруем
            byte[] shifr = aes256.makeAes(fullsrcMessage, Cipher.ENCRYPT_MODE);
            System.out.println(new String(shifr));
            //Дешифруем
            byte[] src = aes256.makeAes(shifr, Cipher.DECRYPT_MODE);
            System.out.println(new String(src));
        }
    }
}

В этом примере шифруем и дешифруем 10 раз сообщение «Опасность». Получаем следующий результат:

Java AES with salt

Как видим, одно и то же сообщение, но шифр разный. Однако здесь есть нюанс, если обратите внимание, то увидите, что первая часть сообщения всегда одна и та же. Это и имелось ввиду, когда говорилось, что AES не поддерживает концепцию соли.

Можете попробовать прикреплять соль к началу сообщения, к середине, или использовать несколько солей. Однако Принцип Керкгоффса подразумевает, что злоумышленнику известен алгоритм шифрования и какую-то закономерность он все же найдет.

Нужна очень «хитрая» реализация алгоритма, задача которой максимально запутать злоумышленника.

Когда я писал статью о реализации данного алгоритма на C# я положился на реализацию AES от Microsoft.

Реализация AES-256 на Java с помощью фреймворка Spring Security

В данной статье приведу реализацию AES с помощью Java фреймворка Spring Security:

package Main;

import org.springframework.security.crypto.encrypt.Encryptors;
import org.springframework.security.crypto.encrypt.TextEncryptor;
import org.springframework.security.crypto.keygen.KeyGenerators;

/**
 * Created by administrator on 16.03.2018.
 */
public class Main {

    public static void main(String[] args)  {
        final String password = "Here is the password";
        String textToEncrypt = "Hello";

        for (int i = 0; i < 10; i++) {
            String salt = KeyGenerators.string().generateKey();
            TextEncryptor encryptor = Encryptors.text(password, salt);
            String cipherText = encryptor.encrypt(textToEncrypt);
            String decryptedText = encryptor.decrypt(cipherText);
            System.out.println("Src: " + textToEncrypt);
            System.out.println("Cipher: " + cipherText);
            System.out.println("Decrypted: " + decryptedText);
            System.out.println("__________________");
        }
    }
}

Результат работы кода:

AES Spring Security

Как видите, реализация AES-256 от Spring Security не подводит. Как знать, что это именно AES? В официальной документации есть такое упоминание:

The "standard" encryption method is 256-bit AES (Spring Crypto Module)

P.S. Расшифровать подобные сообщения относительно разумными средствами (взломать шифр), не имея ключа в настоящее время не представляется возможным.

Можете попробовать перебором паролей, если у вас в запасе есть сотни миллиардов лет.

P.P.S. Так же на сайте имеется запись о шифровании данных с помощью AES-256 на C#.

Создание собственного ClassLoader в Java

Описываю создание собственного ClassLoader в Java.

Собственные загрузчики классов нужны для реализации рефлексии в Java.

Мы загружаем файл-класс «на лету» и исполняем его методы.

Как загрузить Java класс на лету

Чтобы загрузить Java класс нам нужен подготовленный файл с байт-кодом, имеющий расширение .class, однако в приведенном ниже примере никаких заготовок я не использую, и создаю класс так же — «на лету», используя Java компилятор (javac) и класс Runtime в коде программы.

import java.io.File;
import java.io.FileNotFoundException;
import java.lang.reflect.Method;
import java.util.Properties;

public class Main {
    public static void main(String[] args) throws Exception {
        
        //Получаем доступ ко всем Properties
        Properties p = System.getProperties();
        //Получаем разделитель, используемый в операционной системе
        String sep = p.getProperty("file.separator");
        //Получаем путь к папке JRE
        String jrePath = p.getProperty("java.home");

        //Выполняем необходимые манипуляции для получения пути к файла javac (в моем случае javac.exe)
        int lastIndex = jrePath.lastIndexOf(sep);
        String javac = jrePath.substring(0, lastIndex) + sep + "bin" + sep + "javac";
        if(p.getProperty("sun.desktop").equals("windows"))
            javac+=".exe";
        else javac+=".sh";

        //Проверяем, существует ли такой файл (javac.exe)
        File jc = new File(javac);
        if(!jc.isFile())
            throw new FileNotFoundException("Компилятор по адресу "+ jc.getAbsolutePath() +" недоступен ");

        System.out.println("Компилируем " + jc.getAbsolutePath() + " " + file.getAbsolutePath());

        //Запускаем компилятор javac, чтобы получить байт код внешнего класса
        Process p1 = Runtime.getRuntime().exec(javac+" "+file.getAbsolutePath());

        //Если javac завершился с ошибкой, выбрасываем Exception (здесь он самописный)
        //т.к. мне необходимо было проверять синтаксис класса, который подключался.
        //Таким образом, если возникала ошибка компиляции, то процесс p1 мог вернуть текст
        //ошибки (поток байт) с помощью функции getErrorStream()
        if(p1.waitFor()!=0)
            try {
                throw new MyClassCompilationException("Ошибка компиляции", p1);
            } catch (MyClassCompilationException e) {
                e.printStackTrace();
                return;
            }

        //Здесь мы уже имеем созданный файл с байт-кодом
        System.out.println("Компиляция завершена");

        //Формируем абсолютный путь к файлу с байт-кодом
        int pointIndex = file.getAbsolutePath().lastIndexOf(".");
        String absulutePatch = file.getAbsolutePath().substring(0, pointIndex);

        //Объявляем MyClassLoader. Класс ClassLoader является абстрактным
        //поэтому необходимо его переопределить (каким образом, будет показано ниже)
        MyClassLoader loader = new MyClassLoader();

        //Объявляем переменную типа Class.
        Class cl = loader.findClass(absulutePatch);
        System.out.println(cl);

        //Получаем метод m1 из загруженного класса
        Method method = cl.getMethod("m1", new Class[] {String.class, int.class});
        System.out.println(method);
        //Выполняем метод m1. Нельзя забывать про метод newInstance(), если метод динамический.
        method.invoke(cl.newInstance(), new Object[]{"Test", 8});

        //Выполняем метод m2. Он статический, поэтому newInstance() в методе invoke писать не надо
        Method method2 = cl.getMethod("m2", new Class[]{String.class});
        method2.invoke(cl, "QWERRTY");
    }
}

Загружаемый класс выглядит таким образом:

public class Hello {
  public void m1(String text, int c) {
    for(int i = 0; i < c; i++) {
      System.out.println(text + " Hi"+i);
    }
  }

  public static void m2(String text) {
    System.out.println(text + " from static method");
  }
}

Класс MyClassLoader будет загружать созданный класс в статический контекст, чтобы мы могли обращаться к его методам.

MyClassLoader имеет следующий вид:

import java.io.*;

public class MyClassLoader extends ClassLoader {

    //Переопределяем метод findClass, которому надо передать путь к файлу с расширением .class
    @Override
    protected Class<?> findClass(String name) throws ClassNotFoundException {
        //Проверяем, существует ли такой файл
        File f = new File(name+".class");
        if(!f.isFile())
            throw new ClassNotFoundException("Нет такого класса " + name);

        InputStream ins = null;

        try{
            //С помощью потока считываем файл в массив байт
            ins = new BufferedInputStream(new FileInputStream(f));
            byte[]b = new byte[(int)f.length()];
            ins.read(b);
            //С помощью функции defineClass загружаем класс
            Class c = defineClass("Hello", b, 0, b.length);
            return c;

        }catch (Exception e){
            e.printStackTrace();
            throw new ClassNotFoundException("Проблемы с байт кодом");
        }
        finally {
            try {
                ins.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }
}

С первом блоке кода, начиная со строки 54 мы начинаем работать с загруженным классом.

Результат работы приведенного выше кода выглядит следующим образом:

ClassLoader

Здесь приведена загрузка простого класса с простыми методами, однако ничего не мешает загрузить туда более емкие классы.

Если будет нужно, опубликую, как взаимодействовать с внешним процессом так, чтобы получать от него сообщение об ошибке в виде потока байт.

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

Работа с анимацией в Android (Java, XML)

В данном посте рассматривается работа с анимацией в Android.

Для начала необходимо в папке Res создать папку anim и выбрать Resource type anim. Затем добавлять файлы Animation Resourse File в эту папку.

Далее рассмотрим примеры анимаций.

Анимация прозрачности

<?xml version="1.0" encoding="utf-8"?>
<alpha
  xmlns:android="http://schemas.android.com/apk/res/android"
  android:fromAlpha="0.0"
  android:toAlpha="1.0"
  android:duration="3000">
</alpha>

Анимация перемещения

<?xml version="1.0" encoding="utf-8"?>
<translate
  xmlns:android="http://schemas.android.com/apk/res/android"
  android:fromXDelta="-150"
  android:toXDelta="0"
  android:fromYDelta="-200"
  android:toYDelta="0"
  android:duration = "3000">
</translate>

Анимация поворота

<?xml version="1.0" encoding="utf-8"?>
<rotate
  xmlns:android="http://schemas.android.com/apk/res/android"
  android:fromDegrees="0"
  android:toDegrees="360"
  android:duration = "3000">
</rotate>

Анимация масштабирования

<?xml version="1.0" encoding="utf-8"?>
<scale
  xmlns:android="http://schemas.android.com/apk/res/android"
  android:fromXScale="0.1"
  android:toXScale="1.0"
  android:fromYScale="0.1"
  android:toYScale="1.0"
  android:pivotX="50%"
  android:pivotY="50%"
  android:duration="3000">

Использование сразу нескольких эффектов анимаций

Объединяем анимации разворота и масштабирования:

<?xml version="1.0" encoding="utf-8"?>
<set xmlns:android="http://schemas.android.com/apk/res/android">
  <rotate
    android:fromDegrees="0"
    android:toDegrees="360"
    android:duration="3000"
    android:pivotY="50%"
    android:pivotX="50%">
  </rotate>
  <scale
    android:fromXScale="0.1"
    android:toXScale="1.0"
    android:fromYScale="0.1"
    android:toYScale="1.0"
    android:pivotX="50%"
    android:pivotY="50%"
    android:duration="3000">
  </scale>
</set>

Запуск анимации через контекстное меню

В приведенном ниже коде описанные анимации запускаются через контекстное меню:

package razilov.ru;

import android.support.v7.app.AppCompatActivity;
import android.os.Bundle;
import android.view.ContextMenu;
import android.view.MenuItem;
import android.view.View;
import android.view.animation.Animation;
import android.view.animation.AnimationUtils;
import android.widget.TextView;

public class MainActivity extends AppCompatActivity {

  private TextView textView;

  private final int MENU_ALPHA_ID = 1;
  private final int MENU_SCALE_ID = 2;
  private final int MENU_TRANSLATE_ID = 3;
  private final int MENU_ROTATE_ID = 4;
  private final int MENU_COMBO_ID = 5;

  @Override
  public void onCreateContextMenu(ContextMenu menu, View v, ContextMenu.ContextMenuInfo menuInfo) {
    switch (v.getId()){
      case R.id.textView:
      menu.add(0, MENU_ALPHA_ID, 0, "Alpha");
      menu.add(0, MENU_SCALE_ID, 0, "Scale");
      menu.add(0, MENU_TRANSLATE_ID, 0, "Translate");
      menu.add(0, MENU_ROTATE_ID, 0, "Rotate");
      menu.add(0, MENU_COMBO_ID, 0, "Combo");
    }
    super.onCreateContextMenu(menu, v, menuInfo);
  }

//Работа с анимацией
  @Override
  public boolean onContextItemSelected(MenuItem item) {
    Animation anim = null;

    switch (item.getItemId()){
      case MENU_ALPHA_ID:
      anim = AnimationUtils.loadAnimation(this, R.anim.myalpha);
      break;
      case MENU_SCALE_ID:
      anim = AnimationUtils.loadAnimation(this, R.anim.myscale);
      break;
      case MENU_TRANSLATE_ID:
      anim = AnimationUtils.loadAnimation(this, R.anim.mytrans);
      break;
      case MENU_ROTATE_ID:
      anim = AnimationUtils.loadAnimation(this, R.anim.myrotate);
      break;
      case MENU_COMBO_ID:
      anim = AnimationUtils.loadAnimation(this, R.anim.mycombo);
      break;
    }

    textView.startAnimation(anim);
    return super.onContextItemSelected(item);
  }

  @Override
  protected void onCreate(Bundle savedInstanceState) {
    super.onCreate(savedInstanceState);
    setContentView(R.layout.activity_main);

    textView = (TextView)findViewById(R.id.textView);
    registerForContextMenu(textView);
  }
}

Код очень простой. Если есть вопросы, задавайте.

Результат приведенного кода привожу по ссылке.