47318

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

Доклад

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

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

Русский

2014-03-31

20.71 KB

12 чел.

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

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

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

  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

 


 

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

84004. РІД IМЕННИКIВ. ЗМІНЮВАННЯ IМЕННИКIВ ЗА ЧИСЛАМИ 96.5 KB
  Мета: - перевірити знання учнів про іменник, як частину мови, закріпити знання дітей про змінювання іменників за числами, повторити з учнями рід іменників, розвивати вміння правильно ставити рід у словах, повторити антоніми, збагачувати активний словник школярів, продовжувати роботу...
84005. Складання твору за картиною «Зима - чарівниця» 114 KB
  Мета: Ознайомити із темою уроку. Формувати вміння добирати найбільш влучні Прикметники під час складання твору. Розвивати зв’язне мовлення мислення, спостережливість. Удосконалювати чітко і повним реченням відповідати на запитання. Збагачувати словниковий запас. Виховувати любов до природи.
84006. Розвиток зв’язного мовлення. Твір «Моє місто» 133.5 KB
  Мета. Хід уроку Організація класу Актуалізація опорних знань Слово вчителя Діти послухайте вірш Моє місто Умань стародавнє. Яке місто названо у вірші З якої букви потрібно писати це слово На каліграфічній хвилинці повторимо правила написання букв У у букво сполучення із даними буквами.
84007. Навчальний переказ у формі прес-конференції 153.5 KB
  Мета: Вчити дітей передавати послідовно зміст зв’язного тексту. Розширити і збагатити знання учнів про сову, осмислити значення цієї пташки. Розвивати уяву, фантазію, спостережливість. Виховувати бережне ставлення до природи. Засобом рольової гри та нестандартним підходом...
84008. Общая характеристика эволюции управленческой мысли 19.83 KB
  Первобытно общинный рабовладельческий феодальный периоды. Индустриальный период. Период систематизации научно практических знаний. период связан с бурным развитием промышленности научные открытия и изобретения на фоне буржуазных революций.
84009. Школа научного управления и ее современные последователи 17.67 KB
  В основе учения этой школы лежат следующие принципы: использование научного анализа для определения оптимальных способов выполнения задач; отбор работников наиболее подходящих для выполнения определенных задач и их обучение; обеспечение работников необходимыми ресурсами; систематическое и правильное использование материального стимулирования для повышения производительности труда; выделение планирования в функцию управления; становление менеджмента как самостоятельной науки; формирование функций менеджмента. Следовательно школа научного...
84010. Теоретические воззрения Тейлора, «тейлоризм» 22.05 KB
  Тейлором 1856 1915 который возглавил движение научного управления. Он заинтересовался не эффективностью человека а эффективностью деятельности организации что и положило начало развитию школы научного управления. Благодаря разработке концепции научного управления менеджмент был признан самостоятельной областью научных исследований. В своих работах Управление циклом 1903 и Принципы научного менеджмента 1911 Ф.
84011. Теоретические взгляды Г.Л. Ганнта 23.47 KB
  Ганнт является первооткрывателем в области оперативного управления и календарного планирования деятельности предприятий; он разработал целую систему плановых графиков графики Ганнта позволивших благодаря его высокой информированности осуществлять контроль за запланированным и составлять календарные планы на будущее. К числу организационных изобретений Ганнта следует отнести его систему заработной платы с элементами повременной и сдельной форм оплаты. Многие идеи Ганнта получили признание во всем мире и применяются в наши дни например...
84012. Теоретическое наследие Ф. и Л. Гилбрет 24.28 KB
  Солидный вклад в научную теорию управления внесли супруги Фрэнк и ЛилианГилбрет которые в 20е гг. нашего столетия были активными сторонниками научного управления. Это оказало большое влияние на развитие школы научного управления. концентрация производства и монополизация капитала привели к сосредоточению на крупных и мелких предприятиях работников различных специальностей что вызвало необходимость установления функционального кадрового управления.