Типы и структуры данных

Рис. 1. Пример работы 1-ой части программы

1. Создать файл данных, описывающий данную предметную область. Выбрать одно из полей как ключ поиска.

1. На основе файла создать словарь, состоящий из пар: КЛЮЧ- № записи.

2. Упорядочить словарь по возрастанию ключей.

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

4. Сравнить времена поиска со словарем и без словаря (графики и таблицы)

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

2.1 Краткое теоретическое описание

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

· INSERT(ключ, значение)

· FIND(ключ)

· REMOVE(ключ)

Предполагается, что ассоциативный массив не может хранить две пары с одинаковыми ключами.

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

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

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

Существует множество различных реализаций ассоциативного массива.

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

Поиск - нахождение какой-либо конкретной информации в большом объеме ранее собранных данных.

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

Целью поиска является нахождение всех записей подходящих к заданному ключу поиска.

Алгоритм Кнута-Морриса-Пратта

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

Если j определяет позицию в слове-образце, содержащую первый несовпадающий символ то величина сдвига определяется как j-dj. Значения D - таблица сдвигов определяется как размер самой длинной последовательности символов слова, непосредственно предшествующих позиции j (суффикс), которая полностью совпадает с началом слова (префикс). D зависит только от слова и не зависит от текста. Для каждого j будет своя величина D, которую обозначим dj. Перед поиском осуществляется формирование D.

Алгоритм КМП результативно находит подстроку в строке. Поиск информации - одно из основных использований компьютера. Одна из простейших задач поиска информации - поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна - она применяется в текстовых редакторах, СУБД, поисковых машинах…

2.2 Результаты работы программы

1) 2)

8540 символов 145100 символов

Время поиска по ключу: 8 мс Время поиска по ключу: 26 мс

Время поиска со словарем: 3 мс Время поиска со словарем: 18 мс

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

Рис. 2 . Поиск с использованием словаря

Рис. 3. Поиск с использование ключа

Таблица 1. Алгоритм Кнута-Морриса-Пратта

3. Исследование эффективности алгоритмов сортировок для различных структур и размерностей данных

Постановка задачи

· Провести экспериментальный сравнительный анализ различных методов сортировки. Для чистоты эксперимента сортировка должна проводиться на одинаковых наборах входных данных, которые генерируются случайным образом. Для более полного анализа методов сортировка должна проводиться для различных размерностей данных, например: 500, 1000, 3000, 5000, 8000, 10000, 30000, 60000.

· Исходные наборы данных - массивы или файлы соответствующего типа (по № варианта).

· Проследить динамику роста требуемого для сортировки времени.

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

· Сравнить теоретические оценки времени сортировки и числа требуемых операций с экспериментальными.

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

· Провести исследования o для выбранных алгоритмов внутренней сортировки (один из методов вставки и один из методов обменной сортировки)

Постановка задачи

Реализовать процедуры создания красно-черных деревьев (динамическое представление), поиска, удаления и добавления узлов. Реализовать малое левое вращение для решения задач балансировки

Теоретические положения.

Красно-чёрное дерево - самобалансирующееся двоичное дерево поиска, имеющее сложность О(log n), которое быстро выполняет основные операции: добавление, удаление и поиск узла. Узлы дерева имеют атрибут "цвет", что помогает сбалансировать дерево. Атрибут может принимать значения "черный" или "красный". Дерево обладает свойствами: корень и листья дерева - обязательно черные и оба потомка красного узла - черные.

Балансировка дерева - операция изменения связи предок-потомок в случае разницы высот правого и левого поддеревьев больше 1. Результат достигается путем вращения поддерева данной вершины.

Класс main()

import java.util.Dictionary;

import java.util.Hashtable;

public class part2

{

public static void main (String[] args)

{

String KEY="Интернет магазин"; //ключ, по которому будем искать в тексте

Dictionary<Integer, String> dict=new Hashtable <Integer, String>(); //создаем словарь

String S=new String ("Интернет магазин - это специализированный сайт, предлагающий посетителям возможности по приобретению тех или иных товаров или услуг. Идея продавать что-то через Интернет по возрасту сравнима с самим Интернетом. Однако период интенсивного развития онлайновых магазинов связан с появлением веба. Интернет-магазин может быть создан и торговой фирмой, уже имеющей большой опыт продаж в офлайне, и коллективом энтузиастов, решивших сразу начать с онлайна. Онлайновая торговля имеет целый ряд отличительных особенностей, требующих особенного подхода.");

//текст, в котором будет реализован поиск

try

{

file.WriteObject(S);

dict.put(4, "Интернет магазин"); //ключ 4

System.out.println (file.ReadObject().length()+" символов"); //длина текста (=7710)

long t1=System.currentTimeMillis(); //засекаем время начала поиска по ключу

KMP.KnuthMorrisPratt(file.ReadObject(), KEY); //используя чтение из файла, находим по ключу KEY

long t2=System.currentTimeMillis(); //окончание времени поиска по ключу

long t3=System.currentTimeMillis(); //засекаем время начала поиска по ключу

int key=4; //ищем подстроку Интернет магазин

KMP.KnuthMorrisPratt(file.ReadObject(), dict.get(key)); //используя чтение из файла, находим строки по ключам из словаря

long t4=System.currentTimeMillis(); //окончание времени поиска по ключу

System.out.println ("Время поиска по ключу: "+(t2-t1) +" мс"); // вывод результата

System.out.println ("Время поиска со словарем: "+(t4-t3) +" мс"); // вывод результата

}

catch (Exception e) //если файл не найден, бросаем исключение

{

e.getMessage();

}

}

}

Класс KMP, в котором описан алгоритм поиска ключа

public class KMP

{

public static int KnuthMorrisPratt (String where, String what)

{

int n=where.length(); //длина строки, в которой происходит поиск

int m=what.length(); //длина подстроки

//формирование таблицы сдвигов

int[] table=new int [m]; //таблица сдвигов (массив)

table[0]=0; //значение первого элемента =0

int shift=0; //сдвиг равен 0

for (int q=1; q<m; q++)//проходим по количеству букв, которое находится в ключе (подстроке)

{

while (shift > 0 && (what.charAt(shift) != what.charAt(q))) //ищем совпадающее начало кусочка текста и подстроки

shift = table[shift-1]; //меняем сдвиг

if (what.charAt(shift)==what.charAt(q)) shift++; //считаем количество вхождений символов

table[q]=shift; //записываем значения в таблицу - создаем префиксную функцию

}

//поиск с использованием таблицы сдвигов

shift=0; //сдвиг равен 0

for (int i=0; i<n; i++) //прохождение по всему тексту

{

while (shift>0 && what.charAt(shift)!=where.charAt(i)) //если первые символы не совпали, то

shift=table[shift-1]; //двигаем текст на максимально возможное знаечение

if (what.charAt(shift)==where.charAt(i)) //если символы совпадают, то

shift++; //увеличиваем количество совпавших символов

if (shift==m) //если длина совпадения равна длине подстроки

return i-m+1; //подстрока найдена

}

return -1; //если ничего не найдено, возвращаем некорректное значение

}

}

Класс file, позволяющий создать и использовать файл

import java.io.*;

public class file //создание - чтение файла

{

public static void WriteObject (String S) throws IOException //создание файла, на вход идет строка (в нашем случае текст)

{

FileOutputStream fileOutput=new FileOutputStream ("file.dat"); //открываем файловый поток

ObjectOutputStream objectOutput=new ObjectOutputStream (fileOutput); //открываем поток, в который будем записывать объект (в нашем случае текст)

objectOutput.writeObject(S); //записываем в файл строку

fileOutput.close(); //закрываем поток

objectOutput.close(); //закрываем поток

}

public static String ReadObject() throws IOException, ClassNotFoundException //извлечение файла

{

FileInputStream fileInput=new FileInputStream ("file.dat"); //открываем файловый поток

ObjectInputStream objectInput=new ObjectInputStream(fileInput); //открываем поток, из которого будем читать объект (в нашем слкчае текст)

String s=(String) objectInput.readObject(); //создаем переменную, в которую записываем текст

fileInput.close(); //закрываем поток

objectInput.close(); //закрываем поток

return s; //возвращаем строку (текст)}}

Приложение В.

using System;

using System.Diagnostics;

using System.Collections.Generic;

using System.Linq;

using System.Text;

namespace PersonnelDepartmentApp {

public class Sorting {

public void swap(int[] arr, int i, int j) {

int t = arr[i];

arr[i] = arr[j];

arr[j] = t;

}

public void swap(int[] arr, int i) {

int temp;

temp = arr[i];

arr[i] = arr[i - 1];

arr[i - 1] = temp;

}

public int maxValue(int[] arr) {

int maxValue = int.MinValue;

for (int i = 0; i < arr.Length; i++) {

if (arr[i] > maxValue) {

maxValue = arr[i];

}

}

return maxValue;

}

public int[] selectionSort(int[] mass) {

int[] a = (int[]) mass.Clone();

int len = a.Length;

for (int i = 0; i < len - 1; i++) {

int min = i;

for(int j = i + 1; j < len; j++) {

if(a[j] < a[min]) {

min = j;

}

}

if(min != i) {

int t = a[i];

a[i] = a[min];

a[min] = t;

}

}

return a;

}

public int[] bubbleSort(int[] mass){

int[] arr = (int[]) mass.Clone();

for(int i = arr.Length-1 ; i > 0 ; i--){

for(int j = 0 ; j < i ; j++){

if(arr[j] > arr[j+1])

swap(arr, j, j+1);

}

}

return arr;

}

public int[] gnomeSort(int[] mass) {

int[] a = (int[]) mass.Clone();

int size = a.Length, i = 1,j = 2;

while (i < size) {

//для сортировки по убыванию поменяйте знак сравнения на <

if (a[i - 1] > a[i]) {

i = j;

j = j + 1;

} else {

swap(a, i);

i = i - 1;

if (i == 0) {

i = j;

j = j + 1;

}

}

}

return a;

}

public int[] insertionSort (int[] mass) {

int[] m = (int[]) mass.Clone();

int t, i, j;

for (i = 0; i < m.Length; i++) {

t = m[i];

for (j=i-1; j>=0 && m[j] > t; j--)

m[j+1] = m[j];

m[j+1] = t;

}

return m;

}

public void merge(int[] Mas, int left, int right, int medium) {

int j = left;

int k = medium + 1;

int count = right - left + 1;

if (count <= 1)

return;

int[] TmpMas = new int[count];

for (int i = 0; i < count; i++) {

if (j <= medium && k <= right) {

if (Mas[j] < Mas[k])

TmpMas[i] = Mas[j++];

else

TmpMas[i] = Mas[k++];

} else {

if (j <= medium)

TmpMas[i] = Mas[j++];

else

TmpMas[i] = Mas[k++];

}

}

j = 0;

for (int i = left; i <= right; i++) {

Mas[i] = TmpMas[j++];

}

}

public void mergeSort(int[] a, int l, int r) {

int m;

// Условие выхода из рекурсии

if(l >= r)

return;

m = (l + r) / 2;

// Рекурсивная сортировка полученных массивов

mergeSort(a, l, m);

mergeSort(a, m + 1, r);

merge(a, l, r, m);

}

public int[] bucketSort(int[] mass) {

int[] items = new int[mass.Length];

// Предварительная проверка элементов исходного массива

if (items == null || items.Length < 2) {

return mass;

}

int maxValue = items[0];

int minValue = items[0];

for (int i = 1; i < items.Length; i++) {

if (items[i] > maxValue)

maxValue = items[i];

if (items[i] < minValue)

minValue = items[i];

}

List<int>[] bucket = new List<int>[maxValue - minValue + 1];

for (int i = 0; i < bucket.Length; i++) {

bucket[i] = new List<int>();

}

// Занесение значений в пакеты

for (int i = 0; i < items.Length; i++) {

bucket[items[i] - minValue].Add(items[i]);

}

int position = 0;

for (int i = 0; i < bucket.Length; i++)

{

if (bucket[i].Count > 0)

{

for (int j = 0; j < bucket[i].Count; j++)

{

items[position] = (int) bucket[i][j];

position++;

}

}

}

return items;

}

public int[] shellSort(int[] mass) {

int[] a = (int[]) mass.Clone();

int i, j, k, h, m=0, b=a.Length;

int[] d = { 1, 4, 10, 23, 57, 145, 356, 911, 1968, 4711, 11969, 27901,

84801, 213331, 543749, 1355339, 3501671, 8810089, 21521774,

58548857, 157840433, 410151271, 1131376761, 2147483647 };

while (d[m] < b) {

++m;

}

while (--m >= 0) {

k = d[m];

for (i=k; i<b; i++) { // k-сортировка

j=i;

h=a[i];

while ((j >= k) && (a[j-k] > h)) {

a[j]=a[j-k];

j = j-k;

}

a[j] = h;

}

}

return a;

}

public int[] heapSort(int[] mass) {

int[] a = (int[]) mass.Clone();

int n = a.Length, i, sh = 0, b = 0;

while (true) {

b = 0;

for (i = 0; i < n; ++i) {

if (i*2 + 2 + sh < n) {

if (a[i+sh] > a[i*2 + 1 + sh] || a[i + sh] > a[i*2 + 2 + sh]) {

if (a[i*2+1+sh] < a[i*2+2+sh]) {

int t = a[i+sh];

a[i+sh] = a[i*2+1+sh];

a[i*2+1+sh] = t;

b = 1;

} else if (a[i*2+2+sh] < a[i*2+1+sh]) {

int t = a[i+sh];

a[i+sh] = a[i*2+2+sh];

a[i*2+2+sh] = t;

b = 1;

}

}

} else if (i * 2 + 1 + sh < n) {

if (a[i+sh] > a[i*2+1+sh]) {

int t = a[i+sh];

a[i+sh] = a[i*2+1+sh];

a[i*2+1+sh] = t;

b=1;

}

}

}

if (b == 0) {

sh++;

}

if (sh+2==n)

break;

}

return a;

}

public int partition (int[] array, int start, int end) {

int marker = start;

for (int i = start; i <= end; i++) {

if (array[i] <= array[end]) {

int temp = array[marker];

array[marker] = array[i];

array[i] = temp;

marker += 1;

}

}

return marker - 1;

}

public void quickSort (int[] array, int start, int end) {

int pivot;

if (start >= end) {

return;

}

pivot = partition (array, start, end);

quickSort (array, start, pivot-1);

quickSort (array, pivot+1, end);

}

public void stoogeSort(int[] item, int left,int right) {

int tmp, k;

if(item[left] > item[right]) {

tmp=item[left];

item[left]=item[right];

item[right]=tmp;

}

if((left+1)>=right)

return;

k = (int) ((right - left + 1) / 3);

stoogeSort(item,left, right-k);

stoogeSort(item, left+k, right);

stoogeSort(item, left, right-k);

}

public void executeTest(int[] quantity) {

Random random = new Random();

Sorting sorter = new Sorting();

for (int i = 0; i < quantity.Length; i++) {

Console.WriteLine("Отчёт по массиву из " + quantity[i] + " элементов:");

int[] mass = new int[quantity[i]];

for (int j = 0; j < quantity[i]; j++) {

mass[j] = random.Next(10000);

}

long start = 0, end = 0;

Console.Write("Сортировка выбором:");

try {

start = Stopwatch.GetTimestamp();

sorter.selectionSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Сортировка простыми обменами, сортировка пузырькa:");

try {

start = Stopwatch.GetTimestamp();

sorter.bubbleSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Гномья сортировка:");

try {

start = Stopwatch.GetTimestamp();

sorter.gnomeSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Сортировка вставками:");

try {

start = Stopwatch.GetTimestamp();

sorter.insertionSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Сортировка слиянием:");

try {

start = Stopwatch.GetTimestamp();

sorter.mergeSort((int[]) mass.Clone(), 0, mass.Length - 1);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Блочная сортировка:");

try {

start = Stopwatch.GetTimestamp();

sorter.bucketSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Сортировка Шелла:");

try {

start = Stopwatch.GetTimestamp();

sorter.shellSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Пирамидальная сортировка:");

try {

start = Stopwatch.GetTimestamp();

sorter.heapSort(mass);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Быстрая сортировка:");

try {

start = Stopwatch.GetTimestamp();

sorter.quickSort((int[]) mass.Clone(), 0, mass.Length - 1);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

Console.Write("Stooge Sort:");

try {

start = Stopwatch.GetTimestamp();

sorter.stoogeSort((int[]) mass.Clone(), 0, mass.Length - 1);

end = Stopwatch.GetTimestamp();

Console.Write((end - start) + " нс\n");

} catch (Exception e) {

Console.Write(e.Message + "\n");

Console.WriteLine(e.StackTrace);

}

}

}

}

}

\

Класс main()

import java.util.Random;

public class main

{

public static void main(String[] args)

{

Random r=new Random(); //для случайных значений ключей и значений ключей

RedBlackBST<Integer, Integer> st = new RedBlackBST<Integer, Integer>(); //создание экземпляра дерева

for (int i=0; i<10; i++) //10 узлов дерева (пример)

st.put(r.nextInt(100), r.nextInt(100)); //добавление узлов в дерево

for (Integer s : st.keys()) //среди всех ключей

System.out.println("Ключ: "+s + "; значение: " + st.get(s)); //вывести информацию по ключу (ключ-значение)

System.out.println("Содержит ключ 34: "+st.contains(34));

System.out.println("Размер дерева: "+st.size());

System.out.println("Высота дерева: "+st.height());

System.out.println("Получить значение ключа 56: "+st.get(56));

System.out.println("Максимальный ключ: "+st.max());

}

}

Класс RedBlackBST (Red-Black Binary Search Tree)

import java.util.LinkedList;

import java.util.NoSuchElementException;

import java.util.Queue;

public class RedBlackBST<Key extends Comparable<Key>, Value> //класс красно-черного дерева

{

private static final boolean RED = true; //красный узел - true

private static final boolean BLACK = false;//черный узел - false

private Node root; // корень дерева

private class Node //класс узлов дерева

{

private Key key; // ключ узла

private Value val; // значение ключа

private Node left, right; // ссылки на левый и правый элементы

private boolean color; // атрибут цвет

private int N; // счетчик

public Node(Key key, Value val, boolean color, int N) //конструктор

{

this.key = key;

this.val = val;

this.color = color;

this.N = N;

}

}

private boolean isRed(Node x) //является ли узел красным

{

if (x == null) //если в дереве ничего нет

return false; //возвращаем false

return (x.color == RED); //является ли узел красным

}

private int size(Node x) //число узлов в дереве

{

if (x == null) //если корень пустой,

return 0; //то вернуть 0

return x.N; //вернуть число узлов

}

public int size() //число узлов (ключ-значение)

{

return size(root); //вызов метода, начиная с корня

}

public Key search (Key key)

{

return search(root, key);

}

private Key search (Node current, Key key)

{

if (current == null)

return null;

if (current.key == key)

return current.key;

return search(key < current.key ? current.left : current.right, key);

}

public boolean isEmpty() //является ли дерево пустым

{

return root == null; //вернуть true или false

}

public Value get(Key key) //вернуть значение по ключу

{

return get(root, key); //вызов метода с передачей дерева в нем

}

private Value get(Node x, Key key) //получение значение

{

while (x != null) //пока узел не будет пустым,

{

int cmp = key.compareTo(x.key); //сравниваем значение ключа с текущим узлом

if (cmp < 0) x = x.left; //если значение меньше, идем влево

else

if (cmp > 0) x = x.right; //иначе если значение больше, идем вправо

else return x.val; //иначе вернуть искомое значение

}

return null; //если ничего не найдено, вернуть null

}

public boolean contains(Key key) //содержит ли дерево такой ключ

{

return (get(key) != null); //вернуть результат через метод get (Key key)

}

public void put(Key key, Value val) //вставка узла с ключом и значением

{

root = put(root, key, val); //создание узла с передачей в другой метод (private)

root.color = BLACK; //окрашивание корня в черный цвет (для того, чтобы мы могли далее добавлять узлы любого цвета)

}

private Node put(Node h, Key key, Value val)

{

if (h == null) //если узел пустой,

return new Node(key, val, RED, 1); //то окрашиваем его в красный

int cmp = key.compareTo(h.key); //сравниваем вставляемый узел с текущим

if (cmp < 0) h.left = put(h.left, key, val); //если меньше, то вызываем этот метод рекурсивно для вставки слева

else

if (cmp > 0) h.right = put(h.right, key, val); //иначе вызываем метод рекурсивно для вставки справа

else h.val = val; //иначе перезаписываем это значение

if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h); //если узел справа красный и узел слева черный, то вызываем левое вращение узла

if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h); //если узел А слева красный и левый узел В узла А красный, то вызываем правое вращение

if (isRed(h.left) && isRed(h.right)) flipColors(h); //если узел слева красный и узел справа красный, то меняем их цвета на черные (красные узлы имеют только черные дочерние узлы)

h.N = size(h.left) + size(h.right) + 1; //считаем общее количество узлов

return h; //возвращаем узел

}

public void deleteMin() //удаление минимального элемента

{

if (isEmpty()) throw new NoSuchElementException("BST underflow"); //если дерево пустое, выбросить exception

if (!isRed(root.left) && !isRed(root.right)) //если оба дочерних узла корня черные,

root.color = RED; //то перекрасить корень в красный

root = deleteMin(root); //вызов метода для корня

if (!isEmpty()) root.color = BLACK; //если дерево не пустое, то перекрасить корень в черный

}

private Node deleteMin(Node h) //удаление минимального элемента, начиная с корня h

{

if (h.left == null)//если элемента, меньшего корня нет, то

return null; //возвратить null

if (!isRed(h.left) && !isRed(h.left.left)) //если узел слева черный и его дочерний узел слева черный, то

h = moveRedLeft(h); //перекрасить в красный цвет дочерний узел слева

h.left = deleteMin(h.left); //вызываем этот метод рекурсивно для узла слева

return balance(h); //вернуть узел в сбалансированном дереве

}

public void delete(Key key) //удаление по ключу

{

if (!contains(key)) //если такого ключа не существует, то

{

System.err.println("symbol table does not contain " + key); //написать сообщение пользователю

return; //вернуть

}

if (!isRed(root.left) && !isRed(root.right)) //если оба дочерних узла корня черные, то

root.color = RED; //перекрасить корень в красный

root = delete(root, key); //вызов метода удаления, начиная с корня

if (!isEmpty()) root.color = BLACK; //если дерево не пустое, покрасить корень в черный

}

private Node delete(Node h, Key key) //удаление узла с ключом key, начиная с корня h

{

if (key.compareTo(h.key) < 0) //если ключ этого узла меньше ключа корня, то

{

if (!isRed(h.left) && !isRed(h.left.left)) //если узел А слева черный и левый узел В узла А черный,

h = moveRedLeft(h); //то перекрашиваем в красный цвет дочерний узел слева

h.left = delete(h.left, key); //вызываем рекурсивно этот метод для узла слева

}

else

{

if (isRed(h.left)) //если узел слева красный, то

h = rotateRight(h); //вызываем правое вращение

if (key.compareTo(h.key) == 0 && (h.right == null)) //если значение ключа искомого узла равно значению ключа текущего узла и правый узел пустой, то

return null; //ничего не возвращать

if (!isRed(h.right) && !isRed(h.right.left)) //если узел А справа и левый узел узла А черные, то

h = moveRedRight(h); //перекрасить в красный цвет дочерний узел справа

if (key.compareTo(h.key) == 0) //если значение ключа искомого узла равно значению ключа текущего узла, то

{

Node x = min(h.right); //находим минимальный узел справа

h.key = x.key; //переприсваиваем удаленному узлу ключ минимального

h.val = x.val; //переприсваиваем удаленному узлу значение минимального

h.right = deleteMin(h.right); //удаляем минимальный узел

}

else h.right = delete(h.right, key); //иначе сделать то же самое для узла справа

}

return balance(h); //вернуть сбалансированное дерево

}

private Node rotateRight(Node h) //правое вращение узла h

{

Node x = h.left; //текущему узлу присваиваем левый узел узла h

h.left...