Структуры и алгоритмы

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

Для начала, предлагаю рассмотреть разновидности структур данных (еще их называют ассоциативные контейнеры):

Структуры и алгоритмы

Бинарное дерево

Как видите, почти все структуры используют древовидную структуру, поэтому стоит рассмотреть для начала самое обычное бинарное дерево.

Очень важно: справа на изображении показан стек (неассоциативный массив), это реальное представление дерева (именно так линейно и хранятся значения).

Структуры и алгоритмы

Обратите внимание на H - высота дерева.

Теперь познакомимся с формулами, которые показывают, как быстро работать с бинарным деревом. Заметим, что:

  • на каждом ниже лежащем уровне, элементов вдвое больше
  • номер потомка увеличивается вдвое по сравнению с его родителем.

Найти левый дочерний элемент можно по формуле: 2*i+1

Например рассмотрим элемент 1 (со значением 5): 2*1+1=3 (значение 2)

Найти правый дочерний элемент можно по формуле: 2*i+2

Например рассмотрим элемент 1 (со значением 5): 2*1+2=4 (значение 4)

Найти номер родителя можно по формуле: (i-1)%2

Например рассмотрим элемент 5 (со значением 4): (5-1)%2 =2 (значение 9)

Найти приблизительное кол-во элементов в дереве можно с помощью формулы: N ≈ 2H

Найти приблизительную высоту дерева можно с помощью формулы: H ≈ log N

Например, для выше указанного дерева H ≈ log 8 = √8 ≈ 2.8 и округляя получаем 3, проверим: 23 = 8

Время требуемое, чтобы создать дерево ≈ N log N

Забегая вперед хочется отметить, что кроме однопутевого бинарного дерева бывают еще многопутевые деревья (в которых вершины состоят из списка значений), реальный пример:

Структуры и алгоритмы

Вот как выполняется поиск в таком дереве (например поиск значения 57):

Структуры и алгоритмы

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

Пожалуй, это все, что Вас могут спросить на собеседовании, но иногда еще спрашивают про связанный список (советю почитать 1 и 2 ).

А для более любознательных, я припас статью о всех выше перечисленных структурах (копия) и стоит заметить, что SSTable это Кортеж, но не фиксированной длинны.

Источник: 1 - 2 - 3 - 4

Оцени публикацию:
  • 0,0
Оценили: 0
Теги : почему, тэг

Предложения и пожелания:

 

youtube.com/watch?v=7hFivbgIEqk

При полном или частичном использовании материалов данного сайта, ссылка на сайт "yapro.ru" обязательна как на источник информации.
Автоматический импорт материалов и информации с сайта запрещен.
Copyrights © 2007 - 2019 YaPro.Ru

Лебеденко Николай Николаевич
Ошибка в тексте? Выделите её мышкой и нажмите: Ctrl + Enter