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

 


 

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

76362. Задачи визуального и измерительного контроля (ВИК) 369.73 KB
  Способность правильно различать основные цвета называется нормальной трихромазией. Минимальный ахроматический интервал у красного цвета что несмотря на плохую чувствительность глаза в той области является одной из причин использования красного цвета для сигналов опасности или запрета. Цветоведение колористика наука о цвете включающая знания о физической природе цвета и его основных характеристиках ахроматических и хроматических цветах дополнительных и контрастных цветах колорите и цветовой гармонии.Все цвета по своим физическим...
76363. Оптические средства, измерительный контроль 831 KB
  Основным параметром любого оптического прибора является увеличение кратность Г отношение углового размера изображения малого предмета видимого через наблюдательный прибор к угловому размеру самого предмета видимого невооруженным глазом. Угол под которым глаз наблюдателя видит изображение предмета образованное оптической системой наблюдательного прибора;α2 угол под которым предмет виден невооруженным глазом. Зная...
76364. Капиллярная дефектоскопия 424.54 KB
  Физическая сущность ЦД контроля: пенетрация краевой угол смачивания капиллярные явления и уравнение Лапласа. Технологическая схема ЦД контроля чувствительность метода. Дефектоскопические материалы для ЦД контроля Метод контроля основан на капиллярном проникновении индикаторных жидкостей пенетрантов в полости поверхностных и сквозных несплошностей материала объектов контроля и регистрации образующихся индикаторных следов визуальным способом или с помощью преобразователя. Капиллярный НК предназначен для обнаружения невидимых или...
76365. Магнитная дефектоскопия 301.42 KB
  По способу получения первичной информации различают следующие методы магнитного контроля: магнитопорошковый МП основанный на регистрации магнитных полей рассеяния над дефектами с использованием в качествеиндикатора ферромагнитного порошка или магнитной суспензии; магнитографический МГ основанный на регистрации магнитных полей рассеяния с использованием в качестве индикатора ферромагнитной пленки; феррозондовый ФЗ основанный на измерении напряженности магнитного поля феррозондами; эффекта Холла ЭХ основанный на...
76366. МПД-контроль 300.19 KB
  Технологическая схема МПД контроля. Дефектоскопические средства: приборы средства контроля материалы. Размагничивание изделий после контроля. Паспортизация результатов МПДконтроля.
76367. Акустические методы НК 277.5 KB
  Природа и свойства ультразвуковых колебаний. Распространение упругих колебаний в сплошной среде представляет собой волнообразный процесс. Диапазоны упругих колебаний в материальных средах Физическая природа упругих колебаний одинакова во всем диапазоне частот. Свойства упругих колебаний...
76368. Базисная теория таможенного тарифа 82.5 KB
  Базисная теория таможенного тарифа Несмотря на то что свободная торговля приводит к возрастанию экономического благосостояния всех стран как экспортеров так и импортеров на практике международная торговля практически нигде и никогда не развивалась действительно свободно без вмешательства государства. Инструменты используемые государством для регулирования международной торговли можно разделить на тарифные основанные на использовании таможенного тарифа и нетарифные квоты лицензии субсидии демпинг и т. При введении тарифа...
76369. Нетарифные методы торговой политики 90 KB
  Если правительство хочет ограничить объем импорта и устанавливает квоту размером Q то общее предложение зерна на внутреннем рынке с учетом импорта может быть представлено в виде кривой Sd Q. Таким образом в результате введения импортной квоты возникают чистые потери для страны в целом равные области b с то есть результаты воздействия квоты и тарифа на уровень благосостояние идентичны конечно это справедливо если объем лицензированного импорта меньше чем спрос на импорт на внутреннем рынке. Почему же в этом случае государство часто...
76370. Международная экономическая интеграция. Формы (уровни) международной экономической интеграции 260.5 KB
  Борьба за упрочение своего экономического положения побуждает страны к образованию различных интеграционных объединений. Партнеры по объединению получают определенные преференции по сравнению с другими странами но платят за это ответными обязательствами по отношению к партнерам. Международная экономическая интеграция это процесс хозяйственнополитического объединения стран на основе глубоких устойчивых взаимосвязей и разделения труда между национальными хозяйствами. На микроуровне этот процесс идет через взаимодействие отдельных фирм...