4625
правок
Бинарное дерево: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Бинарное дерево'''([[ | '''Бинарное дерево'''(''[[Binary tree]]'') — 1. [[Ордерево]], растущее из | ||
[[корень|корня]], причем из каждой [[вершина|вершины]] исходит | [[корень|корня]], причем из каждой [[вершина|вершины]] исходит | ||
не более двух [[дуга|дуг]], | не более двух [[дуга|дуг]], | ||
| Строка 6: | Строка 6: | ||
и левая дуги, выходит одна правая дуга, выходит одна левая | и левая дуги, выходит одна правая дуга, выходит одна левая | ||
дуга, нет выходящих дуг. На уровне <math>h</math> бинарного дерева имеется | дуга, нет выходящих дуг. На уровне <math>h</math> бинарного дерева имеется | ||
максимум <math>2^{h}</math>вершин. Поэтому '''бинарное дерево''' [[высота дерева|высотой]] <math>d</math> имеет максимум | максимум <math>2^{h}</math> вершин. Поэтому '''бинарное дерево''' [[высота дерева|высотой]] <math>d</math> имеет максимум | ||
<math>(2^{d+1} - 1)</math> вершин, а дерево с <math>n</math> вершинами имеет минимальную | <math>(2^{d+1} - 1)</math> вершин, а дерево с <math>n</math> вершинами имеет минимальную | ||
высоту <math>\log_{2} n</math>. | высоту <math>\log_{2} n</math>. | ||
| Строка 12: | Строка 12: | ||
[[Файл:Binary tree.png|350px]] | [[Файл:Binary tree.png|350px]] | ||
Другое название | Другое название — ''[[Двоичное дерево]]''. | ||
Иногда под '''бинарным деревом''' просто | Иногда под '''бинарным деревом''' просто | ||
понимается ордерево, из каждой вершины которого исходит не | понимается ордерево, из каждой вершины которого исходит не | ||
| Строка 23: | Строка 23: | ||
корня. | корня. | ||
==Литература== | ==Литература== | ||
* Кнут Д. Искусство программирования для ЭВМ. — М.: Мир, 1978. — Т. 3. Сортировка и поиск. | |||
* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985. | |||
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994. | |||
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986. | |||
* Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991. | |||