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

 


 

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

59731. Державні символи України 53 KB
  Мета: 1 закцентувати увагу на державних символах; 2 повторити документи які узаконюють державність; 3 показати відображення питань української символіки в літературі та мистецтві; 4 виховання патріотичних почуттів у підростаючого покоління.
59732. Кривенька качечка 40.5 KB
  Нічого я ще не знаю, бабуся миленька. Давай підемо по грибки, ти моя старенька. Бери козуб і корзину, я візьму відерце, Наберемо ще води ми з чистого джерельця, Назбираємо грибочків, ягідок нарвемо, Зваримо юшки із грибами, млинців напечемо.
59733. Свято весни. Методична розробка уроку 40.5 KB
  Здрастуй день і здрастуй сонце ясне Промені червоні вище підіймай Хай земля всміхається прекрасна Виграє веселкою весна. В сиву давнину пора року весна відзначалась великою кількістю розмаїтих обрядів ігор пісень.
59734. Інсценівка для дітей. На лісовій галявині 40.5 KB
  На сцені розкладені вирізані з паперу квіти, на кожній квіточці — цукерка. Це галявина. На галявину вибігає дівчинка, одягнена в одяг жовто-брунатного кольору, на голові великий жовтий бант. Це — Бджілка. В руці кошик. Вона побачила квіти і (почала збирати цукерки-нектар).
59735. Олександр Олесь «Печенізька облога Києва» 34.5 KB
  Олександр Олесь Печенізька облога Києва. Виразне читання поезії Олександра Олеся Печенізька облога Києва. Розкажіть про становище Києва в облозі.
59736. Разработка приложения, поддерживающего диагностику электрических линий и устройств для легковых автомобилей 8.07 MB
  При современном развитии техники и технологии идет непрерывный процесс совершенствования как самой продукции, так и средств ее производства. Появляются новые системы САПР и модернизируются старые, максимально упрощая путь от идеи до готового изделия
59737. Сценарій до свята Святого Миколая 46 KB
  Ангел: Як же Миколай святий Знайде стежку до дітей Вітер вбігає з метлою: Не турбуйтесь слуги Божі Вітер радо вам поможе. Виходять з санчатами Яринка та Тарасик Яринка: Чом Тарасе не видати Ні одного агеляти Ні дзвіночків не чувати Може Миколай Святий...
59738. Свято Миколая – вірші, оповідання, пісні, народні звичаї та прикмети 45.5 KB
  Листопад Біла молитва братика Хто він той святий Миколай гість з неба на которого так чекають діти Легенда опівадає що у дитинстві а ріс Миколай у заможній родині горнувся хлопчик до бідних нужденних скривджених голодних та калік. Святий Миколай лужком бережком.
59739. Новела М.Хвильового Я (Романтика) 46 KB
  Дослідити образну систему новели, проблематику, стилістичні особливості та ідейний зміст для досягнення розуміння учнями світоглядних позицій автора та ствердження гуманістичних ідей твору на противагу антигуманним.