Главная страница Случайная лекция Мы поможем в написании ваших работ! Порталы: БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика Мы поможем в написании ваших работ! |
Бинарные деревья
Бинарные деревья являются деревьями со степенью не более двух. Бинарное (двоичное) дерево – это динамическая структура данных, представляющее собой дерево, в котором каждая вершинаимеет не более двух потомков ( рис. 31.3). Таким образом, бинарное дерево состоит из элементов, каждый из которых содержит информационное поле и не более двух ссылок на различные бинарные поддеревья. На каждый элемент дерева имеется ровно однассылка.
Каждая вершина бинарного дерева является структурой, состоящей из четырех видов полей. Содержимым этих полей будут соответственно:
По степени вершин бинарные деревья делятся на :
В общем случае у бинарного дерева на k -м уровне может быть до 2k-1 вершин. Бинарное дерево называется полным, если оно содержит только полностью заполненные уровни. В противном случае оно является неполным. Дерево называется сбалансированным, если длины всех путей от корня к внешним вершинам равны между собой. Дерево называетсяпочти сбалансированным, если длины всевозможных путей от корня к внешним вершинам отличаются не более, чем на единицу. Бинарное дерево может представлять собой пустое множество. Бинарное дерево может выродиться в список .
Структура дерева отражается во входном потоке данных так: каждой вводимой пустой связи соответствует условный символ, например, '*' (звездочка). При этом сначала описываются левые потомки, затем, правые.
Бинарные деревья могут применяться для поиска данных в специально построенных деревьях (базы данных), сортировки данных, вычислений арифметических выражений, кодирования (метод Хаффмана) и т.д. Описание бинарного дерева выглядит следующим образом: struct имя_типа { информационное поле; [служебное поле;] адрес левого поддерева; адрес правого поддерева; }; где информационное поле – это поле любого ранее объявленного или стандартного типа; адрес левого (правого) поддерева – это указатель на объект того же типа, что и определяемая структура, в него записывается адрес следующего элемента левого (правого) поддерева. Идеально сбалансированным называется дерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более, чем на 1. Однако идеальную сбалансированность довольно трудно поддерживать. В некоторых случаях при добавлении/удалении может потребоваться значительная перестройка дерева, не гарантирующая логарифмической сложности. Поэтому Г.М.Адельсон-Вельский и Е.М.Ландис ввели менее строгое определение сбалансированности и доказали, что при таком определении можно написать программы добавления/удаления, имеющие логарифмическую сложность и сохраняющие дерево сбалансированным. Дерево считается сбалансированным по АВЛ (в дальнейшем просто «сбалансированным»), если для каждой вершины выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1. Не всякое сбалансированное дерево идеально сбалансировано, но всякое идеально сбалансированное дерево сбалансировано.
Дата добавления: 2015-07-26; просмотров: 208; Нарушение авторских прав Мы поможем в написании ваших работ! |