Средняя высота дерева двоичного поиска
Вам необходимо добавить аннотацию JsonTypeInfo на уровне класса:
@JsonInclude(JsonInclude.Include.NON_NULL)
@JsonPropertyOrder({
"code",
"message",
"payload"
})
@JsonTypeInfo(use = JsonTypeInfo.Id.CLASS, property = "@type")
class Train {
include по умолчанию имеет значение JsonTypeInfo.As.PROPERTY, поэтому вам не нужно указывать его.
См. Также:
6 ответов
Вы можете вычислить высоту двоичного дерева, используя это рекурсивное определение:
height(empty) = 0
height(tree) = 1 + max(height(tree.left), height(tree.right))
Один из способов эмпирически измерить среднюю высоту такого дерева - это многократно создать пустое дерево и добавить 1000 случайных предметы к нему. Измерьте высоту каждого испытания, используя указанную выше функцию, и усредните их.
Я подозреваю, что ваша задача, вероятно, состоит в том, чтобы найти формулу для средней высоты двоичного дерева.
Это зависит от того, используете ли вы какую-либо сбалансированную древовидную структуру (например, красно-черное дерево). Поскольку вы вставляете случайные числа в двоичное дерево, было бы разумно ожидать, что средняя глубина будет приблизительно равна log2 (1000), поэтому значения 10 и 11 будут «нормальными». Я не уверен, насколько далеко это может отклоняться от этого; не менее 10 уровней, возможно, несколько глубже. В крайнем случае без балансировки будет глубина 1000; что вряд ли произойдет со случайными числами.
This question got me asking whether you can definitively work this out without actually generating the trees.
I managed to write an application which could calculate the answer to what the average height would be if you added every possible permutation of N unique numbers to a naively implemented binary tree.
The answers I got are in this graph. (The X-axis is the number of items in the tree, the blue line is the average height, and the red line is the optimum possible height)
N Average Height 2 2 16 7.039 32 9.280 64 11.679 256 16.783 343 17.896
Granitebolshevik is right: it's possible but statistically unlikely that a naively implemented tree will be the optimum height, without extra balancing functionality.
The algorithm has a complexity of O(N^2), and it isn't fast enough to calculate really large numbers.
это зависит от порядка добавления. Если вы начнете с наименьшего значения, тогда дерево будет глубже, потому что все новые значения будут добавлены в правый дочерний BST. Если вы сначала добавите наибольшее значение, то левый дочерний элемент будет глубоким, а правый - пустым.
На самом деле этот вопрос сложный. Ответом будет не 1000, потому что это маловероятно, но log2 (1000) также маловероятно, но тем более в зависимости от того, как растет дерево.
Если вы добавляете int, пройдя через дерево, то наивно добавляете его дерево практически всегда будет выше, чем log2 (1000).
Поговорите со статистиком, потому что это кажется связанным с нормальным распределением вероятностей. Они генерируются множеством повторяющихся случайных событий (голова на одну единицу вправо, хвост влево), а значение случайного целого числа повторяется по дереву по мере того, как оно превращается в лист.
Независимо от того, какое дерево вы используете, средняя высота будет log2 (1000), как упоминалось ранее. Верно, что в зависимости от порядка вставленных чисел фактическая высота может варьироваться, но, если предположить, что числа, распределенные случайным образом, о которых вы упомянули, то фактическое значение будет чаще всего приближаться к ожидаемому значению (которое, опять же, равно log2 (1000))