Бинарное дерево

Материал из WEGA
Версия от 14:59, 10 сентября 2009; KEV (обсуждение | вклад) (Создана новая страница размером '''Бинарное дерево'''(Binary tree) - 1. Ордерево, растущее из [[ко...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

Бинарное дерево(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].

Файл:Binary tree.jpg

Другое название --- Двоичное дерево. Иногда под Б.д. просто понимается ордерево, из каждой вершины которого исходит не более двух дуг. См. [math]\displaystyle{ m }[/math]-Арное дерево.

2. Любая структура данных, используемая для представления Б.д.. Каждая вершина в ней должна быть представлена указателями на левое и правое поддеревья, а также на значение данных, связанное с этой вершиной. Тогда Б.д. можно представить как указатель его корня.}

Литература

[Кнут],

[Евстигнеев/85],

[Евстигнеев-Касьянов/94],

[Касьянов-Поттосин],

[Словарь]