ДЗ 7. Generics

Generics. ArrayList

Давайте вспомним наш список, реализованный на массиве, класс MyArrayList имплементирующий абстрактный класс MyList . Давайте сделаем его более гибким и попробуем сделать так, чтобы мы могли добавить любой тип данных в наш список. Для этого нам необходимо сделать наш список generic-ом.

1. Скопируйте классы MyList и MyArrayList из 5-ой домашки. Сделайте их generic-ами. Перепишите методы из п 8 - 14 чтобы они работали с нужным типом (классом).

2. Метод add (принимает на вход объект и добавляет его в конец списка за o(1))

3. Метод addFirst (принимает на вход объект и добавляет его в начало списка за o(1))

4. Метод insert (принимает на вход объект a и целое число i. Метод вставляет объект a на i-ое место за o(n))

5. Метод delete (принимает на вход одно число i. Метод удаляет i-ый элемент в списке за о(n))

6. Метод get (принимает на вход одно число i. Метод возвращает i-ый элемент в списке за о(n))

7. Метод size (выводит длину списка за o(1))

8. * Метод toArray В данной задаче этот метод должен принимать на вход массив T[] array, и возвращать новый массив, в котором будут все объекты нужного типа. Для того, чтобы создать generic массив воспользуйтесь функцией:

T[] array = (T[]) Array.newInstance(array.getClass(), sizeOfList);

Generics. Доп. домашка. AVL tree

В этой домашке у нас есть часть с “повышенной сложностью”. Если у вас возникли затруднения с ArrayList, то задание с деревом можно пропустить и сконцентрироваться на списке. Однако если вы планируете получить автомат по зачету - сделать это задание нужно.

Давайте попробуем написать сбалансированное по высоте двоичное дерево поиска, которое может работать с любыми числами - как с любыми целыми, так и любыми дробными.

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

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

Однако АВЛ-дерево имеет дополнительное ограничение - для каждой его вершины высота её двух поддеревьев различается не более чем на 1. См. статью на википедии

1. Создайте класс MyAvlTree с конструктором от числа, которое будет в корне дерева.
2. Реализуйте метод contains который принимает на вход число и возвращает boolean, содержит ли дерево вершину с таким числом
3. Реализуйте метод add, который принимает на вход число и вставляет его в дерево
4. Реализуйте метод delete, который принимает на вход число и удаляет его из дерева
5. Реализуйте метод size, который возвращает размер дерева
6. Реализуйте метод toArray, который возвращает дерево в виде массива чисел. Пусть Вершины двоичного дерева располагаются в массиве следующим образом: если k – индекс вершины дерева, то ее потомки находятся в элементах массива с индексами 2k + 1 и 2(k + 1). Для создания generics-массива см. соображения из задания 14 первой части домашки.

P.S. Для того чтобы наше дерево работало с любыми чиселками, нам нужно понять, какие ограничения наложить на параметр типа (T). Рекомендую почитать java документацию на Integer и найти в ней тип(ы), которым(и) нужно ограничить T, чтобы все заработало.

Полезные ссылки

Статья про дженерики