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

 


 

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

1059. Методика аудиторской проверки расчетов с бюджетом (на примере НОУ СПО Учебный центр, Омск 443 KB
  Процесс планирования аудиторской проверки учета расчетов с бюджетом по налогам и сборам. Экономическая характеристика объекта исследования. Организация бухгалтерского и налогового учета расчетов с бюджетом. Аудиторская проверка учета расчетов с бюджетом по единому социальному налогу в НОУ СПО Учебный центр.
1060. Обработка статистической информации о надежности линии привода 3-го формирующего ролика 1-й моталки 265 KB
  Упорядочение исходной выборки наработок до отказа. Проверка статистической гипотезы о соответствии экспоненциальному распределению. Проверка статистической гипотезы о соответствии нормальному или логарифмически нормальному распределению. Графическое оценивание параметров распределений.
1061. Расчет и выбор конструкции кожухотрубного теплообменного аппарата 267 KB
  Тепловой расчет и выбор конструкции теплообменного аппарата. Устройство, передающее теплоту от одного теплоносителя к другому. Проверочный тепловой расчет теплообменного аппарата. Гидравлический расчет теплообменного аппарата. Расчет падения давления теплоносителей в трубном и межтрубном пространстве ТА.
1062. Учет финансовой отчетности в процессе управления предприятием ООО Стиль 411 KB
  Финансовая отчетность и ее роль в информационном обеспечении управления предприятием. Методы анализа устойчивости финансового состояния в процессе управления предприятием. Составление и анализ финансовой отчетности в процессе управления предприятием (на материалах ООО Стиль). Анализ устойчивости финансового состояния по данным финансовой отчетности.
1063. Створення таблиць і форм мовою html 528 KB
  Створення форм і таблиць, вивчення синтаксису і тегів цих елементів, набуття навиків у використанні цих елементів при розробці власних сторінок.
1064. Теоретичні засади державного пенсійного страхування та перспективи його розвитку 569 KB
  Теоретичні засади дослідження системи пенсійного страхування в Україні. Особливості розвитку системи державного пенсійного страхування в країнах світу. Принципи загальнодержавного пенсійного страхування в Україні. Правова основа державного пенсійного страхування в Україні. Тенденції розвитку державного пенсійного страхування в Україні.
1065. Проектування індивідуального житлового будинку в м. Донецьк 441.5 KB
  Проектований двоповерховий житловий будинок має в плані не правильну конфігурацію. Будинок по конструктивній схемі відноситься до будинків з поперечним і повздовжнім розміщенням несучих стін і спиранням плит перекриття по двом сторонам. Зовнішні стіни в будинку виконані з легкої кладки товщиною 510 мм.
1066. Фотодатчики, их классификации, режимы работы и применение в биоинженерной технике 587 KB
  Основные понятия фотоэлектрических приборов. Основные характеристики фотоэлектрических преобразователей. Режимы работы датчиков. Области применения медико-биологической практике. Дополнительные возможности датчиков.
1067. Культура России второй половины ХІХ - первой половины ХХ столетия 550 KB
  Факторы развития культуры в России. Крестьянская реформа 19 февраля 1861 года. Мировой революционный процесс и передовая западноевропейская общественная мысль. Метод критического реализма. Мотив слияния с природой, погружения в ее тайны и красоту.