Please enable JavaScript.

Coggle requires JavaScript to display documents.

Структуры данных - Coggle Diagram

- - - - Двоичные красно-черные
      - AVL
        
        2-3
        
        2-3-4
    - - Снижается частота ребалансировки
      - Снижается скорость поиска
  - - - Открытая адресация
        
        Линейное и квадратичное смещение
        
        Двойное хэширование: смещение, как другая хэш-функция от ключа
        
        Размер массива должен быть простым числом, чтобы снизить вероятность повторных коллизий при проходе по кругу
        
        Резкая потеря эффективности при большом коэффициенте заполнения
      - Метод цепочек
        
        Для каждой ячейки при необходимости создается связанный список пар [ключ, значение]
    - - Отображает большое множество ключей на маленькое множество числовых индексов
      - Изменение размера таблицы требует пересчета всех хэшей
      - Обычно использует операцию mod
  - - - Направленный
      - Взвешенный
    - - Вершины
      - Ребра (связи)
    - - Ациклический
      - Связный (нет островов)
      - Дерево - связный ациклический граф
    - - Матрица смежности
        
        Содержит избыточную информацию для ненаправленных графов
      - Список смежных вершин в каждой вершине
      - P.S. Разные представления эффективны для разных задач
- - - - ASCII
        
        Занимает диапазон 0-127
        
        Используется для обозначения символов в qwerty-клавиатурах
        
        Расширяется большинством других кодировок
      - UTF-8
        
        1-6 байт на символ (хватает 4)
        
        Основана на Unicode
        
        Первые биты байта указывают длину символа или маркируют "вагон"
  - - - Включает в себя почти все возможные символы
      - Промежуточное представления при переводе между кодировками
- - - - Двухсторонний
        
        Позволяет быстро добавлять элементы в конец
        
        Дополнительно хранится ссылка на последний элемент
      - Двухсвязный
        
        Перемещение по элементам в обе стороны
- - - - Апроксимация рядом отрицательных степеней двойки
        (1/2, 1/4, 1/8 и т.д.)
      - Накопленная погрешность может давать неожиданные результаты
    - - Знак числа
      - Порядок (обычно степень 2)
      - Мантиса
- - - - Итерация по возрастанию ключей
      - Потребление памяти только по мере роста
    - - Очень быстрый поиск (при отсутствии коллизий - константный, далее зависит от коэффициента заполнения)
      - Долгое расширение
      - Резервирование памяти