Как получить случайный элемент из дерева с учетом родительского узла?

Question

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

Конечно, я мог бы загрузить ВСЕ детей и применить случайный индекс или еще что-то ... но это было бы неэффективно.

Я интересно, если это неэффективно:

Parent.Children [случайное (Parent.Children.Count)]?

В какой момент предметы загружаются при доступе к Parent.Children?

Answer 1

Item.Children - это ленивое загруженное свойство, и я бы определенно не рекомендовал его использовать именно так, как вы здесь показываете.

Прежде чем отправлять это сообщение, я кое-что пробрал через API, чтобы увидеть, действительно ли нет способа добраться до подсчета дочерних элементов без загрузки этого свойства, но, увы, я не мог найти никакого способа, который мог бы казаться «законный». Кажется, что только свойство .HasChildren связано, и, похоже, работает, выполняя большинство (но не всех) того, что уже делает свойство .Children.

Однако, учитывая, что он ленив, загрузите результат свойства в частном поле для максимальной эффективности. Я помню, как я читал это в официальном руководстве для разработчиков в какой-то момент, я могу при необходимости найти точную ссылку.

ChildList itemChildren = myItem.Parent.Children; 
// Continue doing random() etc here, but using the itemChildren field. 

Answer 2

У вас есть целая древовидная структура? Тогда вы можете сделать какой-то случайный обход. Например, вы можете выбрать случайный элемент из двоичного дерева, как так (псевдо-код):

sub randomNode(node): 
    randomVal = random(0, 3); // random value between 0 and 3 

    if(randomVal == 0): 
    return randomNode(node.left) if node.left != null else return node; 
    elseif(randomVal == 1): 
    return randomNode(node.right) if node.right != null else return node; 
    else 
    return node; 

Для п-арной дерева, вы могли бы иметь что-то вроде этого:

sub randomNode(node): 
    randomVal = random(0, 2) 

    if(randomVal == 0): 
    return randomNode(node.children[random(0, node.children.length)]) if node.children.length != 0 else return node; 
    elseif(randomVal == 1): 
    return node; 

Doing parent.children[random(parent.children.count)] не кажется мне неэффективным; это то, что я использовал в вышеприведенном алгоритме. Что касается вашего последнего вопроса, я думаю, это зависит от того, как вы внедрили свое дерево. Если вы создали собственную древовидную структуру, вы должны иметь всю структуру дерева под рукой. Если вы используете фреймворк, то это зависит от реализации этой структуры.