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

 


 

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

62256. Самостоятельная работа на уроках русского языка как средство активизации познавательного интереса 34.33 KB
  В этом смысле особое значение приобретает проблема внедрения эффективных приемов самостоятельной работы в учебно-воспитательный процесс. Значит учителям необходимо учить детей самостоятельной работе.
62257. Самым лучшим уроком жизни бывает армия 20.01 KB
  Армия Что на самом деле дает этот важный урок в нашей жизни Вопрос на самом деле очень интересен и важен но в то же время кажущимся бесполезным для всех тех героев которые отслужили и вернулись домой. Армия Отнимает она на первый взгляд кажется больше чем дает. При всем моем огромном желании возможностях и начальных способностях я не умею воевать Задавим количеством А если Китай Что же на самом деле дает Армия Ты вглядываешься на жизнь совсем с другой стороны учишься жить в большом непростом коллективе когда каждый сам за...
62259. Счет победителей. Невыученные уроки войн, проигранных Россией 442.6 KB
  Прекратилась ли после этого информационная психологическая война Запада против России Сошла ли на нет русофобия Не прекратилась и не сошла. Вовторых восприятие России Западом как Чужого повидимому сохранится до тех пор пока Россия и Запад будут существовать в их нынешнем виде. Втретьих Запад в долгосрочной перспективе будет стремиться к максимальному ослаблению вплоть до раздробления России об этом откровенно говорили и говорят многие на Западе включая друга Билла Клинтона в октябре 1995 г. до такой степени при которой...
62263. КУЛЬТУРА КИЇВСЬКОЇ РУСІ ТА ГАЛИЦЬКО-ВОЛИНСЬКОЇ ДЕРЖАВИ 36.37 KB
  Матеріальна і духовна культура східних слов’ян. Культура Київської Русі та ГалицькоВолинського князівства IX – до сер. Основою культури Київської Русі була багатовікова самобутня культурна традиція східнослов’янських племен. Торгівля продуктами сільського господарства і ремесла спочатку мала характер обміну як всередині общини так і між племенами та землями Київської Русі.
62264. Окремі організаційні та функціональні складові судів в Україні 45.99 KB
  Члени Вищої кваліфікаційної комісії суддів України з числа суддів призначаються зїздом суддів України відкритим або таємним голосуванням. Зїзд суддів може обрати більше ніж шість суддів на випадок вибуття одного або кількох членів зі складу Комісії...