Тест по BigData. Кривашеев Владислав Анатольевич Группа вбио302 Преподаватель Ожередов Вадим Андреевич Москва 2021 Дана задача
 Скачать 16.54 Kb.
|
|
НЕГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ ЧАСТНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ МОСКОВСКИЙ ФИНАНСОВО-ПРОМЫШЛЕННЫЙ УНИВЕРСИТЕТ «СИНЕРГИЯ» Отчёт пересдачи по предмету Технологии Больших данных (Big Data) Кривашеев Владислав Анатольевич Группа ВБИо-302 Преподаватель: Ожередов Вадим Андреевич Москва – 2021 Дана задача: Сколько узлов будет содержать сбалансированное бинарное дерево поиска глубиной 10? Решение: Каждый уровень (иногда кроме последнего) сбалансированного бинарного дерева поиска можно описать как 2^n узлов. Тогда сложив нужное количество 2^n (которое соответствует количеству уровней, то есть глубине), можно получить число, отображающее узлы в дереве. Так как глубина нашего дерева равна 10, то наше число n будет рядом чисел от 0 до 9. Решение можно выразить так:  Однако в данном дереве поиска на последних уровнях могут быть не равные количества узлов. Для того чтобы установить пределы суммы узлов дерева поиска достаточно от последнего уровня n^9=512 отнять 511 (чтобы соблюдалось условие глубины). Тогда количество узлов(1023-511=512) может лежать в пределах от 512 до 1023. Ответ:1023 (или от 512 до 1023) |