Минимальное и максимальное количество узлов в дереве 2-3

Question

Минимальное и максимальное количество узлов в дереве 2-3

Я пытаюсь выяснить, каково минимальное и максимальное количество узлов в 2-3 дерева с n листьев.

Я попытался заблокировать его с помощью inf\sup, но я не мог пойти дальше, так как число узлов в дереве 2-3 больше, чем число узлов в дереве полного AVL.

заранее спасибо

0

data-structures tree space-complexity avl-tree 2-3-tree

Источник

user2411058 06 май '14 в 19:53

1 ответ

Другие вопросы по тегам data-structures tree space-complexity avl-tree 2-3-tree

user141522 06 май '14 в 20:05 2014-05-06 20:05 · Answer 1 · 2014-05-06 20:05

Действуя по определению 2-3 дерева в Википедии:

В информатике дерево 2–3 - это тип структуры данных, дерево, в котором каждый узел с дочерними элементами (внутренний узел) имеет либо двух дочерних элементов (2 узла), либо один элемент данных, либо трех дочерних элементов (3 узла) и два элементы данных. Узлы на внешней стороне дерева (конечные узлы) не имеют дочерних элементов и одного или двух элементов данных.

Мне кажется, что максимальное количество узлов в дереве будет, когда у каждого внутреннего узла есть 3 дочерних элемента. Чтобы найти максимальное количество узлов в этом дереве, мы должны сначала найти высоту дерева.

Если есть n листья в этом 3 дерева, то высота дерева height = log3(n) (зарегистрируйте базу 3 из n), и поэтому максимальное количество элементов будет 3^height,

Наименьшее дерево - это дерево с наименьшим количеством элементов, которое может быть деревом с одним узлом.