Структуры и алгоритмы обработки данных

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 = x.right; //левому узлу h присваиваем правый узел текущего узла

x.right = h; //правому узлу текущего узла присваиваем узел h

x.color = x.right.color; //перекрашиваем текущий узел в цвет узла справа

x.right.color = RED; //узлу справа текущего узла х присваиваем красный цвет

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

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

return x; //возвращаем текущий узел

}

private Node rotateLeft(Node h) //левое вращение

{

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

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

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

x.color = x.left.color; //перекрашиваем текущий узел в цвет узла слева

x.left.color = RED; //узлу слева текущего узла х присваиваем красный цвет

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

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

return x; //возвращаем текущий узел

}

private void flipColors(Node h) //перекрашивание узлов

{

h.color = !h.color; //меняем цвет текущего узла на противоположный

h.left.color = !h.left.color; //меняем цвет левого узла на противоположный

h.right.color = !h.right.color; //меняем цвет правого узла на противоположный

}

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

{

flipColors(h); //перекрасить узел h и его дочерние узлы

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

{

h.right = rotateRight(h.right); //правый узел - результат правого вращения

h = rotateLeft(h); //узел - результат левого вращения

}

return h; //вернуть узел

}

// Предполагая, что узел h красный и правый узел и левый узел правого узла черные, сделать правый узел h или один из дочерних узлов красным

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

{

flipColors(h); //перекрасить узел h и его дочерние узлы

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

h = rotateRight(h); //узел - результат правого вращения

return h; //вернуть узел

}

private Node balance(Node h) //восстановление красно-черного дерева

{

if (isRed(h.right)) 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 int height() //высота дерева

{

return height(root); //вызов метода с ссылкой на корень дерева

}

private int height(Node x) //метод вычисления высоты дерева

{

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

return -1; //вернуть -1

return 1 + Math.max(height(x.left), height(x.right)); //вернуть 1 + (максимальная высота из левого и правого поддеревьев)

}

public Key min() //минимальное значение ключа

{

if (isEmpty()) //если дерево пустое, вернуть

return null; //null

return min(root).key; //вызвать метод поиска минимального ключа

}

private Node min(Node x) //поиск минимального ключа

{

if (x.left == null) //если узла слева нет, то

return x; //вернуть текущий узел

else //иначе

return min(x.left); //вызываем рекурсивно метод для узла слева

}

public Key max() //максимальное значение ключа

{

if (isEmpty()) return null; //если дерево пустое, вернуть null

return max(root).key; //вызвать метод поиска максимального ключа

}

private Node max(Node x) //поиск максимального ключа

{

if (x.right == null) return x; //если узла справа нет, то вернуть текущий узел

else return max(x.right); //иначе вызвать рекурсивно этот метод для узла справа

}

public int rank(Key key) //количество ключей, меньших или = заданному

{

return rank(key, root); //вызов метода

}

private int rank(Key key, Node x) //количество ключей, меньших или = заданному, начиная с х

{

if (x == null) return 0; //если узел пустой, вернуть 0

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

if (cmp < 0) return rank(key, x.left); //если заданный меньше, то вызываем рекурсивно метод для левого узла

else if (cmp > 0) return 1 + size(x.left) + rank(key, x.right); //иначе если заданный больше, то вызываем рекурсивно метод для правого узла

else return size(x.left); //иначе возвращаем количество

}

public Iterable<Key> keys() //все ключи

{

return keys(min(), max()); //вернуть все ключи

}

public Iterable<Key> keys(Key lo, Key hi) //все ключи

{

Queue<Key> queue = new LinkedList <Key>(); //очередь для добавления ключей в порядке возрастания

keys(root, queue, lo, hi); //добавление ключей в очередь

return queue; //вернуть очередь

}

public void keys(Node x, Queue<Key> queue, Key lo, Key hi) //добавление ключей в очередь, начиная с узла х, между минимальным и максимальным

{

if (x == null) return; //если узел пустой, выйти из метода

int cmplo = lo.compareTo(x.key); //сравнение с меньшим

int cmphi = hi.compareTo(x.key); //сравнение с большим

if (cmplo < 0) keys(x.left, queue, lo, hi); //если меньше меньшего, выполнить рекурсивно метод для левого узла

if (cmplo <= 0 && cmphi >= 0) queue.add(x.key); //если меньше или = меньшему или больше или = большему, то просто добавить в очередь

if (cmphi > 0) keys(x.right, queue, lo, hi); //если больше большего, то выполнить рекурсивно метод для правого узла

}

public int size(Key lo, Key hi) //количество ключей между меньшим и большим ключами

{

if (lo.compareTo(hi) > 0) return 0; //если разница между наименьшим и наибольшим больше 0, то вернуть 0

if (contains(hi)) return rank(hi) - rank(lo) + 1; //если дерево содержит наибольший, то вернуть количество ключей между наибольшим и наименьшим +1

else return rank(hi) - rank(lo); //иначе вернуть количество ключей между наибольшим и наименьшим

}

private boolean isBalanced(Node x, int black) //сбалансированно ли дерево

{

if (x == null) return black == 0; //если текущая узел пустой, вернуть 0 черных узлов

if (!isRed(x)) black++; //если узел черный, пересчитать черные узлы

return isBalanced(x.left, black) && isBalanced(x.right, black); //вернуть, сбалансированно ли дерево справа и слева

}

}

Приложение Д

Класс main()

import java.util.Scanner;

public class main

{

public static void main (String args[])

{

Scanner scan = new Scanner(System.in); //создание объекта для ввода с клавиатуры

System.out.println("Тестирование хеш-таблицы\n\n");

System.out.println("Введите размер таблицы");

HashTable ht = new HashTable(scan.nextInt()); //создание экземпляра таблицы

char ch; //символ при вводе "n" или "у"

do //действия при нажатии "y" (да)

{

System.out.println("\nОперации хеш-таблицы\n");

System.out.println("1. Вставка ");

System.out.println("2. Удаление");

System.out.println("3. Найти по ключу");

int choice = scan.nextInt(); //считывание номера операции

switch (choice) //варианты:

{

case 1 : //при нажатии "1"

System.out.println("Введите ключ и значение");

ht.insert(scan.next(), scan.nextInt()); //считывание ключа и значения

break; //прерывание действия

case 2 : //при нажатии "2"

System.out.println("Введите ключ");

ht.remove(scan.next()); //удаление по ключу

break; //прерывание

case 3 : //при нажатии "3"

System.out.println("Введите ключ");

System.out.println("Значение искомого ключа = "+ ht.get(scan.next())); //вывод значения ключа

break; //прерывание

default : //при вводе некорректного символа

System.out.println("Ошибка \n ");

break; //прерывание

}

ht.printHashTable(); //отображение хеш-таблицы

System.out.println("\nХотите продолжить? (Введите y или n)\n");

ch = scan.next().charAt(0); //чтение символа у или n

}

while (ch == 'Y'|| ch == 'y'); //условие при выполнении действий с хеш-таблицей

}

}

Класс HashTable

public class HashTable //класс хеш-таблицы

{

private int TABLE_SIZE; //размер таблицы для создания объекта HashEntry

private int size; //размер таблицы

private HashEntry[] table; //таблица

private int primeSize; //размер таблицы (для вычисления хеш-функции)

public HashTable(int ts) //конструктор

{

size = 0;

TABLE_SIZE = ts;

table = new HashEntry[TABLE_SIZE];

for (int i = 0; i < TABLE_SIZE; i++)

table[i] = null;

primeSize = getPrime();

}

public int size()

{

return this.size;

}

public int getPrime() //получить число, меньшее, чем размер таблицы для вычисления функции myhash2

{

for (int i = TABLE_SIZE - 1; i >= 1; i--) //рассматриваем весь размер таблицы

{

int fact = 0; //счетчик

for (int j = 2; j <= (int) Math.sqrt(i); j++) //рассматриваем числа от 2 до корень(i)

if (i % j == 0)//если от деления нет остатка, то

fact++; //прибавляем 1

if (fact == 0) //если в счетчике ничего не было,

return i; //вернуть размер таблицы-1

}

return 3; //вернуть 3

}

public int get(String key) //получить значение по ключу

{

int hash1 = myhash1( key ); //вычисление функции myhash1

int hash2 = myhash2( key ); //вычисление функции myhash2

while (table[hash1] != null) //пока просмотр таблицы не окончится

{

if (table[hash1].key.equals(key)) //если значение ключа равно искомому,

return table[hash1].value; //возвратить значение найденного ключа

hash1 += hash2; //вычисляем хеш-функцию

hash1 %= TABLE_SIZE; //вычисляем хеш-значение

}

return -1; //ключ не найден

}

public void insert(String key, int value) //добавление в таблицу пары ключ-значение

{

if (size == TABLE_SIZE) //если размер таблицы равен уже заданному размеру, то

{

System.out.println("Таблица заполнена");

return;

}

int hash1 = myhash1( key ); //вычисление функции myhash1

int hash2 = myhash2( key ); //вычисление функции myhash2

while (table[hash1] != null) //пока просмотр таблицы не окончится

{

hash1 += hash2; //вычисляем хеш-функцию

hash1 %= TABLE_SIZE; //вычисляем хеш-значение

}

table[hash1] = new HashEntry(key, value); //создаем новое значение таблицы

size++; //увеличиваем размер на 1

}

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

{

int hash1 = myhash1( key ); //вычисление функции myhash1

int hash2 = myhash2( key ); //вычисление функции myhash2

while (table[hash1] != null && !table[hash1].key.equals(key)) //пока просмотр таблицы не окончится и значение ключа не равно искомому,

{

hash1 += hash2; //вычисляем хеш-функцию

hash1 %= TABLE_SIZE; //вычисляем хеш-значение

}

table[hash1] = null; //очищаем значение таблицы

size--; //уменьшаем размер таблицы на 1

}

private int myhash1(String x ) //хеш-функция, которая дает хеш-значение для ключа (String)

{

int hashVal = x.hashCode( ); //получение хеш-кода

hashVal %= TABLE_SIZE; //хеш-значение

if (hashVal < 0) //если хеш-значение меньше нуля, то

hashVal += TABLE_SIZE; //прибавим к нему размер таблицы

return hashVal; //вернуть хеш-значение

}

private int myhash2(String x ) //хеш-функция для двойного хеширования

{

int hashVal = x.hashCode( ); //получение хеш-кода

hashVal %= TABLE_SIZE; //хеш-значение

if (hashVal < 0) //если хеш-значение меньше нуля, то

hashVal += TABLE_SIZE; //прибавим к нему размер таблицы

return primeSize - hashVal % primeSize; //вернуть хеш-значение (размер таблицы - остаток от деления хеш-значения на размер таблицы)

}

private int hashFunc2 (String key) //хеш-функция умножением

{

float f; //индекс в таблице (массиве)

float A=(float) 0.6180339887499; //любое число в диапазоне 0..1

int sss=key.length(); //получение длины ключа

f = sss * A; //умножить ключ на константу А=(sqrt(5)-1)/2

f = f - (int) f; // взять дробную часть

return (int) (size*f); // возвратить число в диапазоне 0...size-1

}

private int hashFunc3 (String key) //хеш-функция делением с остатком

{

int len=key.length(); //получение длины ключа

int j=len%TABLE_SIZE; //остаток от деления на размер таблицы

return j; //вернуть значение

}

public void printHashTable() //вывод хеш-таблицы

{

System.out.println("\nХеш-таблица");

for (int i = 0; i < TABLE_SIZE; i++) //рассматриваем весь размер таблицы

if (table[i] != null) //если таблица не пуста, то

System.out.println(table[i].key +" "+table[i].value); // вывести ключ и значение ключа

}

}

Класс HashEntry

public class HashEntry //класс для создания таблицы

{

String key; //ключ

int value; //значение ключа

public HashEntry(String key, int value) //конструктор при создании таблицы

{

this.key = key;

this.value = value;

}

}

Размещено на Allbest.ru

...