Бинарные деревья

  • 02 окт. 2012 г.
  • 1568 Слова
Содержание

Введение…………………………………………………………………………………...3
1. Двоичные деревья поиска…………………………………………………………….4
2. Сбалансированные двоичные деревья………………………………………………...7
3. Дерево оптимального поиска………………………………………………………….8
4. Бинарное дерево цифрового поиска………………………………………...............10
Заключение……………………………………………………………………………….11
Список литературы………………………………………………………………………12Введение

Понятия, связанные с деревьями, широко известны и понятны. Тем не менее,
существует несколько возможных определений дерева. С точки зрения теории графов, деревом часто называют неориентированный граф с выделенной вершиной (корнем), который не содержит циклов. Нас будут интересовать не произвольные графы, а только ориентированные деревья, причем с точки зренияпрограммистов. Поэтому мы используем следующее рекурсивное определение: дерево R с базовым типом T – это либо (a) пустое дерево (не содержащее ни одной вершины), либо (b) некоторая вершина типа T (корень дерева) с конечным (возможно, нулевым) числом связанных с ней деревьев с базовым типом T (эти деревья называются поддеревьями дерева R).
Цель данной курсовой работы заключается в том, чтобы изучитьпреимущества использования бинарных деревьев как одного из метода поиска в основной памяти.
Исходя из заданной цели, были поставлены следующие задачи:
1. Изучить процесс организации поиска в бинарном дереве.
2. Ознакомиться с возможностями использования сбалансированных деревьев.
3. Иметь представление о деревьях оптимального поиска.
4. Рассмотреть бинарное дерево цифрового поиска.Цель и задачи обусловили структуру курсовой работы. Она состоит из содержания, введения, четырех разделов, заключения, списка литературы.
Организация данных с помощью бинарных деревьев часто позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов,присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени. Максимальное число шагов при поиске по дереву равно высоте данного дерева, т.е. количеству уровней в иерархической структуре дерева.


1. Двоичное дерево поиска

Бинарное (двоичное) дерево (binary tree) – это упорядоченное дерево, каждая вершина которого имеет не более двухподдеревьев. Для каждого узла выполняется правило: в левом поддереве содержатся только ключи, имеющие значения, меньшие, чем значение данного узла, а в правом поддереве содержатся только ключи, имеющие значения, большие, чем значение данного узла.
Вершину дерева называют его корнем, а узлы дерева, которые не имеют потомков – листом. Высота дерева – это длина наидлиннейшего из путей от корня клистьям (рис. 1.1).
[pic]
Рис. 1.1 Двоичное дерево поиска, в котором ключами являются латинские символы, упорядоченные по алфавиту.

Для организации поиска в основной памяти особое значение имеют упорядоченные двоичные (бинарные) деревья (рис. 1.2).
[pic]
Рис. 2.1.2

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

При использовании в целях поиска элементов данных по значению уникального ключа применяются двоичные деревья поиска, обладающие тем свойством, что для любой вершины дерева значение ее ключа больше значения ключа любой вершины ее левого поддерева и больше значения ключа любой вершиныправого поддерева (рис. 1.3). Для поиска заданного ключа в дереве поиска достаточно пройти по одному пути от корня до (возможно, листовой) вершины (рис. 1.4).
[pic] Рис.1.3
[pic] Рис. 1.4




Базовый интерфейс двоичного дерева поиска состоит из трех операций:
1) FIND (K) – поиск узла, в котором хранится...
tracking img