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

 


 

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

733. Анализ деятельности фирмы на рынке и теория коррупции 127 KB
  Рынок и закономерности его функционирования. Крупный бизнес и слабое государство. Конкурентные рынки и выбор фирм. Планирование деятельности и доходов фирмы. Проблемы российских предпринимателей при ведении ими бизнеса. Динамика коррупции в России.
734. Определение коэффициента вязкости жидкости по методу падающего шарика 57 KB
  Основная расчетная формула для вычисления коэффициента вязкости жидкости. Средние значения диаметра шарика и время его падения. Средства измерений и их характеристики. Расчет границы абсолютной погрешности измерения плотности материала шариков.
735. Многофункциональный высотный жилой дом 96 KB
  Решение генплана и благоустройство территории. Конструктивное решение объекта. Инженерно-техническое решение и оборудование. Мероприятия по решению вопросов энергосбережения и экологии. Площади для размещения инженерного оборудования.
736. Сетевые методы планирования и управления 530 KB
  Составление индивидуального перечня работ и построение СГ. Расчет сметной стоимости работ. Расчет сметной стоимости работ оптимизированного СГ. Построение графиков Время – затраты.
737. Возникновение и протекание гипертонической болезни 143 KB
  Этиология, патогенез и лечение гипертонической болезни. Стадия начальных органических изменений. Стресс и хроническое психоэмоциональное напряжение. Классификация и клинические проявления. Профилактика гипертонической болезни
738. Инструкции обработки цепочек на языке ассемблер 89 KB
  Изучить команды обработки цепочек процессора i8086. Зашифровать строку по таблице. Таблица считается известной.
739. Влияние налогов на развитие малого предпринимательства 129.5 KB
  Сущность малого бизнеса и его роль в экономике страны. Упрощенная система налогообложения. Система налогообложения в виде единого налога на вмененный доход. Роль налоговой системы на развитие малого предпринимательства в России.
740. Процесс создание и отладки программы на языке ассемблера 88 KB
  Знакомство с методами создания и отладки программ, написанных на языке ассемблера. Создание программы, на языке ассемблера выполняющей арифметическую операцию и ввод/вывод с консоли. Трансляция, компоновка, трассировка программы.
741. Исследование параметров и характеристик двигателя постоянного тока с независимым возбуждением 337.5 KB
  Построение статических характеристик двигателя постоянного тока. Исследование механических характеристик двигателя постоянного тока с независимым возбуждением. Методика расчета параметров модели двигателя. Результаты исследования искусственной механической характеристики при пониженном напряжении на обмотке якоря. Частотная характеристика двигателя постоянного тока с независимым возбуждением.