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

 


 

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

65493. ВЗАЄМОВІДНОСИНИ УКРАЇНСЬКОЇ НАРОДНОЇ РЕСПУБЛІКИ Й ЗАХІДНО-УКРАЇНСЬКОЇ НАРОДНОЇ РЕСПУБЛІКИ (ЛИСТОПАД 1918 – КВІТЕНЬ 1920 рр.) 173.5 KB
  Предметом дослідження є основні напрямки та форми двосторонніх відносин УНР і ЗУНР у політичній економічній і військовій сферах. Нижня межа обумовлена утворенням ЗУНР і початком протигетьманського повстання під проводом Директорії в Наддніпрянській Україні.
65494. Тепловий захист короткозамкненого ротора асинхронного електродвигуна на основі контролю параметрів поточного режиму 945 KB
  Основним типом машин змінного струму, що вживаються в електроприводі механізмів власних потреб електростанцій, а також механізмів промислових підприємств, є асинхронні електродвигуни (АЕД) з короткозамкненим ротором (КЗР).
65495. Церковно-адміністративна та громадсько-політична діяльність митрополита Антонія (Храповицького) в Харківській єпархії (травень 1914 – червень 1918 рр.) 201.5 KB
  Діяльність владики Антонія на посаді архієпископа а потім митрополита Харківського та Охтирського припала на буремні роки Першої світової війни Української національнодемократичної революції та громадянської війни.
65496. Закономірності фазових і структурних перетворень в сплавах на основі системи ti-si при гартуванні та відпуску 11.77 MB
  Розробка новітніх сплавів передусім ґрунтується на досягненнях фізичного матеріалознавства в основному на даних досліджень фазових і структурних перетворень та фізики міцності. Водночас можливості таких методів структурної інженерії як легування в області твердих розчинів пластична деформація і термічна...
65497. ФУНКЦІОНАЛЬНА ПІДГОТОВКА ЮНИХ ФУТБОЛІСТІВ РІЗНИХ ІГРОВИХ АМПЛУА НА ЕТАПІ СПЕЦІАЛІЗОВАНОЇ БАЗОВОЇ ПІДГОТОВКИ 222.5 KB
  Основним завданням підготовки футболістів у змагальному періоді є збереження їх рухового й функціонального потенціалу при постійному вдосконаленні індивідуального та командного рівня технікотактичної майстерності а також реалізація можливостей гравців у змаганнях...
65498. УДОСКОНАЛЕННЯ МЕТОДІВ РОЗРАХУНКУ ЕКСПЛУАТАЦІЙНИХ НАВАНТАЖЕНЬ ТА ЗНОСІВ КОЛІНЧАТИХ ВАЛІВ ЛОКОМОТИВНИХ ЕНЕРГЕТИЧНИХ УСТАНОВОК 718 KB
  Така ситуація визначає необхідність розгортання науково-дослідних і дослідно-конструкторських робіт спрямованих на забезпечення надійності та довговічності в експлуатації основних агрегатів тепловозів головне місце серед яких належить локомотивним енергетичним установкам ЛЕУ.
65499. ПОЛІПШЕННЯ ВОГНЕЗАХИСНИХ ВЛАСТИВОСТЕЙ ЦЕЛЮЛОЗНИХ ТЕКСТИЛЬНИХ МАТЕРІАЛІВ З ВИКОРИСТАННЯМ РЕАКЦІЙНО ЗДАТНИХ АНТИПІРЕНІВ 605 KB
  За отриманими рівняннями регресії для нормованих значень факторів – концентрація МПФА і концентрація аддукт ДА – були побудовані поверхні відгуку рис. Установлено що при введенні 15 МПФА і 10 аддукта ДА від маси тканини зберігаються міцні характеристики тканин...
65500. РОЛЬ КИСНЮ ТА СІРКИ ВУГІЛЛЯ В ПРОЦЕСАХ ЙОГО ТЕРМІЧНОЇ ДЕСТРУКЦІЇ 280.5 KB
  Наявність атомів оксигену сульфуру й у меншій мірі нітрогену в органічній масі вугілля ОМВ визначає ті властивості які відрізняють вугілля від інших вуглецевих матеріалів. Вугілля України Донецький Дніпровський басейни належить до найбільш сірчистого.