Инструменты пользователя

Инструменты сайта


binarnoe_derevo

Различия

Здесь показаны различия между двумя версиями данной страницы.

Ссылка на это сравнение

binarnoe_derevo [2011/01/02 06:57] (текущий)
Строка 1: Строка 1:
 +====== Бинарное дерево ======
 +**Бинарное дерево (binary tree**) - это упорядоченная древовидная динамическая структура. Каждый элемент (узел) дерева имеет не более двух элементов следующих за ним (потомков) и не более одного предыдущего (родителя).
 +Организация данных с помощью бинарных деревьев часто позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов,​ присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов,​ поэтому занимает значительно меньше времени. Максимальное число шагов при поиске по дереву равно высоте данного дерева,​ т.е. количеству уровней в иерархической структуре дерева.
 +<​note>​Бинарное дерево является рекурсивной структурой,​ поскольку каждое его поддерево само является бинарным деревом и, следовательно,​ каждый его узел в свою очередь является корнем самостоятельного дерева.</​note>​
 +При работе с деревьями обычно используются рекурсивные алгоритмы. Использование рекурсивных функций менее эффективно,​ поскольку многократный вызов функции расходует системные ресурсы. Тем не менее, в данном случае использование рекурсивных функций является оправданным,​ поскольку нерекурсивные функции для работы с деревьями гораздо сложнее и для написания,​ и для восприятия кода программы.
 +
 +  - Самый главный принцип бинарного дерева заключается в том, что для каждого узла выполняется правило:​ **в левой ветке содержатся только те ключи, которые имеют значения,​ меньшие,​ чем значение данного узла. В правой же ветке содержатся ключи, имеющие значения,​ большие,​ чем значение данного узла**.
 +  - Каждый узел может иметь два, одного или ни одного потомка.
 +  - **Лист** - узел, не имеющий потомков.
 +  - Узел является родительским для своих потомков и дочерним для своего предка.
 +  - **Левый потомок** - дочерний узел слева от текущего узла.
 +  - **Правый потомок** - дочерний узел справа от текущего узла.
 +  - **Корень** - основной узел, не имеющий родителей.
 +  - Каждый узел состоит из четырех частей: ​
 +        * Значение.
 +        * Указатель на родителя.
 +        * Указатель на левого потомка.
 +        * Указатель на правого потомка.
  
загрузка...
binarnoe_derevo.txt · Последние изменения: 2011/01/02 06:57 (внешнее изменение)