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

 


 

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

24960. Гражданско-правовые проблемы приватизации жилищного фонда 81 KB
  Гражданскоправовые проблемы приватизации жилищного фонда Согласно Федеральному закону от 29 декабря 2004 г. N 1541I О приватизации жилищного фонда в Российской Федерации последние изменения от 29 декабря 2004 г. Имеется проблема приватизации коммунальных квартир и комнат в них. В Примерном положении о бесплатной приватизации жилищного фонда в Российской Федерации утвержденного решением коллегии Комитета РФ по муниципальному хозяйству от 18.
24961. Гражданско-правовое регулирование приватизации государственных и муниципальных предприятий 40.5 KB
  Гражданскоправовое регулирование приватизации государственных и муниципальных предприятий Определение: приватизация – отчуждение переход недвижимого имущества из государственной или муниципальной собственности в частную собственность граждан или определенных юридических лиц в порядке установленном специальным законодательством а также переход в указанном порядке к названным лицам принадлежащих публичноправовым образованиям акций открытых акционерных обществ удостоверенных ими прав. Следует отличать от коммерциализации государственных...
24962. Договор хранения 72.5 KB
  Договор хранения Сложность и особенность хранения как обязательства по оказанию услуг заключается в двойственной природе данного договора. По договору хранения одна сторона хранитель обязуется хранить вещь переданную ей другой стороной поклажедателем возвратить эту вещь в сохранности: односторонний безвозмездный и реальный договор. В бытовой сфере где отношения сторон хранения продолжают носить личнодоверительный характер указанная элементарная конструкция может найти применение хотя и в этой сфере ее значение падает поскольку и на...
24963. Договор аренды 57 KB
  Договор аренды По договору аренды имущественного найма арендодатель обязуется предоставить арендатору имущество за плату во временное владение и пользование или во временное пользование. Договор аренды консенсуальный возмездный взаимный и двусторонний. В настоящее время объектами аренды могут быть земельные участки и участки лесного фонда. Единственным существенным условием договора аренды в силу требования закона является условие о предмете аренды.
24964. Договор аренды транспортных средств 43 KB
  Договор аренды транспортных средств Выделение договора аренды транспортного средства в качестве отдельного вида договора аренды продиктовано особенностями его предмета транспортного средства. По второму признаку аренда конной повозки с неизбежностью будет отнесена к аренде движимой вещи но не к аренде транспортного средства. Закон регламентирует две разновидности договора аренды транспортного средства: 1 аренда транспортного средства с предоставлением услуг по управлению и технической эксплуатации; 2 аренда транспортного средства без...
24965. Аренда недвижимости 56 KB
  По договору аренды предприятия в целом как имущественного комплекса используемого для осуществления предпринимательской деятельности арендодатель обязуется предоставить арендатору за плату во временное владение и пользование земельные участки здания сооружения оборудование и другие входящие в состав предприятия основные средства передать в порядке на условиях и в пределах определяемых договором запасы сырья топлива материалов и иные оборотные средства права пользования землей водой и другими природными ресурсами зданиями...
24966. Договор строительного подряда. Понятие и предмет договора 70.5 KB
  Договор строительного подряда. По договору строительного подряда одна сторона подрядчик обязуется в установленный договором срок построить по заданию заказчика определенный объект либо выполнить иные строительные работы а другая сторона заказчик обязуется создать подрядчику необходимые условия для выполнения работ принять их результат и уплатить обусловленную цену п. основной отличительный признак договора строительного подряда – характер работ и особая область в которой они осуществляются. Следовательно выполнение монтажных работ...
24967. Сравнительная характеристика договоров поручения, комиссии и агентского договора. Значение этих договоров 55.5 KB
  Сравнительная характеристика договоров поручения комиссии и агентского договора.971 ГК – легальное определение дра поручения. и фактических действий; 2 длящийся харр; 3 агент действует либо от своего имени и за счет принципала модель отношений дра комиссии либо от имени и за счет принципала модель отношений дра поручения но при этом агентский договор никогда не носит личнодоверительного характера. деятти хотя бы одним из его учв – поручение всегда возмездно если только в самом дре не предусмотрено иное; 3 отношения учв...
24968. Государственный контракт на выполнение подрядных работ для государственных нужд 54.5 KB
  Заказчик уполномоченный орган вправе размещать заказ путем проведения закрытого конкурса аукциона исключительно в случае размещения заказа на поставку товаров выполнение работ оказание услуг сведения о которых составляют государственную тайну. При этом создание комиссии по размещению заказа определение начальной цены контракта предмета и его существенных условий утверждение проекта контракта конкурсной документации документации об аукционе определение условий торгов и их изменение осуществляются заказчиком уполномоченным органом а...