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