~553, 554 дни 👨‍💻 | Закончил работу над бинарным деревом

Написал 545 строк тестов. Было не просто.

Какие сделал выводы?

1) Тестировать все возможные варианты;

2) Если по условию задачи в отрицательном случае метод должен возвращать False, то в противоположном случае обязательно реализуем возврат True. Не оставляем None.

3) Листок и ручка - лучшие друзья при решении подобных задач. Сначала пишем, рисуем. Только потом пишем код.

---------
И самое главное! Читаем условия задачи не жопой! А внимательно, с ручкой и бумагой!

С итоговым кодом можно ознакомиться по ссылке на гитхаб: https://github.com/avagners/algorithms_and_data_structures/tree/main/data_structures%2Fbinary_search_trees

📚Чтение:
+ 0 стр. "Изучаем SQL" Алан Бьюли (2007 год)
(135 страниц из 308)

~555, 556 дни 👨‍💻 | Поиск в глубину и поиск в ширину

Есть 2 общепринятых способа обхода дерева:
- обход в ширину - это когда перебираем узлы по уровням: сначала корень, потом все узлы второго уровня, далее все узлы третьего уровня, и так далее;

- обход в глубину - это рекурсивный перебор узлов по веткам. Например, сначала перебираем все узлы левого поддерева, потом корень, потом все правого поддерева. Такой способ возвращает упорядоченный список узлов в порядке возрастания. Его ещё называют in-order. Есть ещё pre-order (сначала проверяем узел), и post-order (узел проверяем последним);

С кодом можно ознакомиться на гитхаб: https://github.com/avagners/algorithms_and_data_structures/blob/main/data_structures/binary_search_trees/binary_search_tree.py#L165
---------
📚Чтение:
+ 15 стр. "Изучаем SQL" Алан Бьюли (2007 год)
(150 страниц из 308)

​~557 день 👨‍💻 | Двоичное дерево в виде массива

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

Основные моменты.

1) Узлы в массиве хранятся в последовательном порядке;
2) Дерево хранится целиком. Т.е. если узла нет, то на его месте в массиве хранится None. Пример на изображении.
3) Индексы родителя, левого или правого потомка можно найти след. образом:
- индекс родителя:
(I - 1) / 2
- индекс левого потомка:
2 * I + 1
- индекс правого потомка:
2 * I + 2
, где I - это текущий индекс массива.

—————
📚Чтение:
+ 0 стр. "Изучаем SQL" Алан Бьюли (2007 год)
(150 страниц из 308)

~558 день 👨‍💻 | Двоичное дерево в виде массива

Реализовал двоичное дерево поиска в виде массива.
Написал 2 метода:
- поиск индекса по ключу;
- вставка нового ключа в массив;

Покрыл всё тестами.

С кодом можно ознакомиться на гитхаб:
https://github.com/avagners/algorithms_and_data_structures/tree/main/data_structures/binary_search_trees_array

—————
📚Чтение:
+ 0 стр. "Изучаем SQL" Алан Бьюли (2007 год)
(150 страниц из 308)

~559, 560 дни 👨‍💻 | Еще бинарные деревья поиска

Реализовал функцию преобразования неупорядоченного массива в сбалансированное бинарное дерево поиска.

На вход подается неотсортированный массив целых чисел. Размер массива соответствует полностью заполненному дереву N-глубины. Функция возвращает сбалансированное бинарное дерево поиска в виде массива.

Написал тесты.

С кодом можно ознакомиться на гитхаб:
https://github.com/avagners/algorithms_and_data_structures/tree/main/data_structures/generate_bbst_array

—————
P.s. ниже формула нахождения размера массива для создания бинарного дерева нужной глубины:

2^(H+1)-1

, где H - необходимая глубина дерева.

Например, для создания дерева глубиной:
- в 2 уровня - размер массива 7
- в 3 уровня - размер массива 15


📚Чтение:
+ 0 стр. "Изучаем SQL" Алан Бьюли (2007 год)
(150 страниц из 308)

~ 561 день 👨‍💻 | снова бинарные деревья...

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

Также написал метод проверки - сбалансировано дерево или нет. С данным методом просидел несколько часов)

Написал тесты.

С кодом можно ознакомиться по ссылке на гитхаб:
https://github.com/avagners/algorithms_and_data_structures/tree/main/data_structures%2Fbalanced_binary_search_trees

​~ 562, 563, 564 день 👨‍💻 | Кучи/пирамиды

С понедельника знакомился со структурой данных "Пирамида (еще называют "куча").

Эту структуру можно назвать деревом, которая имеет следующие признаки:
- реализуется на основе массива;
- значение ключа родителя всегда больше потомков;
- нет упорядоченности левого и правого потомка;

Фактически это версия бинарного дерева, которое упорядоченно сверху вниз.

Скорость выполнения операций:
- Удаление максимального элемента - О(1);
- Вставка нового элемента - О(log2 N);
- Поиск - О(n)

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

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

Покрыл код тестами.

С кодом можно ознакомиться по ссылке на гитхаб:
https://github.com/avagners/algorithms_and_data_structures/blob/main/data_structures/heap/heap_array.py

~ 565 - 567 дни 👨‍💻 | Графы

Последние дни знакомился с графами.

Графы - это структура связанных данных. Она состоит из вершин и ребёр.
Рёбра - это связи между вершинами.

Графы похожи на деревья. Точнее деревья являются частным случаем графов.

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

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

Направленный граф (ориентированный) - это граф с рёбрами, у которых есть направление.

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

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

Вершины обычно хранятся в виде объектов класса в массиве.
Рёбра (т.е. связи между вершинами) реализуются 2-мя способами:
1) Матрица смежности;
2) Список смежности;

Реализовал структуру данных и методы вставки вершины/связи, удаления вершины/связи, проверка смежности вершин.

Покрыл код тестами.

P.s. как здорово, что прошлым летом я прорешал большое кол-во маленьких задач по работе с матрицами на python. 🤓

С кодом можно ознакомиться на гитхаб:
https://github.com/avagners/algorithms_and_data_structures/tree/main/data_structures/graph

~ 568, 569 дни 👨‍💻 | Поиск пути в графе, чётные деревья

За эти два дня написал 2 метода:

1) Поиск пути в графе (обход в глубину).

Ищем путь из вершины А к вершине Б.
Метод возвращает список вершин от А до Б.

Ссылка на гитхаб: https://github.com/avagners/algorithms_and_data_structures/blob/b888bc9ef1116eb3383e44769b4473bf3fcda893/data_structures/graph/simple_graph.py#L50

2) Разделение дерева на чётные поддеревья.

Дано дерево. Нужно разорвать в дереве связи между узлами таким образом, чтобы получилось максимально возможное кол-во чётных деревьев.
Метод возвращает список узлов, между которыми нужно удалить связь

Ссылка на гитхаб: https://github.com/avagners/algorithms_and_data_structures/blob/b888bc9ef1116eb3383e44769b4473bf3fcda893/data_structures/trees/SimpleTree.py#L89

Код покрыл тестами.

~ 570, 571 дни 👨‍💻 | Поиск пути в графе (обход в ширину)

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

Данная реализация позволяет получить кратчайший путь. Это его отличает от обхода в глубину.

Кратчайший путь мы получаем так как обходим все смежные вершины последовательно. И только потом опускаемся на уровень вниз.

Сам метод поиска реализовать было относительно не сложно.
Довольно много времени провёл над решением возврата пути из вершины А к вершине В.

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

Код покрыл тестами.

С кодом можно ознакомиться по ссылке на гитхаб: https://github.com/avagners/algorithms_and_data_structures/blob/main/data_structures/graph/simple_graph.py#L84

▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓░  90%

Потрачено в этом году👆👆👆

Ещё 10% чтобы закрыть оставшиеся задачи поставленные на этот год.

~ 572 день 👨‍💻 | Уязвимые вершины в графе

Реализовал метод нахождения уязвимых вершин в графе.

Уязвимые вершины - это вершины, которые не в ходят ни в какой треугольник.

Треугольник вершин - это когда у смежных вершин есть связь.

Например, у вершины А есть смежные вершины В и С. Если у вершин В и С есть связь, то вершины устойчивы, они связаны в треугольник.

Если вершина не имеет ни одной связи между смежных вершин, то данная вершина уязвимая.

Код покрыл тестами.

С кодом можно ознакомиться на гитхаб:
https://github.com/avagners/algorithms_and_data_structures/blob/main/data_structures/graph/simple_graph.py#L110