Структуры данных: заметки
- Двухсвязный список может быть выгоднее массива: любые операции вставки и удаления занимают в нём время О(1). Но, в зависимости от данных, можно обойтись односвязным списком или просто массивом.
- Поиск в связанном списке равен О(n), если не прибегать к дополнительному индексированию и другим трюкам.
- Стек полезен, например, в линтинге. Каждый раз, когда создается открывающая скобка в коде, в стек редактора заносится единица, когда создается закрывающая - удаляется. Если на конец кода стек не пуст - то допущена ошибка.
- Реализовать стек можно с помощью массива или односвязного списка. Я делал и обычной строкой :)
- В деревьях есть понятие "листового узла" - это узлы, не имеющие потомков.
- Закономерность в деревьях: ребер в дереве всегда равно количеству узлов минус 1. Так получается, потому что к любому из узлов (кроме корня) ведет один указатель.
- Глубина узла дерева - это количество ребер, которое нужно пройти, чтобы добраться до узла. Например, у корня глубина - 0: на него ничего не указывает.
- Высота дерева - это количество ребер, которое нужно пройти от самого глубокого узла до корня.
- Свойства двоичного дерева:
1. Максимальное количество узлов на уровне высоты: 2^уровень.
2. Максимальное количество узлов дерева: (2^высота дерева)-1.
3. Высота дерева по количеству узлов: log2(n+1)-1
- Деревья бывают сбалансированными и несбалансированными. Сбалансированные деревья максимально заполнены. Это важно, потому что высота дерева прямо влияет на количество операций поиска по нему. Максимальная заполненность - это состояние, когда разница между правым и левым поддеревьями не меньше константного числа (обычно, 1).
- Хранить деревья в памяти можно по-разному:
1. Обычное дерево можно хранить в связанном списке.
2. Complete binary tree - дерево, в котором все узлы, кроме листовых, заполнены, и дерево расширяется слева - допустимо хранить в массиве.
#структуры_данных
- Двухсвязный список может быть выгоднее массива: любые операции вставки и удаления занимают в нём время О(1). Но, в зависимости от данных, можно обойтись односвязным списком или просто массивом.
- Поиск в связанном списке равен О(n), если не прибегать к дополнительному индексированию и другим трюкам.
- Стек полезен, например, в линтинге. Каждый раз, когда создается открывающая скобка в коде, в стек редактора заносится единица, когда создается закрывающая - удаляется. Если на конец кода стек не пуст - то допущена ошибка.
- Реализовать стек можно с помощью массива или односвязного списка. Я делал и обычной строкой :)
- В деревьях есть понятие "листового узла" - это узлы, не имеющие потомков.
- Закономерность в деревьях: ребер в дереве всегда равно количеству узлов минус 1. Так получается, потому что к любому из узлов (кроме корня) ведет один указатель.
- Глубина узла дерева - это количество ребер, которое нужно пройти, чтобы добраться до узла. Например, у корня глубина - 0: на него ничего не указывает.
- Высота дерева - это количество ребер, которое нужно пройти от самого глубокого узла до корня.
- Свойства двоичного дерева:
1. Максимальное количество узлов на уровне высоты: 2^уровень.
2. Максимальное количество узлов дерева: (2^высота дерева)-1.
3. Высота дерева по количеству узлов: log2(n+1)-1
- Деревья бывают сбалансированными и несбалансированными. Сбалансированные деревья максимально заполнены. Это важно, потому что высота дерева прямо влияет на количество операций поиска по нему. Максимальная заполненность - это состояние, когда разница между правым и левым поддеревьями не меньше константного числа (обычно, 1).
- Хранить деревья в памяти можно по-разному:
1. Обычное дерево можно хранить в связанном списке.
2. Complete binary tree - дерево, в котором все узлы, кроме листовых, заполнены, и дерево расширяется слева - допустимо хранить в массиве.
#структуры_данных