Специальное бинарное дерево

Question

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

Ну, это особый вид дерева, а не дерево AVL.

Answer 1

если двоичное дерево сбалансировано, то его высота является функцией его узлов (n). высота = бревно ₂ н. таким образом, у сбалансированного дерева нет диапазона высот.

Answer 2

Минимальное количество узлов, которое может иметь полностью сбалансированное двоичное дерево для высоты d, равно 2 ^ (d-1) +1 Насколько я знаю, у этого типа нет имени.

Максимальное количество узлов - 2 ^ d. Это называется полным деревом. Все слои полностью заполнены, и каждый узел имеет 2 или ноль детей (подразумевается).

Answer 3

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

Answer 4

Красно-чёрное дерево?

Любой из http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree#Implementations?