Структуры данных

Небольшая коллекция практик, трюков и подсказок, с помощью которых вы сэкономите своё время при изучении Java и написании кода на этом языке программирования. Перевод статьиTop 25 Java Tricks, Tips, and Best Practices от специалистов Рексофт.

Организация работы

Чистый код

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

• Правило 10-50-500. В одном пакете не может быть более 10 классов. Каждый метод должен быть короче 50 строк кода, а каждый класс короче 500 строк.

• SOLID принципы.

• Использование паттернов проектирования.

Работа с ошибками

Stack Trace (Трассировка стека)

Выявление ошибок это, пожалуй, самая трудоемкая часть процесса разработки на Java. Трассировка стека позволяет вам точно отслеживать, где именно в проекте возникла ошибка или исключение (exception).

import java.io.*;Exception e = ;java.io.StringWriter sw = new java.io.StringWriter();e.printStackTrace(new java.io.PrintWriter(sw));String trace = sw.getBuffer().toString();

NullPointerException

Исключения, возникающие из-заnullзначений (NullPointerException), довольно часто появляются при попытке вызвать метод у несуществующего объекта.

Возьмем для примера следующий код:

int noOfStudents = school.listStudents().count;private int getListOfStudents(File[] files) {if (files == null)  throw new NullPointerException("File list cannot be null");}

Примечание переводчика: а вот пример от меня как переводчика материала:

String anyString = null;if (anyString.equals("some string")) { // здесь будет null pointer exception, т.к. anyString == null// ...}

Дата и Время

System.currentTimeMillis или System.nanoTime?

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

МетодSystem.currentTimeMillis()возвращает текущее количество миллисекунд с начала эры Unix в формате Long. Его точность составляет от 1 до 15 тысячных долей секунды в зависимости от системы.

long startTime = System.currentTimeMillis();long estimatedTime = System.currentTimeMillis() - startTime;

МетодSystem.nanoTime()имеет точность до одной миллионной секунды (наносекунды) и возвращает текущее значение наиболее точного доступного системного таймера.

long startTime = System.nanoTime();long estimatedTime = System.nanoTime() - startTime;

Таким образом, методSystem.currentTimeMillis()лучше применять для отображения и синхронизации абсолютного времени, аSystem.nanoTime()для измерения относительных интервалов времени.

Валидация Даты из строки

Если необходимо достать объектDateиз обычной строки в Java, можете использовать небольшой утилитный класс, который приведен ниже. Он позаботится обо всех сложностях валидации и преобразовании строки в объектDate.

package net.viralpatel.java;import java.text.ParseException;import java.text.SimpleDateFormat;import java.util.ArrayList;import java.util.Date;import java.util.List;public class DateUtil {// List of all date formats that we want to parse.// Add your own format here.private static List; dateFormats = new ArrayList() {{add(new SimpleDateFormat("M/dd/yyyy"));add(new SimpleDateFormat("dd.M.yyyy"));add(new SimpleDateFormat("M/dd/yyyy hh:mm:ss a"));add(new SimpleDateFormat("dd.M.yyyy hh:mm:ss a"));add(new SimpleDateFormat("dd.MMM.yyyy"));add(new SimpleDateFormat("dd-MMM-yyyy"));}};/** * Convert String with various formats into java.util.Date *  * @param input *            Date as a string * @return java.util.Date object if input string is parsed  * successfully else returns null */public static Date convertToDate(String input) {Date date = null;if(null == input) {return null;}for (SimpleDateFormat format : dateFormats) {try {format.setLenient(false);date = format.parse(input);} catch (ParseException e) {//Shhh.. try other formats}if (date != null) {break;}}return date;}}

Пример его использования:

package net.viralpatel.java;public class TestDateUtil {public static void main(String[] args) {System.out.println("10/14/2012" + " = " + DateUtil.convertToDate("10/14/2012"));System.out.println("10-Jan-2012" + " = " + DateUtil.convertToDate("10-Jan-2012"));System.out.println("01.03.2002" + " = " + DateUtil.convertToDate("01.03.2002"));System.out.println("12/03/2010" + " = " + DateUtil.convertToDate("12/03/2010"));System.out.println("19.Feb.2011" + " = " + DateUtil.convertToDate("19.Feb.2011" ));System.out.println("4/20/2012" + " = " + DateUtil.convertToDate("4/20/2012"));System.out.println("some string" + " = " + DateUtil.convertToDate("some string"));System.out.println("123456" + " = " + DateUtil.convertToDate("123456"));System.out.println("null" + " = " + DateUtil.convertToDate(null));}}

Результат:

10/14/2012 = Sun Oct 14 00:00:00 CEST 201210-Jan-2012 = Tue Jan 10 00:00:00 CET 201201.03.2002 = Fri Mar 01 00:00:00 CET 200212/03/2010 = Fri Dec 03 00:00:00 CET 201019.Feb.2011 = Sat Feb 19 00:00:00 CET 20114/20/2012 = Fri Apr 20 00:00:00 CEST 2012some string = null123456 = nullnull = null

Строки

Оптимизация строки

Для конкатенации (сложения) строк в Java используется оператор +, для примера, в циклеforновый объект может создаваться для каждой новой строки, что приводит к потере памяти и увеличению времени работы программы.

Необходимо избегать создания Java строк через конструктор, пример:

// медленное создание строкиString bad = new String ("Yet another string object");// быстрое создание строкиString good = "Yet another string object"

Одинарные и двойные кавычки

Что ты ожидаешь в результате выполнения этого кода?

public class Haha {  public static void main(String args[]) {    System.out.print("H" + "a");    System.out.print('H' + 'a');  }}

Казалось бы, строка должна возвращать HaHa, но на самом деле это будет Ha169.

Двойные кавычки обрабатывают символы как строки, но одинарные кавычки ведут себя иначе. Они преобразуют символьные операнды ('H'и'a') в целые значения посредством расширения примитивных типов получается 169.

Математика

Float или Double?

Программисты часто не могут выбрать необходимую точность для чисел с плавающей запятой. Float требует всего 4 байта, но имеет только 7 значащих цифр, а Double в два раза точнее (15 цифр), но в два раза прожорливее.

Фактически, большинство процессоров могут одинаково эффективно работать как с Float, так и с Double, поэтому воспользуйтесь рекомендацией Бьорна Страуструпа (автор языка С++):

Выбор правильной точности для решения реальных задач требует хорошего понимания природы машинных вычислений. Если у вас его нет, либо посоветуйтесь с кем-нибудь, либо изучите проблему самостоятельно, либо используйте Double и надейтесь на лучшее.

Проверка на нечетность

Можно ли использовать этот код для точного определения нечетного числа?

public boolean oddOrNot(int num) {  return num % 2 == 1;}

Надеюсь, вы заметили хитрость. Если мы решим таким образом проверить отрицательное нечетное число (например, -5), остаток от деления не будет равен единице, поэтому воспользуйтесь более точным методом:

public boolean oddOrNot(int num) {  return (num & 1) != 0;}

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

Возведение в степень

Возвести число в степень можно двумя способами:

1. простое умножение;

2. используя методMath.pow()(двойное основание, двойной показатель степени).

Использование библиотечной функции рекомендуется только в случае крайней необходимости, например, в случае дробной или отрицательной степени.

double result = Math.pow(625, 0.5); // 25.0

Простое умножение в Java работает в 300-600 раз эффективнее, кроме того, его можно дополнительно оптимизировать:

double square = double a * double a;  double cube = double a * double a * double a; // не оптимизированоdouble cube = double a * double square;  // оптимизировано double quad = double a * double a * double a * double a; // не оптимизированоdouble quad = double square * double square; // оптимизировано

JIT оптимизация

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

В качестве примера рассмотрим две простые операции:

// 1n += 2 * i * i; // 2n += 2 * (i * i);

Давайте измерим время выполнения каждого из них:

// 1long startTime1 = System.nanoTime(); int n1 = 0; for (int i = 0; i < 1000000000; i++) {   n1 += 2 * i * i; } double resultTime1 = (double)(System.nanoTime() - startTime1) / 1000000000;System.out.println(resultTime1 + " s");  // 2long startTime2 = System.nanoTime(); int n2 = 0; for (int i = 0; i < 1000000000; i++) {   n2 += 2 * (i * i); } double resultTime2 = (double)(System.nanoTime() - startTime2) / 1000000000;System.out.println(resultTime2 + " s");

Запустив этот код несколько раз, мы получим примерно следующее:

|`2*(i*i)`| `2*i*i`||---------|--------||0.5183738 | 0.6246434||0.5298337 | 0.6049722||0.5308647 | 0.6603363||0.5133458 | 0.6243328||0.5003011 | 0.6541802||0.5366181 | 0.6312638||0.515149  | 0.6241105||0.5237389 | 0.627815 ||0.5249942 | 0.6114252||0.5641624 | 0.6781033||0.538412  | 0.6393969||0.5466744 | 0.6608845||0.531159  | 0.6201077||0.5048032 | 0.6511559||0.5232789 | 0.6544526|

Схема очевидна: группировка переменных в круглые скобки ускоряет работу программы. Это связано с генерацией более эффективного байт-кода при умножении одинаковых значений.

Вы можете узнать больше об этом экспериментездесь. Или можете провести свой собственный тест, используя онлайн-компилятор Java.

Структуры данных

Комбинирование хеш-таблиц

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

import java.util.*;Map m1 = ;Map m2 = ;m2.putAll(m1); // добавить к m2 все элементы из m1

Array или ArrayList?

Выбор междуArrayиArrayListзависит от специфики задачи Java, которую вы хотите решить. Запомните следующие особенности этих типов:

• Массив имеет фиксированный размер, и память для него выделяется во время объявления, а размерArrayListможет динамически меняться.

• Массивы Java работают намного быстрее, а вArrayListнамного проще добавлять и удалять элементы.

• При работе сArrayскорее всего возникнет ошибкаArrayIndexOutOfBoundsException.

• ArrayList может быть только одномерным, когда массивы Java могут быть многомерными.

import java.util.*; public class ArrayVsArrayList {  public static void main(String[] args) {    // создаем массив    int[] myArray = new int[6];     // ссылаемся на несуществующий индекс    myArray[7]= 10; // ArrayIndexOutOfBoundsException     // создаем ArrayList    List myArrayList = new ArrayList<>();     // простое добавление и удаление элементов    myArrayList.add(1);    myArrayList.add(2);    myArrayList.add(3);    myArrayList.add(4);    myArrayList.add(5);    myArrayList.remove(0);     // перебор элементов ArrayList     for(int i = 0; i < myArrayList.size(); i++) {      System.out.println("Element: " + myArrayList.get(i));    }     //  многомерный массив    int[][][] multiArray = new int[3][3][3];   }}

JSON

Сериализация и Десериализация

JSON невероятно удобный и полезный синтаксис для хранения и обмена данными. Java полностью поддерживает это.

Примечание переводчика: для использования JSON из примера необходимо подключить библиотекуJSON Simple.

Вы можете сериализовать данные следующим образом:

import org.json.simple.JSONObject;import org.json.simple.JSONArray; public class JsonEncodeDemo {  public static void main(String[] args) {    JSONObject obj = new JSONObject();    obj.put("Novel Name", "Godaan");    obj.put("Author", "Munshi Premchand");     JSONArray novelDetails = new JSONArray();    novelDetails.add("Language: Hindi");    novelDetails.add("Year of Publication: 1936");    novelDetails.add("Publisher: Lokmanya Press");            obj.put("Novel Details", novelDetails);      System.out.print(obj);    }}

Получается следующая строка JSON:

{"Novel Name":"Godaan","Novel Details":["Language: Hindi","Year of Publication: 1936","Publisher: Lokmanya Press"],"Author":"Munshi Premchand"}

Десериализация в Java выглядит так:

import java.io.FileNotFoundException;import java.io.FileReader;import java.io.IOException;import java.util.Iterator; import org.json.simple.JSONArray;import org.json.simple.JSONObject;import org.json.simple.parser.JSONParser;import org.json.simple.parser.ParseException; public class JsonParseTest {  private static final String filePath = "//home//user//Documents//jsonDemoFile.json";      public static void main(String[] args) {    try {      // читаем json файл      FileReader reader = new FileReader(filePath);      JSONParser jsonParser = new JSONParser();      JSONObject jsonObject = (JSONObject)jsonParser.parse(reader);                  // берем данные из json объекта      Long id =  (Long) jsonObject.get("id");      System.out.println("The id is: " + id);                  String type = (String) jsonObject.get("type");      System.out.println("The type is: " + type);       String name = (String) jsonObject.get("name");      System.out.println("The name is: " + name);       Double ppu =  (Double) jsonObject.get("ppu");      System.out.println("The PPU is: " + ppu);       // извлекаем массив              System.out.println("Batters:");      JSONArray batterArray= (JSONArray) jsonObject.get("batters");      Iterator i = batterArray.iterator();            // проходимся по всем элементам массива      while (i.hasNext()) {        JSONObject innerObj = (JSONObject) i.next();        System.out.println("ID "+ innerObj.get("id") +             " type " + innerObj.get("type"));      }       System.out.println("Topping:");      JSONArray toppingArray= (JSONArray) jsonObject.get("topping");      Iterator j = toppingArray.iterator();      while (j.hasNext()) {        JSONObject innerObj = (JSONObject) j.next();        System.out.println("ID "+ innerObj.get("id") +             " type " + innerObj.get("type"));      }    } catch (FileNotFoundException|IOException|ParseException|NullPointerException ex) {      ex.printStackTrace();    }  }}

Используемый в примере файл JSON (jsonDemoFile.json):

{  "id": 0001,  "type": "donut",  "name": "Cake",  "ppu": 0.55,  "batters":    [      { "id": 1001, "type": "Regular" },      { "id": 1002, "type": "Chocolate" },      { "id": 1003, "type": "Blueberry" },      { "id": 1004, "type": "Devil's Food" }    ],  "topping":    [      { "id": 5001, "type": "None" },      { "id": 5002, "type": "Glazed" },      { "id": 5005, "type": "Sugar" },      { "id": 5007, "type": "Powdered Sugar" },      { "id": 5006, "type": "Chocolate with Sprinkles" },      { "id": 5003, "type": "Chocolate" },      { "id": 5004, "type": "Maple" }    ]}

Примечание переводчика: в Java проектах очень часто для работы с JSON используют библиотеки Gson от Google или Jackson. Обе библиотеки очень популярны и хорошо поддерживаются. Попробуйте и их.

Ввод и Вывод

FileOutputStream или FileWriter?

Запись файлов в Java осуществляется двумя способами:FileOutputStreamиFileWriter. Какой метод выбрать, зависит от конкретной задачи.

FileOutputStreamпредназначен для записи необработанных байтовых потоков. Это делает его идеальным решением, например, для работы с изображениями.

File foutput = new File(file_location_string);FileOutputStream fos = new FileOutputStream(foutput);BufferedWriter output = new BufferedWriter(new OutputStreamWriter(fos));output.write("Buffered Content");

УFileWriterдругое призвание: работа с потоками символов. Поэтому, если вы пишете текстовые файлы, выберите этот метод.

FileWriter fstream = new FileWriter(file_location_string);BufferedWriter output = new BufferedWriter(fstream);output.write("Buffered Content");

Производительность и лучшие практики

Пустая коллекция вместо Null

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

import java.util.*public List getLocations() {  List result = someService.getLocationsFromDB();  return result == null ? Collections.emptyList() : result;}

Создание объектов только когда необходимо

Создание объектов одна из самых затратных операций в Java. Лучше всего создавать их только тогда, когда они действительно нужны.

import java.util.ArrayList;import java.util.List; public class Employees {  private List Employees;   public List getEmployees() {    // initialization only if necessary    if(null == Employees) {      Employees = new ArrayList();    }        return Employees;  }}

Deadlocks (Дедлоки)

Взаимная блокировка (Deadlock) потоков может происходить по многим причинам, и полностью защититься от них в Java 8 очень сложно. Чаще всего, это происходит, когда один синхронизируемый объект ожидает ресурсов, которые заблокированы другим синхронизированным объектом.

Вот пример тупика этого потока:

public class DeadlockDemo {  public static Object addLock = new Object();  public static Object subLock = new Object();   public static void main(String args[]) {    MyAdditionThread add = new MyAdditionThread();    MySubtractionThread sub = new MySubtractionThread();    add.start();    sub.start();  }   private static class MyAdditionThread extends Thread {    public void run() {      synchronized (addLock) {        int a = 10, b = 3;        int c = a + b;        System.out.println("Addition Thread: " + c);        System.out.println("Holding First Lock...");        try { Thread.sleep(10); }        catch (InterruptedException e) {}        System.out.println("Addition Thread: Waiting for AddLock...");        synchronized (subLock) {           System.out.println("Threads: Holding Add and Sub Locks...");        }      }    }  }   private static class MySubtractionThread extends Thread {    public void run() {      synchronized (subLock) {        int a = 10, b = 3;        int c = a - b;        System.out.println("Subtraction Thread: " + c);        System.out.println("Holding Second Lock...");        try { Thread.sleep(10); }        catch (InterruptedException e) {}        System.out.println("Subtraction  Thread: Waiting for SubLock...");        synchronized (addLock) {           System.out.println("Threads: Holding Add and Sub Locks...");        }      }    }  }}

Результат этой программы:

=====Addition Thread: 13Subtraction Thread: 7Holding First Lock...Holding Second Lock...Addition Thread: Waiting for AddLock...Subtraction  Thread: Waiting for SubLock...

Взаимоблокировок можно избежать, изменив порядок вызова потоков:

private static class MySubtractionThread extends Thread {  public void run() {    synchronized (addLock) {      int a = 10, b = 3;      int c = a - b;      System.out.println("Subtraction Thread: " + c);      System.out.println("Holding Second Lock...");      try { Thread.sleep(10); }      catch (InterruptedException e) {}      System.out.println("Subtraction  Thread: Waiting for SubLock...");      synchronized (subLock) {        System.out.println("Threads: Holding Add and Sub Locks...");      }    }  }}

Вывод:

=====Addition Thread: 13Holding First Lock...Addition Thread: Waiting for AddLock...Threads: Holding Add and Sub Locks...Subtraction Thread: 7Holding Second Lock...Subtraction  Thread: Waiting for SubLock...Threads: Holding Add and Sub Locks...

Резервирование памяти

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

export JAVA_OPTS="$JAVA_OPTS -Xms5000m -Xmx6000m -XX:PermSize=1024m -XX:MaxPermSize=2048m"

• Xms минимальный пул выделения памяти;

• Xmx максимальный пул выделения памяти;

• XX: PermSize начальный размер, который будет выделен при запуске JVM;

• XX: MaxPermSize максимальный размер, который можно выделить при запуске JVM.

Примечание переводчика: PermSize и MaxPermSize, начиная с Java 8 уже больше не используются.

Решение распространенных проблем

Содержимое директории

Java позволяет вам получать имена всех подкаталогов и файлов в папке в виде массива, который затем можно последовательно прочитать:

import java.io.*; public class ListContents {  public static void main(String[] args) {    File file = new File("//home//user//Documents/");    String[] files = file.list();     System.out.println("Listing contents of " + file.getPath());    for(int i=0 ; i < files.length ; i++) {      System.out.println(files[i]);    }  }}

Выполнение консольных команд

Java позволяет выполнять консольные команды прямо из кода, используя классRuntime. Очень важно не забывать об обработке исключений.

Например, давайте попробуем открыть файл PDF через терминал Java (на Linuxe):

public class ShellCommandExec {  public static void main(String[] args) {    String gnomeOpenCommand = "gnome-open //home//user//Documents//MyDoc.pdf";     try {      Runtime rt = Runtime.getRuntime();      Process processObj = rt.exec(gnomeOpenCommand);       InputStream stdin = processObj.getErrorStream();      InputStreamReader isr = new InputStreamReader(stdin);      BufferedReader br = new BufferedReader(isr);       String myoutput = "";       while ((myoutput=br.readLine()) != null) {        myoutput = myoutput+"\n";      }      System.out.println(myoutput);    } catch (Exception e) {      e.printStackTrace();    }  }

Воспроизведение звуков

Звук важный компонент многих десктопных приложений и игр. Язык программирования Java предоставляет средства для работы с ним.

import java.io.*;import java.net.URL;import javax.sound.sampled.*;import javax.swing.*; public class PlaySoundDemo extends JFrame {    // constructor   public playSoundDemo() {      this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);      this.setTitle("Play Sound Demo");      this.setSize(300, 200);      this.setVisible(true);       try {         URL url = this.getClass().getResource("MyAudio.wav");         AudioInputStream audioIn = AudioSystem.getAudioInputStream(url);         Clip clip = AudioSystem.getClip();         clip.open(audioIn);         clip.start();      } catch (UnsupportedAudioFileException|IOException|LineUnavailableException e) {         e.printStackTrace();      }   }    public static void main(String[] args) {      new PlaySoundDemo();   }}

Отправка email

Отправить электронную почту на Java очень просто. Вам просто нужно установитьJava Mailи указать путь к нему в пути к классам проекта.

import java.util.*;import javax.mail.*;import javax.mail.internet.*; public class SendEmail {  public static void main(String [] args) {        String to = "recipient@gmail.com";    String from = "sender@gmail.com";    String host = "localhost";     Properties properties = System.getProperties();    properties.setProperty("mail.smtp.host", host);    Session session = Session.getDefaultInstance(properties);     try{      MimeMessage message = new MimeMessage(session);      message.setFrom(new InternetAddress(from));       message.addRecipient(Message.RecipientType.TO,new InternetAddress(to));       message.setSubject("My Email Subject");      message.setText("My Message Body");      Transport.send(message);      System.out.println("Sent successfully!");    } catch (MessagingException ex) {      ex.printStackTrace();    }  }}

Получение координат курсора

Чтобы фиксировать события мыши, вам необходимо реализовать интерфейсMouseMotionListener. Когда курсор попадает в определенную область, срабатывает обработчик событияmouseMoved, из которого вы можете получить точные координаты (используя Swing для UI)

import java.awt.event.*;import javax.swing.*; public class MouseCaptureDemo extends JFrame implements MouseMotionListener {  public JLabel mouseHoverStatus;   public static void main(String[] args) {    new MouseCaptureDemo();  }   MouseCaptureDemo() {    setSize(500, 500);    setTitle("Frame displaying Coordinates of Mouse Motion");     mouseHoverStatus = new JLabel("No Mouse Hover Detected.", JLabel.CENTER);    add(mouseHoverStatus);    addMouseMotionListener(this);    setVisible(true);  }   public void mouseMoved(MouseEvent e) {    mouseHoverStatus.setText("Mouse Cursor Coordinates => X:"+e.getX()+" | Y:"+e.getY());  }   public void mouseDragged(MouseEvent e) {  }}

Базовые алгоритмы сортировки

Пирамидальная сортировка (или сортировка кучей, Heap Sort)

Куча (heap) это не что иное, как двоичное дерево с некоторыми дополнительными правилами, которым оно должно следовать: во-первых, оно всегда должно иметь структуру кучи, где все уровни двоичного дерева заполняются слева направо, и, во-вторых, оно должно быть упорядочено в виде max-кучи или min-кучи. В качестве примера я буду использовать min-кучу.

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

Ниже приведен псевдокод пирамидальной сортировки:

HeapSort(A[1n]):1 - H = buildHeap(A[1n])2 - for i = 1 to n do:3 -   A[i] = extract-min(H)

В самом начале мы имеем несортированный массив. Первый шаг взять этот массив и превратить его в кучу; в нашем случае мы хотим превратить его в min-кучу. Итак, нам нужно преобразовать данные несортированного массива и построить из них min-кучу. Обычно это инкапсулируется одной функцией, которую можно назвать, например, buildHeap.

Ниже приведен псевдокод buildHeap:

buildHeap():1 - Изначально H пустая2 - for i = 1 to n do:3 -   Add(H, A[i])

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

Теперь самый маленький элемент в куче находится в последнем узле, что нам и нужно. Мы знаем, что он находится в отсортирован относительно остальных элементов, поэтому его можно полностью удалить из кучи (функция extract-min). Но нам нужно сделать еще кое-что: убедиться, что новый элемент корневого узла находится на своем месте! Маловероятно, что элемент, который мы сделали корневым узлом, находится на своем месте, поэтому мы переместим элемент корневого узла вниз в его корректное положение, используя функцию, которая обычно называется heapify (приведение к виду кучи).

Ниже приведен псевдокод extract-min и heapify:

extract-min(H):1 - min = H[1]2 - H[1] = H[H.size()]3 - уменьшаем H.size() на 14 - heapify(H, 1)5 - return minheapify():1 - n = H.size()2 - while (LeftChild(i) <= n and H[i] > H[LeftChild(i)]) or (RightChild(i) <= n and H[i] > H[RightChild(i)]) do:3 -   if (H[LeftChild(i)] < H[RightChild(i)]) then:4 -     j = LeftChild(i)5 -   else:6 -     j = RightChild(i)7 -   меняем местами H[i] и H[j]8 -   i = j

Вот и все! Алгоритм продолжает повторять эти шаги до тех пор, пока куча не сократится до одного единственного узла. На момент, когда это произойдет, мы будем уверенны, что все элементы в несортированном массиве находятся в своих отсортированных позициях и что последний оставшийся узел в конечном итоге станет первым элементом в отсортированном массиве. Общее время работы этого алгоритма составляет O(n log n).

Сортировка слиянием (Merge Sort)

Алгоритм сортировки слиянием это алгоритм сортировки, который сортирует коллекцию, разбивая ее на половины. Затем он сортирует эти две половины и объединяет их вместе, чтобы сформировать одну полностью отсортированную коллекцию. В большинстве реализаций сортировки слиянием все это делается посредством рекурсии.

Сортировка слиянием это алгоритм разделяй и властвуй, который можно свести к 3 шагам:

• Разделите (разбейте) задачу на минимально возможные подзадачи одного типа.

• В первую очередь победите (решите) самые мелкие подзадачи. После того, как вы нашли рабочее решение, используйте ту же самую технику для решения более крупных подзадач другими словами, решайте подзадачи рекурсивно.

• Объединяйте результаты и соединяйте более мелкие подзадачи, пока вы, наконец, не примените то же решение к более крупной и сложной задаче, с которой вы начинали!

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

Функция mergeSort в свою очередь состоит из двух функций:

• функции слияния, которая фактически объединяет два списка вместе и сортирует их в правильном порядке.

• функции mergeSort, которая будет продолжать разделять входной массив снова и снова (рекурсивно), а затем будет вызывать функцию слияния снова и снова (также рекурсивно).

Ниже приведен псевдокод сортировки слиянием:

Merge(A, B):1 - i = 1; j = 1; k = 1;2 - a_(m+1) = ; b_{n+1} = 3 - while (k <= m+n) do:4 -   if (a_i < b_j) then5 -     c_k = a_i; i++;6 -   else7 -     c_k = b_j; j++;8 -   k++;9 - return C = {c_1, c_2, , c_(m+n)}MergeSort(X, n)1 - if (n == 1) return X2 - middle = n/2 (round down)3 - A = {x_1, x_2, , x_middle}4 - B = {x_(middle+1), x_{middle+2), , x_n}5 - As = MergeSort(A, middle)6 - Bs = MergeSort(B, n - middle)7 - return Merge(As, Bs)

Именно потому, что сортировка слиянием реализована рекурсивно, это делает ее быстрее, чем другие алгоритмы, которые мы рассмотрели до сих пор. Сортировка слиянием имеет время выполнения O(n log n).

Выпуклая оболочка (или выпуклый контур, Convex Hull)

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

Подход 1 Упаковка подарков (Gift Wrapping) O(n)

Идея проста, мы начинаем с самой левой точки (или точки с минимальным значением координаты x) и продолжаем оборачивать точки против часовой стрелки. Если точка p является текущей точкой, следующая точка выбирается как точка, которая перекрывает все остальные точки по ориентации против часовой стрелки. Ниже приводится псевдокод:

1 - ConvexHull = пустой список2 - Ищем точку с наименьшим x и присваиваем ее u (:= u_original)3 - Пусть L будет вертикальной линией, проходящей через u3 - Do:4 -   Пусть v будет точкой с наименьшим углом между L и u * v5 -   Добавляем v в ConvexHull6 -   Пусть L = uv линии7 -   u := v8 - Until v = u_original9 - Выводим ConvexHull

Подход 2 Алгоритм Грэхема (Graham Scan) O(n log n)

Этот алгоритм можно разделить на 2 этапа:

• Этап 1 (сортировка точек): сначала мы находим самую нижнюю точку. Идея состоит в том, чтобы предварительно обработать точки, сортируя их по самой нижней точке. После сортировки точек они образуют простой замкнутый путь. Какими должны быть критерии сортировки? Вычисление фактических углов было бы неэффективным, поскольку тригонометрические функции не являются простыми в вычислении. Идея состоит в том, чтобы использовать ориентацию для сравнения углов без их фактического вычисления.

• Этап 2 (включении или отбрасывание точек): после того, как у нас есть замкнутый путь, следующим шагом будет прохождение по пути и удаление из него вогнутых точек. Первые две точки в отсортированном массиве всегда являются частью выпуклой оболочки. Для оставшихся точек мы смотрим на последние три точки и находим угол, образованный ими. Пусть это три точки: prev(p), curr(c) и next(n). Если ориентация этих точек (рассматривая их в том же порядке) не против часовой стрелки, мы отбрасываем c, в противном случае мы оставляем ее.

1 - ConvexHull = пустой список2 - Пусть u - точка с наименьшим значением x (если таких точек несколько, выбираем ту, у которой наименьший y)3 - Сортируем оставшиеся точки по угловой фазе в порядке против часовой стрелки вокруг u4 - Добавляем u и первую точку в ConvexHull5 - For i = 2 to n - 1:6 -   While угол между предпоследней, последней и точкой i > 180 градусов:7 -     Удаляем точку из ConvexHull8 -   Добавляем i в ConvexHull9 - Return ConvexHull

Если вам интересно следить за моей работой в области компьютерных наук и машинного обучения, вы можете посетить мои Medium и GitHub, а также другие проекты на https://jameskle.com/. Вы также можете написать мне мне в Твиттере, но электронной почте или найти меня в LinkedIn. Или подписывайтесь на мою рассылку, чтобы получать мои последние статьи прямо на ваш почтовый ящик!

Перевод статьи подготовлен в преддверии старта курса Алгоритмы и структуры данных.

Приглашаем также посетить бесплатный демо-урок на тему Пирамидальная сортировка. На этом бесплатном демо-занятии мы: сначала реализуем алгоритм сортировки выбором, потом превратим массив в пирамиду (кучу) и ускорим время поиск максимального элемента в неотсортированной части массива с линейного до логарифмического.В итоге у нас получится алгоритм Пирамидальной сортировки. Мы наглядно продемонстрируем работу алгоритма на визуальных примерах с конкретными числами.

Представьте человека, который изучает алгоритмы. Чтобы понять как они работают, приходится изучать их код и представлять, как компьютер будет его выполнять. Это странно почему мы должны учиться думать как компьютер, вместо того, чтобы заставить его помогать нам учиться? Какая-то сильная технозависимость.

На мой взгляд, потеть должна машина, а человек учиться, не выворачивая мозги наизнанку. Поэтому я подумал, а почему бы не визуализировать работу алгоритмов? Визуализации помогли бы не закапываться в код, а наглядно показали бы как работают алгоритмы и позволили бы понять их. Что у меня получилось читайте в этой статье.

В результате родился проект Объясняем код. Посмотреть, что это такое можно на code-explained.com. Код проекта выложен на Гитхаб.

Чем я вдохновлялся

Брет Виктор говорит, что творцам нужна мгновенная обратная связь с тем, что они делают. Когда вы создаете что-то или вносите изменения в свое творение, то должны сразу же видеть результат. Иначе, часть идей просто никогда не придут к вам в голову.

Например, если вы редактируете программный код, то результат должен отображаться в реальном времени, без повторной компиляции. Иначе, вы не увидите промежуточные состояния, и у вас не родятся связанные с ними идеи. Я не буду подробно пересказывать эту мысль, тем более, что на Хабре уже подробно о ней рассказали. Почитайте, если еще не успели.

Идея Брета Виктора о мгновенной обратной связи сильно меня вдохновила. Я подумал, что она могла бы изменить подход к изучению программирования, в частности алгоритмов и структур данных. Потому что сегодня этот процесс ужасно технозависим.

Как сегодня изучают алгоритмы

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

В видео на Youtube происходит нечто подобное ведущий берет код алгоритма и отрисовывает этапы его работы

На ИТ-ресурсах создают анимации.

А кто-то даже пытается объяснить работу алгоритма через танец.

Почему эти подходы казались мне неэффективными

У всех перечисленных подходов есть огромный минус. Они пытаются заставить нас думать как компьютер, а не наоборот подчинить железо нашим потребностям. Чтобы понять, как работает код алгоритма, нужно представлять, как машина будет его выполнять. Я решил, что хочу уйти от этого подхода.

Как я перешел от технозависимости к человечности

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

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

Выглядит это как-то так. Можно вводить свои данные. А затем с помощью плеера запускать и останавливать исполнение кода, перематывать его вперед и назад. При этом визуализация в реальном времени показывает, что делает алгоритм.

Как это технически реализовано

Для кода на Python написан аналогичный код на JS, который после выполнения каждой строчки сохраняет состояние. Такой трюк помогает исполнять код на фронтенде без тяжелого интерпретатора. Чтобы убедиться, что код на JS делает то же самое, что и на Python, есть автотестер он прогоняет код на обоих языках и сравнивает результаты.

Чтобы сэкономить на копировании данных, я применил Immutable.js. Immutable.js это библиотека неизменяемых коллекций. Модификации таких коллекций всегда возвращают новую коллекцию, которую легко сохранить. Так я избегаю глубокого копирования. Не буду вдаваться в подробности, на Хабре про immutable.js уже писали. Для примера кусочек кода с итерированием по хеш-таблице:

while (true) { // Итерируемся по списку    this.addBP('check-not-found'); // Метод сохраняем состояние    if (this.newList.get(this.newListIdx) === null) {        // this.newList -- это немутабельный список        break;    }    this.addBP('check-found'); // Выполнена очередная строчка, сохраняем состояние    if (EQ(this.newList.get(this.newListIdx), this.number)) {        this.addBP('found-key');        return true;    }    this.fmtCollisionCount += 1; // Для динамических комментариев иногда нужно сохранять статистикуу    this.newListIdx = (this.newListIdx + 1) % this.newList.size; // Переходим к следующему индекксу    this.addBP('next-idx');}

В любой момент пользователь может отмотать время слайдером, и мы должны быть готовы анимировать переход. Поэтому анимации сделаны декларативно на React и CSS. На React описываются нужное состояние, а CSS transitions автоматически высчитывают и анимируют переход. Это позволяет избежать совсем сложного императивного кода с запутанным состоянием и ручными вычислениями. Получается тоже не просто, и в итоге анимациями заведует огромный класс на 1000 строк. Но я уверен, что императивно реализовать то же самое у меня вообще не получилось бы.

Много строк возникает из-за особенностей браузерных API и производительности в разных браузерах. Например, большой проблемой оказалось сделать так, чтобы браузеры не склеивали последовательные изменения друг с другом. Если добавить div с определённой начальной позицией, и потом сразу же поменять координаты на конечные, то браузер склеит эти два изменения в одно. Div сразу окажется в конечной позиции без анимации. Чтобы такое не происходило, приходится вставлять задержку в два фрейма анимации с помощью window.requestAnimationFrame().

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

Код проекта на гитхабе

Что дальше?

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

Привет, Хабр. В прошлой статье я рассказал о начальном анализе предметной области и базовом проектировании нашей новой ECM-системы. Теперь я расскажу о первой практической задаче, которую мы решили. А именно - о выборе способа организации структуры хранилища бизнес-атрибутов объектов.

Напомню, что в результате анализа мы пришли к следующей структуре объекта:

Системные и интеграционные поля содержат техническую информацию и редко подвержены модификациям. А вот бизнес-поля - искомые атрибуты объектов - могут и будут различаться для разных типов документов, которых у нас на входе предполагается около 1000. Проанализировав возможность повторного использования полей, мы пришли к выводу, что у разных типов документов может быть не более 15% общих свойств. И при этом всё равно придется скрепя сердце согласиться на неполное соответствие названия и содержания.

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

Какие есть варианты?

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

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

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

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

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

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

Также стоит упомянуть про еще один способ организации данных, с которым я сталкивался. Он используется не в пример реже и больше напоминает "велосипед" - назовем его вертикальный. В хранилище создается таблица, которая содержит, условно, название поля, данные в нем, тип данных и связь с объектом. Возможно создание нескольких таких таблиц для разных типов данных или несколько колонок в одной таблице. Далее, при извлечении такие данные трансформируются из списка в плоский набор полей. Понимаете, почему я упомянул про велосипед?

А что у нас?

Второй вариант - это использование специализированных документоориентированных (или документных, как больше нравится) баз данных, реализующих NoSQL-подход к хранению и обработкенеструктурированной или слабоструктурированной информации. Наиболее часто данные хранятся в виде JSON объектов, но с предоставлением производителями СУБД инструментария для доступа к данным внутри этих структур.

У такого подхода, применительно к проектируемой системе, можно выделить несколько плюсов:

• можем управлять структурой объектов без программирования, в том числе в реальном времени, путем администрирования. Администратор сможет зайти в некий интерфейс справочника полей и задать новые.

• ограничиваем ситуации случайного воздействия на данные - модифицировать json объект гораздо сложнее, чем данные в колонке.

• проще описывать объекты в коде - иногда можно вообще не описывать структуру документа в коде, а работать прямо с полями в JSON.

Но есть и минусы:

• невозможно нативно реализовать проверки данных при размещении в хранилище.

• валидацию данных придется проводить в коде.

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

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

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

Делаем прототип

Возьмем гипотезу, что NoSQL-подход для нашей системы применим как минимум не хуже, чем классический. Для ее проверки создадим прототип, в рамках которого реализуем оба подхода. В качестве СУБД возьмем Postgre, который уже давно умеет хорошо работать с JSON полями.

Создадим следующие таблицы:

Для описания объектов в табличном виде:

• r_objects, базовые данные по объектам: тип, дата создания и ссылка на хранилище атрибутов.

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

Для описания объектов в виде JSON:

• objects. Данные по объектам, где в поле data формата jsonb хранятся искомые атрибуты.

Остальные таблицы - это различные вспомогательные хранилища.

Реализуем в коде 5 разных типов объектов, для каждого из них описав программную структуру, механизм извлечения данных из хранилища и наполнения этими данными самих объектов.

Методика тестирования

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

• добавление данных по объекту. Критерий успешности: объект с данными появился в хранилище, метод вернул в ответе его идентификатор.

• обновление данных по объекту. Критерий успешности: данные в хранилище были изменены, метод вернул отметку об успехе. Удаление данных в системе не предусматривается, поэтому удаление объекта является операцией, аналогичной обновлению.

• извлечение данных по объекту. Критерий успешности: объект с данными возвращен в ответе на запрос. Извлечение объекта происходит по конкретному идентификатору, по критериям поиска и постранично (пагинация).

Генерация запросов будет происходить в 20 параллельных потоков по 50 запросов в каждом потоке. Для того, чтобы тестирование было действительно показательным с точки зрения производительности, предварительно наполним базу 200 млн. объектов.

Тестирование показало следующие результаты:

Первая (высокая) часть графика - это получение объектов по случайной странице - пагинация. Здесь в обоих случаях пришлось применить небольшой трюк - так как Postgres не агрегирует точное число строк в таблице, то узнать, сколько всего записей на объеме данных теста простым count - это долго, и для получения количества записей пришлось брать статистику данных по таблице. Также время получения данных на страницах свыше 10000-й неприлично велико, поэтому верхняя планка для получения случайного номера страницы была установлена в 10000. Учитывая специфику нашей системы, получение пагинированных данных не будет частой операцией, и поэтому такое извлечение данных применяется исключительно в целях тестирования.

Вторая (средняя) часть графика - вставка или обновление данных.

Третья (низкая) часть графика - получение данных по случайному идентификатору.

В случае табличной структуры данных - линий на графике больше, потому что с точки зрения программной структуры, получение данных для каждого типа объекта идет по разным методам, тогда как для NoSQL - по одинаковым.

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

Результаты тестов на 40000 запросов приведу в виде таблицы:

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

Что получилось?

В итоге, можно с уверенностью сказать, что для нашей системы NoSQL-подход к хранению данных оказался вполне подходящим. Даже с учетом потенциальных минусов, которые можно решить на этапе разработки серверной части, можно сказать, что он дает лучшие показатели по сравнению с табличным хранением. А плюсы в виде возможности настройки структуры объекта на лету, позволяют высвободить ресурсы от рутинного расширения объектов в сторону разработки новой функциональности.

Довольно долгое время я воевал с красно-черным деревом (далее - кчд). Вся информация, которую я находил, была в духе "листья и корень дерева всегда черные, ПОТОМУ ЧТО", "топ 5 свойств красно-черного дерева" или "3 случая при балансировке и 12 случаев при удалении ноды". Такой расклад меня не устраивал.

Мне не хотелось заучивать свойства дерева, псевдокод и варианты балансировки, я хотел знать: почему. Каким образом цвета помогают при балансировке? Почему у красной ноды не может быть красного потомка? Почему глубину дерева измеряют "черной высотой"?

Ответы на эти вопросы я получил только тогда, когда мне дали ссылку на лекцию про два-три дерево, с которого мы и начнем.

Эта статья разделена на 3 логические части. Я рекомендую прочитать их в указанном порядке. Первая часть (данная) будет направлена на введение в кчд и знакомство с ним. Во второй части мы поговорим о балансировке и вставке в кчд. В третьей, завершающей, части мы разберем процесс удаления ноды. Наберитесь терпения и приятного чтения:)

Дисклеймер

1. В этой статье не будет информации про плюсы и минусы дерева, его применение и т.д.: информации об асимптотике дерева и работе с ним в интернете полно.

2. Материал предназначен для тех, кто уже знаком с кчд и теперь хочет их понять, а также для тех, кто только знакомится с ними.

3. Статья не будет содержать деталей реализации структуры.

4. Можно считать что эта статья перевод английского видео материала в упрощенный русский текстовый вариант. Все ссылки я оставляю в конце статьи.

Два-три дерево

Чтобы понять красно-черное дерево, нужно понять два-три дерево

Забегая вперед, скажу, что два-три дерево - это, по сути, родитель нашего кчд, поэтому важно начать именно с него. Поймем два-три дерево - поймем и кчд.

Два-три дерево - абстрактный тип данных, напоминающий по структуре дерево. В нодах два-три дерева может быть одно или два значения и два или три потомка (от чего зависит количество значений и потомков ноды, узнаем ниже). Ноду с одним значением и двумя потомками будем называть 2-нода, ноду с двумя значениями и тремя потомками - 3-нода. Объяснение я начну с создания такого дерева: это наглядно и просто. Но некоторые уточнения нужны все же вначале:

1. Добавляя элемент, мы всегда спускаемся вниз по дереву.

2. Дерево отсортировано классически - меньшие значения находятся слева, бОльшие - справа.

3. Два-три дерево - отсортированное, сбалансированное дерево.

Итак, начнем с первой ноды, это число 5. Тут все просто - 5 становится корнем.

Добавим число 12. Число 12 мы так же добавляем в корень (помним, что нода может иметь два значения), но теперь нам нужно "отсортировать" нашу ноду (сортировать два элемента, ха), т.е. уложить их в порядке возрастания. В итоге получается нода 5-12.

Добавим следующее число. Пусть это будет 17. Давайте пока добавим наш элемент в единственную ноду и снова отсортируем ее. Получилась нода 5-12-17.

Внимательный читатель заметит тут подвох - выше я говорил о том, что наши ноды могут содержать не более двух элементов. Вот тут и происходит магия! Мы берем средний элемент нашей ноды и "просачиваем" его наверх. Итог виден на картинке. Корнем стало число 12, левым сыном число 5, правым - 17.

То, что мы сделали выше, можно назвать балансировкой два-три дерева. Правило в этой балансировке простое: если в ноде оказывается три значения, среднее значение мы "просачиваем" вверх. Алгоритм действий зависит от 3 условий:

1. Нода является корнем. Тогда ничего не остается, как создать новую ноду с одним значением и сделать ее новым корнем (как в нашем случае).

2. Родительская нода имеет одно значение. Тогда мы просто добавляем значение к родителю и завершаем балансировку (при этом у родителя появляется третий потомок).

3. Родительская нода имеет два значения. Тогда мы снова просачиваем значение вверх, пока не придем к пункту один или два.

Второй и третий случай балансировки будут рассмотрены ниже.

Окей, идем дальше. Давайте добавим число 3. Так как теперь мы не ограничиваемся одной нодой, спускаемся вниз. Понятно, что спуститься надо влево и добавить 3 к ноде со значением 5. Не забываем расставить 3 и 5 в нужном порядке. В итоге получилась нода 3-5.

Потерпите, мы близимся к самому интересному:)

Давайте добавим число 4 которое также пойдет влево и присоединится к ноде 3-5. Получится нода 3-4-5, которую, как мы уже знаем, нужно привести к нужному виду. Что делаем? Балансируем наше дерево, т.е. "просачиваем" значение 4 наверх.

Теперь самое интересное. Помимо того, что мы добавим 4 к корню, мы так же добавим корню третьего потомка - это будет нода, которая была больше 4. В нашем случае это 5. Картина будет выглядеть так:

Почему 5 не могла остаться на месте в своей ноде? Тут мы вспоминаем правило отсортированного дерева: значения меньше - слева, значения больше - справа. И так как 5 больше 4, мы не может оставить 5 слева, т.к. это нарушит наш инвариант. Поэтому ноде со значением 5 ничего не остается, как "переехать", и стать потомком ноды 4-12 (кстати, если бы у 5 были потомки, они так же "переехали" бы вместе с родителем).

Тут нужно сделать небольшую паузу и объяснить, как ориентироваться в нодах с тремя потомками. Все просто:

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

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

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

А теперь посмотрите на то, что получилось. Смело можно заявить, что это отсортированное, сбалансированное два-три дерево. Значения меньше лежат слева, значения больше - справа (тут, как и в случае со значениями 4-5-12, мы считаем, что 5 лежит справа от 4 и слева от 12). Корень имеет два значения и три потомка, что абсолютно соответствует описанию дерева выше. Сейчас вы можете сами попробовать добавить любое значение, чтобы удостовериться, что вы поняли логику (что произойдет с деревом, если добавить значение 7? А затем 9?).

Окей, с самим деревом, я надеюсь, разобрались. Ноды добавляются, дерево балансируется, искать можно, все супер. Но есть нюансы.

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

Красно-черное дерево

Как мы выяснили, главный недостаток два-три дерева - его структура. Тогда давайте попробуем превратить два-три дерево в дерево бинарное. Как мы можем сделать это?

Чтобы добиться этого, нам нужно простое представление для 3-ноды. Давайте разделим 3-ноду на две 2-ноды и свяжем их ссылками. Пометим эти ссылки каким-нибудь свойством, например, цветом, (возьмём красный), чтобы отличать такие ссылки в дереве от всех остальных.

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

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

Свойства красно-черного дерева

Свойство 1.

Две красные ноды не могут идти подряд. Это свойство приобретает смысл, если мы знаем, что красная нода - это по сути часть 3-ноды в 2-3 дереве. Ну а если две красные ноды идут подряд, то получается 4-нода, которой у нас не существует:)

Свойство 2.

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

Свойство 3.

Все null-ноды (ноды, которые не имеют потомков) - черные. Почему именно так, для себя объяснений я не нашел. Но хочу сказать, что это довольно удобное правило, когда дело доходит до балансировки дерева.

Свойство 4.

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

На этом введение подходит к концу. В следующей части мы поговорим о том, как вставлять ноды в дерево и балансировать его.