47318

Процедура построения бинарного дерева поиска и ее особенности

Доклад

Информатика, кибернетика и программирование

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

Русский

2014-03-31

20.71 KB

14 чел.

Процедура построения бинарного дерева поиска и ее особенности.

Деревом называется связный ориентированный граф, не содержащий циклов.

Для деревьев выделяются следующие понятия:

  1. родитель - вершина, из которых есть дуга в данную вершину
  2. потомок (сын, дочерняя вершина) - вершина, в которую ведёт дуга из данной вершины
  3. корень - самый верхний узел дерева, в который не входят никакие дуги. У корня нет родительской вершины.
  4. лист (листовой или терминальный узел) - вершина, не имеющий дочерних элементов, из которого не выходят никакие дуги.
  5. внутренний узел — любой узел дерева, имеющий и потомков и родителей, и таким образом, не являющийся ни корнем, ни листовым узлом.

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

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

Обход дерева это процедура перечисления вершин, при которой каждая вершина дерева проходится лишь один раз.

Задан p1, p2,…,pn массив признаков. В корень дерева, начав с уровня 0 или 1, помещают признак p1. Если следующий р2 массива признаков больше чем р1 , то р2 является правым непосредственным потомком вершины р1, в противоположном случае левым. Таким образом, непосредственные потомки располагаются на следующем уровне. По аналогичному принципу размещаются в дереве и остальные элементы массива признаков.

Построенное дерево носит название дерева бинарного поиска, что означает, что для любой вершины x этого дерева левая ветвь, исходящая из x в поддереве, корнем которого является вершина x , содержит элементы меньше x, а правая ветвь, исходящая из вершины x данного поддерева, содержит элементы больше, чем x.

Сложность построения бинарного дерева «в среднем» составляет около 1.39n*log2n сравнений, а в худшем случае O(n2). В среднем для поиска в двоичном дереве, содержащем n вершин потребуется около 1.39n*log2n сравнений, а в худшем случае n сравнений.

Пример : Значения элементов дерева: 20, 10, 35, 15, 17, 27, 24, 8, 30

 


 

А также другие работы, которые могут Вас заинтересовать

50296. МОДЕЛИРОВАНИЕ ЭЛЕКТРИЧЕСКИХ ФИЛЬТРОВ 631 KB
  Электрические фильтры широко применяются в измерительной и вычислительной технике в системах телеметрии и автоматического регулирования используются для устранения помех и наводок в электрических цепях и для коррекции амплитудночастотных характеристик АЧХ четырехполюсников. Фильтры классифицируются на четыре основных типа: 1. LCфильтры обладают рядом достоинств таких как высокая стабильность низкий уровень собственных шумов а также возможность создания фильтров с различными частотными характеристиками.
50297. ГРАФИЧЕСКОЕ ОФОРМЛЕНИЕ ТАБЛИЦ И ДИАГРАММ 123.5 KB
  Ее можно подключить либо командой Панели инструментов меню Вид либо кнопкой Рисование на стандартной панели инструментов. Для размещения в рабочей книге графических объектов можно применить команду Рисунок из меню Вставка. Команда Объект меню Вставка позволяет производить обмен данными между приложениями. Команда Вставить меню Правка позволяет разместить созданный рисунок скопированный в буфер обмена для заполнения предварительно отмеченного ряда данных.
50298. Создание и редактирование баз данных средствами MS Excel и MS Access 726 KB
  Создание базы данных БД. Система управления базами данных CCESS EXCEL позволяет работать с базами данных.
50299. Кинематика материальной точки 99.5 KB
  Найти модуль скорости точки в середине интервала наблюдения и углы составляемые вектором скорости с осями координат в этот момент. Задание 3 Найти ускорение точки в тот же момент времени и углы составляемые вектором ускорения с осями координат. Задание 4 Найти тангенциальное и нормальное ускорение точки в тот же момент времени....
50302. Оптика. Атомная и ядерная физика: Учебное пособие 547.5 KB
  Точечный источник света расположен в воде на глубине 1 м. Показатель преломления воды равен 1,33. Каков радиус круга на поверхности воды, в пределах которого возможен выход лучей в воздух?
50303. Построение плоских фигур 428 KB
  Рассмотрим достаточно подробно алгоритм построения графика функциональной зависимости в заданном интервале изменения аргумента функции. Первый этап выполнения такого задания должен заключаться в исследовании данной функции в результате которого следует выяснить: 1 имеет ли функция в заданном интервале особенности не обращается ли она в бесконечнось при всех ли значения аргумента она определена; 2 пределы изменения область что необходимо для оценки коэффициентов преобразований. После этого можно приступать непосредственно к...