+7 (700) 521-36-15
бинарное дерево поискаш

бинарное дерево поискавая

Бинарное дерево – проще чем кажется. Опубликовано 02.09.2012 | Автор: admin.  } Автор сайта отвечает: Бинарные деревья, как правило, используют для поиска.

Содержание
1 Основные понятия
2 Представление в памяти
3 Бинарное дерево поиска
4 Пути и полупути
5 Обходы дерева
5.1 Прямой обход
5.2 Обратный обход
5.3 Внутренний обход
6 Удаление вершины Основные понятия
Деревом называется связный граф без циклов. На практике часто приходится иметь дело со специальными видами деревьев. Наиболее распространенным среди них является корневое дерево.
Корневое дерево — это ориентированный граф, который удовлетворяет следующим условиям:
имеется в точности одна вершина, в которую не входит ни одна дуга, называемая корнем;
в каждую вершину, кроме корня, входит ровно одна дуга;
из корня имеется путь к каждой вершине.
Если в корневом дереве существует путь из v в w, то v называют предком вершины w, а w — потомком вершины v. Если вершина не имеет потомков, то ее называют висячей вершиной или листом. Остальные вершины называют внутренними. Если ( v, w) — дуга корневого дерева, то v называется отцом (непосредственным предком) вершины w, а w называется сыном (непосредственным потомком) вершины v. Вершина v корневого дерева T и все ее потомки вместе образуют поддерево корневого дерева T с корнем в вершине v.
Глубиной вершины v в корневом дереве называется длина в дугах пути (этот путь единственный) из корня в эту вершину.
Высотой вершины v в корневом дереве называется длина (в дугах) наибольшего пути из вершины v до одного из его потомков. Высота корневого дерева — высота корня. Высота дерева, состоящего из одной единственной вершины, полагается равной нулю.
Уровнем вершины v называется разность высоты дерева и глубины вершины v.
Упорядоченное корневое дерево — это корневое дерево, у которого дуги, выходящие из каждой вершины, упорядочены (в дальнейшем будем считать, что они упорядочены слева направо).
Бинарное дерево — это упорядоченное корневое дерево, у каждой вершины которого имеется не более двух сыновей. В бинарном дереве каждый сын произвольной вершины определяется как левый или правый. Поддерево (если оно существует), корнем которого является левый сын вершины v, называется левым поддеревом вершины v. Аналогичным образом определяется правое поддерево для вершины v.
Представление в памяти
Существует несколько способов представления бинарных деревьев (предполагаем, что вершины дерева занумерованы целыми числами от 1 до n).
Представление в виде двух массивов — Left и Right:
если вершина j является левым (правым) сыном вершины i, то Left[i] = j ( Right[i] = j);
если у вершины i нет левого (правого) сына, то Left[i] = 0 ( Right[i] = 0).

Для выполнения операции findElement(A:) в словаре Д представленном бинарным деревом поиска Г, рассмотрим деребо Г как дерево решений (см. рис. 6.5).

Представление в виде списковой структуры, когда каждый элемент списка содержит помимо информационной части (ключ вершины, дополнительные метки и т.п.), ссылку на левого и правого ее сыновей и, возможно, ссылку на отца:
Бинарное поисковое дерево высоты 3 с 9 вершинами, корнем 8 и листьями 1, 4, 7 и 13, средней по значению среди вершин дерева является вершина 7
Предположим, что каждой вершине бинарного дерева соответствует некоторое ключевое значение (например целое число). Бинарное дерево называется деревом поиска ( бинарным поисковым деревом), если оно организовано так, что для каждой вершины v справедливо утверждение, что все ключи в левом поддереве вершины v меньше ключа вершины v, а все ключи в правом поддереве больше. В поисковом дереве нет двух вершин с одинаковыми ключевыми значениями, если не оговорено иное. Минимальный (максимальный) элемент бинарного поискового дерева соответствует ключевому значению самой левой (правой) вершины дерева.
Во многих задачах требуется найти среднюю по значению из вершин дерева. Средней по значению является та из вершин дерева, которой соответствует такое ключевое значение x, что количество вершин дерева, имеющих ключевое значение строго меньшее x, равно количеству вершин дерева, имеющих ключевые значения строго большие x. Если количество вершин в дереве чётно, то будем считать, что средней по значению вершины не существует. Если же дерево состоит из единственной вершины, то будем полагать, что эта вершина является средней по значению.
Пути и полупути
Путём в дереве называется чередующаяся последовательность вершин и дуг v 0, ( v 0, v 1), v 1, ( v 1, v 2), v 2, ..., v n. Напомним, что в пути дуги не могут повторяться. Длина пути — количество дуг в нём. Так, на приведённом рисунке последовательность 8, (8, 3), 3, (3, 6), 6 является путём длины 2.
Определим центральную вершину некоторого пути, как такую вершину v, что количество вершин в этом пути до нее равно количеству вершин в этом пути после нее (если количество вершин в пути четно, то будем говорить, что центральной вершины для заданного пути не существует). Так, на приведённом рисунке для пути 8, (8, 3), 3, (3, 6), 6 центральной вершиной является вершина 3.
Определим среднюю вершину некоторого пути, как такую вершину v, что количество вершин в этом пути ключ которых меньше ключа вершины v равно количеству вершин в этом пути ключ которых больше ключа вершины v (если количество вершин в пути четно, то будем говорить, что средней вершины для заданного пути не существует). Так, на приведённом рисунке для пути 8, (8, 3), 3, (3, 6), 6 средней вершиной является вершина 6.

Рассмотрим несколько основных функций для работы с бинарным деревом: добавление нового узла(add), поиск элемента (serch), обход (view), очистить (clean).

Для полупути снимается ограничение на направление дуг. Например, последовательность 3, (8, 3), 8, (8, 10), 10 является полупутём длины 2, но не является путём. В полупути, как и в пути, дуги не могут повторяться.
Корнем полупути будем называть ту из вершин этого полупути, которая находится на наибольшей высоте (если выписать дуги полупути, то из коня этого полупути дуги только выходят). Центральная и средняя вершины полупути определяются аналогично, как и для пути. Для полупути 3, (8, 3), 8, (8, 10), 10 вершина 8 является и центральной, и средней, и корнем этого полупути.
Наибольшим полупутём в дереве будем называть полупуть наибольшей длины (не стоит путать наибольший полупуть с максимальным полупутём — полупутём, который нельзя продолжить; наибольший полупуть всегда является максимальным, а вот обратное не всегда верно). Следует отметить, что наибольший полупуть в дереве не обязательно соединяет некоторые два листа этого дерева. Так, например, если у корня дерева только одно поддерево, то наибольший полупуть может соединять корень дерева и один из листьев.
Заметим, что в дереве может быть несколько корней полупутей наибольшей длины, а через один и тот же корень может проходить несколько различных полупутей наибольшей длины.
Так, в дереве, приведённом на рисунке, есть два наибольших полупути: один соединяет вершину 4 и вершину 13, другой — вершину 7 и вершину 13. Оба эти полупути имеют длину 6 и имеют общий корень — вершину 8.
Обходы дерева
Бинарное поисковое дерево. Прямой левый обход: 8 3 1 6 4 7 10 14 13; обратный левый обход: 4 7 6 1 3 13 14 10 8; внутренний левый обход:1 3 4 6 7 8 10 13 14.
Многие алгоритмы, работая с бинарными корневыми деревьями, посещают один раз в определенном порядке каждую вершину дерева. Cуществуют три наиболее распространенных способа обхода вершин бинарного дерева (предполагаем, что бинарное дерево задано списковой структурой): прямой, обратный и внутренний.
Прямой обход
Прямой порядок обхода (сверху вниз) заключается в том, что корень некоторого дерева посещается раньше, чем его поддеревья. Если после корня посещается его левое (правое) поддерево, то обход называется прямым левым (правым) обходом.
Приведем процедуру прямого левого обхода.
procedure order2 (v : tree_ptr ) ; begin if v nil then begin
order2 (v ^ . left ) ;
order2 (v ^ . right ) ;
solve (v ) ; end ; end ; Внутренний обход
Внутренний порядок обхода (слева направо или справа налево) заключается в том, что корень посещается после посещения одного из его поддеревьев. Если корень посещается после посещения его левого (правого) поддерева, то обход называется внутренним левым (правым) обходом. Заметим, что внутренний левый (правый) обход посещает вершины дерева в порядке возрастания (убывания) ключей вершин.
Приведем процедуру левого внутреннего обхода.
procedure order3 (v : tree_ptr ) ; begin if v nil then begin
order3 (v ^ . left ) ;
solve (v ) ;
order3 (v ^ . right ) ; end ; end ;
Для решения многих задач, предложенных в системе InsightRunner, может потребоваться вычисление для каждой вершины v некоторых меток, например, высоты, глубины, количества вершин в дереве с корнем в вершине v и др. Для выполнения этих действий можно использовать соответствующие процедуры обхода вершин дерева, а вычисления нужных меток выполнять в процедуре solve(v).
Удаление вершины
В некоторых задачах требуется выполнить удаление заданной вершины v из дерева (предположим, что f – отец удаляемой вершины).
Задача удаления достаточно проста и выполняется за константное время, если у удаляемой вершины v не более одного поддерева (предположим, что если поддерево у вершины v существует, то w – его корень). В этом случае можно выполнить непосредственное удаление вершины v, после чего выполняются следующие действия:
если v — корень дерева, то корнем дерева станет вершина w (если у вершины v сыновей не было, то дерево перестанет существовать);
если v — лист, то ссылка у вершины f, указывающая на вершину v, станет пустой;
если v не лист и не корень дерева, то ссылка у f, указывающая на v, будет указывать на w.
Случай удаления вершины v, у которой два поддерева, можно свести к предыдущему. При этом непосредственного удаления вершины v из дерева не происходит, а ключ вершины v заменяется на значение минимального (максимального) ключа среди вершин правого (левого) поддерева вершины v — такое удаление называют правым ( левым).
Рассмотрим более подробно правое удаление. Предположим, что минимальный ключ в правом поддереве вершины v имела вершина z. Запишем ключ вершины z в вершину v, что приведёт к тому, что в дереве появятся две вершины v и z с одинаковыми ключевыми значениями, а это недопустимо для бинарного поискового дерева.
Поэтому, удаляем вершину z из дерева. Это сделать проще, так как вершина z не имеет левого поддерева (либо является листом) и завершаем процедуру удаления.

Здесь приведены два класса, реализующие двоичное дерево поиска: TreeNode и Tree. Первый класс содержит описание узлов дерева 6 апреля 2004


C++ Бинарное (двоичное) дерево поиска C++ Бинарное дерево поиска знаков зодиака C++  Искать еще темы с ответами. Или воспользуйтесь поиском по форуму

Бинарное дерево поиска (англ. binary search tree, BST) — структура данных для работы с упорядоченными множествами. Бинарное дерево поиска обладает следующим свойством: если — узел бинарного дерева с ключом


Двоичное дерево поиска (англ. binary search tree, BST) — это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска): Оба поддерева — левое и правое — являются двоичными деревьями поиска.


Ев. от Матфея, 19:30 Основы программирования Содержание 2 ¨ ¨ Деревья и бинарные деревья Бинарные деревья поиска Деревья и бинарные деревья 3

3.2.2. Бинарные деревья поиска, сортировка деревом: Tree65 Бинарное дерево называется деревом поиска


Таким образом, последовательное поступление вершин с ключами 100, 50, 200, 100 приведет к созданию структуры данных - бинарного дерева поиска.


Бинарное дерево поиска. Понятие бинарных деревьев. Программа для работы с бинарным упорядоченным деревом, созданная в среде Turbo Pascal.

Википедея даёт вот такое изображение бинарного дерева поиска: Итак, класс (назову его BinaryTree) дерева будет содержать следующую информацию