Binary Tree - Генератор случайных

Question

Пусть у меня есть бинарное дерево, как это -

 5    
    /\  
    / \  
    / \  
/  \  
    2  8  
/\ /\ 
/ \ / \ 
1 3 6 9 
     \ \ \ 
     4 11 10 

Теперь у меня есть генератор случайных чисел, который будет генерировать число от 1 до размера дерева (10 в данном случае). Основываясь на случайном значении, генерируемом случайным генератором, я должен вернуть узел из дерева (предположим, генератор задан 7, поэтому я возвращаю 7-й узел (значение 11), выполняя обход порядка). Завтра я добавляю еще 4 узла к дереву. Как сохранить согласованность? Как и в случае, тот же узел из дерева возвращается для случайного значения. Проход по порядку создаст другой массив, и значение индекса изменится.

Answer 1

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

Пока неясно, чего вы пытаетесь достичь, но я вижу пару возможностей. Если ваше намерение заключается в том, что новые узлы могут быть добавлены в любом месте дерева, тогда у них действительно нет никаких индексов, которые бы отображали их разумно. В этом случае я бы просто создал карту (например, HashMap) в точке замерзания, чтобы сопоставить индексы с узлами. Пройдите дерево с обходным путем, постройте карту и сохраните ее вместе с древовидной структурой. Используйте карту для определения узла для индекса, а не для перемещения по дереву.

Если вместо добавления узлов в любом месте дерева вы хотите добавить узлы в место, чтобы исходные узлы по-прежнему имели один и тот же индекс, тогда все, что вам нужно сделать, это спуститься справа от деревьев, пока вы не попал в узел без права ребенка. В Опубликованном например, что бы узле 10:

 5    
    /\  
    / \  
    / \  
/  \  
    2  8  
/\ /\ 
/ \ / \ 
1 3 6 9 
     \ \ \ 
     4 11 10** 

Отметить этот узел в точке, где вы хотите, чтобы заморозить. Затем, когда вы добавляете новый узел, новый узел должен быть добавлен либо как правый дочерний элемент отмеченного узла, либо если отмеченный узел имеет правильный дочерний элемент R (поскольку вы уже добавили один после замораживания) где бы он ни был потомком R. Новые узлы, добавленные таким образом, всегда будут успешными в обходном порядке узлами, которые присутствовали в точке замерзания. Таким образом, индексы ранее добавленных узлов не будут затронуты.

Если ни одно из них не является тем, что вы хотите, вам необходимо предоставить дополнительные разъяснения о том, что вам нужно.

Answer 2

Одним из вариантов было бы просто добавить новые узлы в качестве прав детей последнего узла в обходном порядке. Это приведет к очень глубокому и неуравновешенному дереву; вы не просили сбалансированного дерева, поэтому вполне возможно, что все в порядке.