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

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


Боковая панель

Связь

binarnoe_derevo

Бинарное дерево

Бинарное дерево (binary tree) - это упорядоченная древовидная динамическая структура. Каждый элемент (узел) дерева имеет не более двух элементов следующих за ним (потомков) и не более одного предыдущего (родителя). Организация данных с помощью бинарных деревьев часто позволяет значительно сократить время поиска нужного элемента. Поиск элемента в линейных структурах данных обычно осуществляется путем последовательного перебора всех элементов, присутствующих в данной структуре. Поиск по дереву не требует перебора всех элементов, поэтому занимает значительно меньше времени. Максимальное число шагов при поиске по дереву равно высоте данного дерева, т.е. количеству уровней в иерархической структуре дерева.

Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само является бинарным деревом и, следовательно, каждый его узел в свою очередь является корнем самостоятельного дерева.

При работе с деревьями обычно используются рекурсивные алгоритмы. Использование рекурсивных функций менее эффективно, поскольку многократный вызов функции расходует системные ресурсы. Тем не менее, в данном случае использование рекурсивных функций является оправданным, поскольку нерекурсивные функции для работы с деревьями гораздо сложнее и для написания, и для восприятия кода программы.

  1. Самый главный принцип бинарного дерева заключается в том, что для каждого узла выполняется правило: в левой ветке содержатся только те ключи, которые имеют значения, меньшие, чем значение данного узла. В правой же ветке содержатся ключи, имеющие значения, большие, чем значение данного узла.
  2. Каждый узел может иметь два, одного или ни одного потомка.
  3. Лист - узел, не имеющий потомков.
  4. Узел является родительским для своих потомков и дочерним для своего предка.
  5. Левый потомок - дочерний узел слева от текущего узла.
  6. Правый потомок - дочерний узел справа от текущего узла.
  7. Корень - основной узел, не имеющий родителей.
  8. Каждый узел состоит из четырех частей:
    • Значение.
    • Указатель на родителя.
    • Указатель на левого потомка.
    • Указатель на правого потомка.



binarnoe_derevo.txt · Последние изменения: 2011/01/02 06:57 (внешнее изменение)