3.8. Поиск в дереве.

Проблема поиска в больших массивах информации – одна из важнейших в информатике.

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

Видим, что гораздо быстрее и эффективнее искать объекты, расположенные в виде бинарного дерева. Идя от корня мы на каждом шаге должны определить, влево или вправо надо двигаться. Например, можно наложить на вершины префиксный код (нули и единицы).

Чтобы сравнить длину последовательно поиска с поиском в бинарном дереве, выясним явязь количества вершин дерева с его глубиной. (Это и есть длина поиска). Для этого рассмотрим идеальное бинарное дерево, в котором каждая вершина (кроме висячих) имеет ровно 32 потомка – левый и правый.

Тогда вершин будет n=1+2+2²+2³+…+2^k

S=2^k+1=1

n=2^k+1-1

2^k+1=n+1

K+1=log₂(n+1)

K=log₂(n+1)-1

Пример. Пусти в идеальном бинарном ордереве миллион вершин. Какова длина поиска в таком дереве.

K=log₂10000000-1= 6log₂10-1=6*32=1+18,2=19 уровней.

Вопросы к экзамену по теме 3.

20. Что такое матрица смежности орграфа и какими свойством обладает матрица смежности неориентированного графа?

21. Как строиться код Харари.

22. Что называется деревом, ордеревом и как они связаны между собой?

23. Как строится префиксный код бинарного дерева?

24. Как строится код Прюфера

25. Какие 3 способа обхода бинарного дерева вы знаете (с примерами более 10 вершин)

26. Как связаны число вершин идеального бинарного дерева и его глубина?

27. Что называется атомом, списком и как связаны деревья со списком?

Задачи могут быть к вопросам 21-25, 27