Раздел «Алгоритмы».BinaryTree:

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

Бинарное дерево — это направленый граф, являющийся деревом, у каждой вершины которого исходящая степень меньше либо равна 2, а входящая степень равна 1. Исключением является одна вершина — корень дерева, — входящая степень которой равна 0.

Входящая (исходящая) степень вершины есть это число входящих (исходящийх) в нее ребер.

Edit drawing 'btree' (requires a Java enabled browser)

На бинарном дереве основаны структуры данных BinaryHeap, BinarySearchTree.

Бинарное дерево называется сбалансированным, если у любой вершины с исходящей степенью 1 исходящая степень ребенка равна 0. В частности, если в структуре BinaryHeap используется именно сбалансированное бинарное дерево.

Вообще говоря, существует несколько неэквивалентных определений понятия сбалансированного дерево. Суть сбалансированности в том, что на дерево накладывается такое условие, которое гарантирует, что число вершин в граые растёт экспонециально с высотой дерева.

TopicTypeForm
Type: Определение
Author:  

Attachment sort Action Size Date Who Comment
btree.draw manage 3.9 K 06 Nov 2004 - 07:17 ArtemVoroztsov TWikiDraw? draw file
btree.gif manage 2.7 K 06 Nov 2004 - 07:17 ArtemVoroztsov TWikiDraw? GIF file