Категория
Информатика
Тип
реферат
Страницы
5 стр.
Дата
15.09.2008
Формат файла
.rtf — Rich Text Format (Wordpad)
Архив
18193.zip — 10.58 kb
  • dinamicheskie-struktury-dannyx-dvoichnye-derevja_18193_1.rtf — 51.46 Kb
  • Readme_docus.me.txt — 125 Bytes
Рейтинг
10  из 10
Оценок
1
Оцените работу
Хорошо  или  Плохо


Текст работы

Динамические структуры данных: двоичные деревья
Дерево — это совокупность элементов, называемых узлами (при этом один из них определен
как корень), и отношений (родительский– дочерний), образующих иерархическую структуру узлов. Узлы могут являться величинами любого простого или
структурированного типа, за исключением файлового. Узлы, которые не имеют ни одного последующего узла, называются листьями.
В двоичном (бинарном) дереве каждый узел может быть связан не более чем двумя другими узлами. Рекурсивно двоичное дерево определяется так: двоичное дерево бывает либо пустым (не содержит ни одного узла), либо содержит узел, называемый корнем, а также два независимых поддерева — левое поддерево и правое поддерево.
Двоичное дерево поиска может быть либо пустым, либо оно обладает таким свойством, что корневой элемент имеет большее значение узла, чем любой элемент в левом поддереве, и меньшее или равное, чем элементы в правом поддереве. Указанное свойство называется характеристическим свойством двоичного дерева поиска и выполняется для любого узла такого дерева, включая
корень. Далее будем рассматривать только двоичные деревья поиска. Такое
название двоичные деревья поиска получили по той причине, что скорость
поиска в них примерно такая же, что и в отсортированных массивах: O(n) = C
• log2n (в худшем случае O(n) =
n).
Пример. Для набора данных 9, 44, 0, – 7, 10, 6, – 12, 45 построить двоичное дерево поиска.
Согласно определению двоичного дерева поиска число 9 помещаем в корень,
все значения, меньшие его — на левое поддерево, большие или равные
— на правое. В каждом поддереве очередной элемент можно рассматривать как корень и действовать по тому же алгоритму. В итоге получаем
Выделим



Ваше мнение



CAPTCHA