4625
правок
Бинарное дерево: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
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. Любая структура данных, используемая для представления '''бинарного дерева'''. | ||
Каждая вершина в ней должна быть представлена указателями на левое и | Каждая вершина в ней должна быть представлена указателями на левое и | ||
правое поддеревья, а также на значение данных, связанное с этой | правое поддеревья, а также на значение данных, связанное с этой | ||
вершиной. Тогда ''' | вершиной. Тогда '''бинарное дерево''' можно представить как указатель его | ||
корня. | корня. | ||
==Литература== | ==Литература== | ||
[Кнут], | [Кнут], | ||