Сбалансированное двоичное дерево

Question

Каково имя бинарного дерева (или семейства двоичных деревьев ), которое сбалансировано и имеет минимальное количество узлов , возможное для его высоты?

Answer 1

Это называется Фибоначчи дерево

Answer 2

AVL является сбалансированным деревом с логом (п) высоты (это самая низкой высота возможна для двоичного дерева).
Другая реализация аналогичной структуры данных - Red Black Tree.

Оба дерева реализуют все операции в O (log (n)).

Answer 3

AVL Tree - это то, что вы искали.

Материал из Википедии:

В информатике AVL tree является самобалансировку бинарное дерево поиска, и это первая такая структура данных, которые будут изобретены. В дереве AVL высоты двух дочерних поддеревьев любого узла отличаются не более чем одним; поэтому, также говорят, что сбалансированный по высоте. Поиск, вставка и удаление все принимают время O (log n) как в среднем, так и в худшем случае, где n - количество узлов в дереве до операции. Вставки и удаления могут потребовать, чтобы дерево было перебалансировано одним или несколькими вращениями дерева.

Answer 4

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

(структура данных)

Определение: binary tree, где нет leaf не больше, чем определенное количество дальше от root, чем любой другой. После вставки или удаления node дерево может перебалансироваться с помощью «поворотов».

Обобщение (я являюсь видом ...) binary tree.

Специализация (... это своего рода мне.) AVL tree, red-black tree, B-tree, balanced binary search tree.

Совокупный ребенок (... является частью или используется во мне.) left rotation, right rotation.

См. Также BB(α) tree, height-balanced tree.

- http://www.itl.nist.gov/div897/sqg/dads/HTML/balancedbitr.html