Бинарное дерево: различия между версиями
KEV (обсуждение | вклад) (Создана новая страница размером '''Бинарное дерево'''(Binary tree) - 1. Ордерево, растущее из [[ко...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 6: | Строка 6: | ||
и левая дуги, выходит одна правая дуга, выходит одна левая | и левая дуги, выходит одна правая дуга, выходит одна левая | ||
дуга, нет выходящих дуг. На уровне <math>h</math> бинарного дерева имеется | дуга, нет выходящих дуг. На уровне <math>h</math> бинарного дерева имеется | ||
максимум <math>2^{h}</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>. | ||
[[Файл:Binary tree. | [[Файл:Binary tree.png]] | ||
Другое название --- [[Двоичное дерево|''Двоичное дерево'']]. | Другое название --- [[Двоичное дерево|''Двоичное дерево'']]. | ||
Иногда под ''' | Иногда под '''бинарным деревом''' просто | ||
понимается ордерево, из каждой вершины которого исходит не | понимается ордерево, из каждой вершины которого исходит не | ||
более двух дуг. См. [[m-Арное дерево|''<math>m</math>-Арное дерево'']]. | более двух дуг. См. [[m-Арное дерево|''<math>m</math>-Арное дерево'']]. | ||
2. Любая структура данных, используемая для представления ''' | 2. Любая структура данных, используемая для представления '''бинарного дерева'''. | ||
Каждая вершина в ней должна быть представлена указателями на левое и | Каждая вершина в ней должна быть представлена указателями на левое и | ||
правое поддеревья, а также на значение данных, связанное с этой | правое поддеревья, а также на значение данных, связанное с этой | ||
вершиной. Тогда ''' | вершиной. Тогда '''бинарное дерево''' можно представить как указатель его | ||
корня. | корня. | ||
==Литература== | ==Литература== | ||
[Кнут], | [Кнут], | ||
Версия от 13:24, 7 июня 2010
Бинарное дерево(Binary tree) - 1. Ордерево, растущее из корня, причем из каждой вершины исходит не более двух дуг, помеченных как правая или левая дуга. Другими словами, возможны следующие комбинации: выходят правая и левая дуги, выходит одна правая дуга, выходит одна левая дуга, нет выходящих дуг. На уровне [math]\displaystyle{ h }[/math] бинарного дерева имеется максимум [math]\displaystyle{ 2^{h} }[/math]вершин. Поэтому бинарное дерево высотой [math]\displaystyle{ d }[/math] имеет максимум [math]\displaystyle{ (2^{d+1} - 1) }[/math] вершин, а дерево с [math]\displaystyle{ n }[/math] вершинами имеет минимальную высоту [math]\displaystyle{ \log_{2} n }[/math].
Другое название --- Двоичное дерево. Иногда под бинарным деревом просто понимается ордерево, из каждой вершины которого исходит не более двух дуг. См. [math]\displaystyle{ m }[/math]-Арное дерево.
2. Любая структура данных, используемая для представления бинарного дерева. Каждая вершина в ней должна быть представлена указателями на левое и правое поддеревья, а также на значение данных, связанное с этой вершиной. Тогда бинарное дерево можно представить как указатель его корня.
Литература
[Кнут],
[Евстигнеев/85],
[Евстигнеев-Касьянов/94],
[Касьянов-Поттосин],
[Словарь]