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

 


 

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

38752. СИЛА МОМЕНТА РУКОВОДСТВО ПО ДУХОВНОМУ ПРОСВЕТЛЕНИЮ 986.5 KB
  ДИКАРЛО ВВЕДЕНИЕ ПЕРВОПРИЧИНА ЭТОЙ КНИГИ ИСТИНА КОТОРАЯ ВНУТРИ ТЕБЯ ГЛАВА ПЕРВАЯ: ТЫ ЭТО НЕ ТВОЙ УМ САМОЕ БОЛЬШОЕ ПРЕПЯТСТВИЕ НА ПУТИ К ПРОСВЕТЛЕНИЮ ОСВОБОЖДЕНИЕ СЕБЯ ОТ УМА ПРОСВЕТЛЕНИЕ: ВОСХОЖДЕНИЕ НАД МЫШЛЕНИЕМ ЭМОЦИЯ: РЕАКЦИЯ ТЕЛА НА СОСТОЯНИЕ УМА ГЛАВА ВТОРАЯ: СОЗНАНИЕ: ПУТЬ ПРОЧЬ ОТ БОЛИ ПЕРЕСТАНЬ СОЗДАВАТЬ БОЛЬ В НАСТОЯЩЕМ БОЛЬ ИЗ ПРОШЛОГО: РАСТВОРЕНИЕ ТЕЛА БОЛИ ОТОЖДЕСТВЛЕНИЕ ЭГО С ТЕЛОМ БОЛИ ПЕРВОПРИЧИНА СТРАХА КАК ЭГО ИЩЕТ ЦЕЛОСТНОСТЬ ГЛАВА ТРЕТЬЯ: УГЛУБЛЯЯСЬ В МОМЕНТ СЕЙЧАС НЕ ИЩИ СЕБЯ В УМЕ ПОКОНЧИ С ИЛЛЮЗИЕЙ ВРЕМЕНИ НИЧТО НЕ...
38756. Осторожно! Вредные продукты 2.96 MB
  Когда начинаешь говорить о последствиях наступивших в результате употребления некоторых продуктов питания которых и продуктамито назвать затруднительно люди часто отмахиваются: Да ведь живем же. Вообще история развития диетологии напоминает политический детектив: различные виды продуктов то подвергались гонениям то возводились на пьедестал. Но ныне диетология остепенилась и окончательно стала тем чем собственно она всегда и была мощным средством одурачивания в руках недобросовестных производителей продуктов питания. Но На...
38757. Отношение человека к собственному телу 155.5 KB
  Что происходило в Ваших отношениях с другими вследствие этой травмы Как изменились Ваши отношения с коллегами друзьями родителями любимыми в ситуации травмы Какой у Вас появился опыт преодоления травмы Изменилось ли Ваше обращение с собственным телом Какой способ обхождения с травмами и болью Вы получили Изменились ли Ваши цели планы надежды в связи с травмой Обратитесь к своему телу или части тела которая была повреждена и причиняла страдания. Что бы Вы могли сказать этой части тела Мысленно осмотрите свое тело и...
38758. Ораторское искусство 411 KB
  Критерием качества усвоения той или иной темы является умение подмечать ошибки допускаемые в собственной речи и или в речах других людей глубоко и всесторонне анализировать язык и стиль публичных выступлений ярко образно аргументированно и убедительно излагать те или иные положения. Тема 1Предмет и функции ораторского искусства В научной литературе понятия риторика красноречие мастерство публичного выступления ораторское искусство нередко используются как родственные. Разделяет ее в частности отечественная философская...
38759. Экономика и управление на предприятии ОАО «Новосибирская макаронная фабрика» 126.5 KB
  Королева Отчет по преддипломной практике по предприятию ОАО Новосибирская макаронная фабрика по специальности Экономика и управление на предприятие Выполнила: Детюченко В. Данную работу можно разделить на несколько разделов: 1 Уставные характеристики организации 2 История предприятия ОАО Новосибирская макаронная фабрика 3 Приоритетные направления деятельности ОАО Новосибирская макаронная фабрика 4 Анализ структуры предприятия 5 Анализ системы закупок Заключение Список использованной литературы Содержание...
38760. Социальная психология и психотерапия 456.5 KB
  психика это системное качво мозга которое реализуется чз функциональные сисмы мозга кторые формируются у Ч в прцессе жизни и овладения им истор сложившихся форм Дти и опыта человва чз собственную активную Дть. Фрейд определял генезис психического как одну из важных детерминант полноценного функционирования взрослого человека Принцип субъекта предполагает рассматривать человека как автономную инициативную личность способную в определенных пределах изменять себя и окружающий мир. Формы взаимодействия чел в миром. Выполняя...