Аноним

Бинарное дерево: различия между версиями

Материал из WEGA
нет описания правки
Нет описания правки
Нет описания правки
Строка 1: Строка 1:
'''Бинарное дерево'''([[Binary tree|Binary tree]]) - 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.


[Евстигнеев/85],
* Касьянов В.Н., Поттосин И.В. Методы построения трансляторов. — Новосибирск: Наука. Сиб. отд-ние, 1986.
   
   
[Евстигнеев-Касьянов/94],
* Толковый словарь по вычислительным системам. — М.: Машиностроение, 1991.
 
[Касьянов-Поттосин], 
 
[Словарь]