Dado un árbol binario con Nodes secundarios, devuelva un Node aleatorio con la misma probabilidad de seleccionar cualquier Node en el árbol.
Considere el árbol dado con raíz 1.
10
/ \
20 30
/ \ / \
40 50 60 70
Ejemplos:
Input : getRandom(root); Output : A Random Node From Tree : 3 Input : getRandom(root); Output : A Random Node From Tree : 2
Una solución simple es almacenar el recorrido del árbol en orden en una array. Sea n el número de Nodes. Para obtener un Node aleatorio, generamos un número aleatorio de 0 a n-1, usamos este número como índice en la array y devolvemos el valor en el índice.
Una solución alternativa es modificar la estructura de árbol. Almacenamos el recuento de niños en cada Node. Considere el árbol anterior. Usamos el recorrido en orden aquí también. Generamos un número menor o igual al número de Nodes. Atravesamos el árbol y vamos al Node en ese índice. Usamos conteos para llegar rápidamente al Node deseado. Con conteos, llegamos en tiempo O(h) donde h es la altura del árbol.
10,6
/ \
20,2 30,2
/ \ / \
40,0 50,0 60,0 70,0
The first value is node and second
value is count of children.
Comenzamos a atravesar el árbol, en cada Node vamos al subárbol izquierdo o al subárbol derecho considerando si el conteo de niños es menor que el conteo aleatorio o no.
Si el conteo aleatorio es menor que el conteo de niños, vamos a la izquierda, de lo contrario, vamos a la derecha.
A continuación se muestra la implementación del algoritmo anterior. getElements devolverá el recuento de niños para root, InsertChildrenCount inserta datos de niños en cada Node, RandomNode devolverá el Node aleatorio con la ayuda de la función de utilidad RandomNodeUtil.
C++
// CPP program to Select a Random Node from a tree
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
int children;
Node *left, *right;
};
Node* newNode(int data)
{
Node *temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
temp->children = 0;
return temp;
}
// This is used to fill children counts.
int getElements(Node* root)
{
if (!root)
return 0;
return getElements(root->left) +
getElements(root->right) + 1;
}
// Inserts Children count for each node
void insertChildrenCount(Node*& root)
{
if (!root)
return;
root->children = getElements(root) - 1;
insertChildrenCount(root->left);
insertChildrenCount(root->right);
}
// returns number of children for root
int children(Node* root)
{
if (!root)
return 0;
return root->children + 1;
}
// Helper Function to return a random node
int randomNodeUtil(Node* root, int count)
{
if (!root)
return 0;
if (count == children(root->left))
return root->data;
if (count < children(root->left))
return randomNodeUtil(root->left, count);
return randomNodeUtil(root->right,
count - children(root->left) - 1);
}
// Returns Random node
int randomNode(Node* root)
{
srand(time(0));
int count = rand() % (root->children + 1);
return randomNodeUtil(root, count);
}
int main()
{
// Creating Above Tree
Node* root = newNode(10);
root->left = newNode(20);
root->right = newNode(30);
root->left->right = newNode(40);
root->left->right = newNode(50);
root->right->left = newNode(60);
root->right->right = newNode(70);
insertChildrenCount(root);
cout << "A Random Node From Tree : "
<< randomNode(root) << endl;
return 0;
}
Java
// Java program to Select a Random Node from a tree
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG
{
static class Node
{
int data;
int children;
Node left, right;
}
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
temp.children = 0;
return temp;
}
// This is used to fill children counts.
static int getElements(Node root)
{
if (root == null)
return 0;
return getElements(root.left) +
getElements(root.right) + 1;
}
// Inserts Children count for each node
static Node insertChildrenCount(Node root)
{
if (root == null)
return null;
root.children = getElements(root) - 1;
root.left = insertChildrenCount(root.left);
root.right = insertChildrenCount(root.right);
return root;
}
// returns number of children for root
static int children(Node root)
{
if (root == null)
return 0;
return root.children + 1;
}
// Helper Function to return a random node
static int randomNodeUtil(Node root, int count)
{
if (root == null)
return 0;
if (count == children(root.left))
return root.data;
if (count < children(root.left))
return randomNodeUtil(root.left, count);
return randomNodeUtil(root.right,
count - children(root.left) - 1);
}
// Returns Random node
static int randomNode(Node root)
{
int count = (int) Math.random() *
(root.children + 1);
return randomNodeUtil(root, count);
}
// Driver Code
public static void main(String args[])
{
// Creating Above Tree
Node root = newNode(10);
root.left = newNode(20);
root.right = newNode(30);
root.left.right = newNode(40);
root.left.right = newNode(50);
root.right.left = newNode(60);
root.right.right = newNode(70);
insertChildrenCount(root);
System.out.println( "A Random Node From Tree : " +
randomNode(root));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to Select a
# Random Node from a tree
from random import randint
class Node:
def __init__(self, data):
self.data = data
self.children = 0
self.left = None
self.right = None
# This is used to fill children counts.
def getElements(root):
if root == None:
return 0
return (getElements(root.left) +
getElements(root.right) + 1)
# Inserts Children count for each node
def insertChildrenCount(root):
if root == None:
return
root.children = getElements(root) - 1
insertChildrenCount(root.left)
insertChildrenCount(root.right)
# Returns number of children for root
def children(root):
if root == None:
return 0
return root.children + 1
# Helper Function to return a random node
def randomNodeUtil(root, count):
if root == None:
return 0
if count == children(root.left):
return root.data
if count < children(root.left):
return randomNodeUtil(root.left, count)
return randomNodeUtil(root.right,
count - children(root.left) - 1)
# Returns Random node
def randomNode(root):
count = randint(0, root.children)
return randomNodeUtil(root, count)
# Driver Code
if __name__ == "__main__":
# Creating Above Tree
root = Node(10)
root.left = Node(20)
root.right = Node(30)
root.left.right = Node(40)
root.left.right = Node(50)
root.right.left = Node(60)
root.right.right = Node(70)
insertChildrenCount(root)
print("A Random Node From Tree :",
randomNode(root))
# This code is contributed by Rituraj Jain
C#
// C# program to Select a Random Node from a tree
using System;
class GFG
{
class Node
{
public int data;
public int children;
public Node left, right;
}
static Node newNode(int data)
{
Node temp = new Node();
temp.data = data;
temp.left = temp.right = null;
temp.children = 0;
return temp;
}
// This is used to fill children counts.
static int getElements(Node root)
{
if (root == null)
return 0;
return getElements(root.left) +
getElements(root.right) + 1;
}
// Inserts Children count for each node
static Node insertChildrenCount(Node root)
{
if (root == null)
return null;
root.children = getElements(root) - 1;
root.left = insertChildrenCount(root.left);
root.right = insertChildrenCount(root.right);
return root;
}
// returns number of children for root
static int children(Node root)
{
if (root == null)
return 0;
return root.children + 1;
}
// Helper Function to return a random node
static int randomNodeUtil(Node root, int count)
{
if (root == null)
return 0;
if (count == children(root.left))
return root.data;
if (count < children(root.left))
return randomNodeUtil(root.left, count);
return randomNodeUtil(root.right,
count - children(root.left) - 1);
}
// Returns Random node
static int randomNode(Node root)
{
int count = (int) new Random().Next(0, root.children + 1);
return randomNodeUtil(root, count);
}
// Driver Code
public static void Main(String []args)
{
// Creating Above Tree
Node root = newNode(10);
root.left = newNode(20);
root.right = newNode(30);
root.left.right = newNode(40);
root.left.right = newNode(50);
root.right.left = newNode(60);
root.right.right = newNode(70);
insertChildrenCount(root);
Console.Write( "A Random Node From Tree : " +
randomNode(root));
}
}
// This code is contributed by Arnab Kundu
Javascript
<script>
// JavaScript program to Select a Random Node from a tree
class Node
{
constructor(data)
{
this.data=data;
this.left=this.right=null;
this.children = 0;
}
}
// This is used to fill children counts.
function getElements(root)
{
if (root == null)
return 0;
return getElements(root.left) +
getElements(root.right) + 1;
}
// Inserts Children count for each node
function insertChildrenCount(root)
{
if (root == null)
return null;
root.children = getElements(root) - 1;
root.left = insertChildrenCount(root.left);
root.right = insertChildrenCount(root.right);
return root;
}
// returns number of children for root
function children(root)
{
if (root == null)
return 0;
return root.children + 1;
}
// Helper Function to return a random node
function randomNodeUtil(root,count)
{
if (root == null)
return 0;
if (count == children(root.left))
return root.data;
if (count < children(root.left))
return randomNodeUtil(root.left, count);
return randomNodeUtil(root.right,
count - children(root.left) - 1);
}
// Returns Random node
function randomNode(root)
{
let count = Math.floor(Math.random() *
(root.children + 1));
return randomNodeUtil(root, count);
}
// Driver Code
// Creating Above Tree
let root = new Node(10);
root.left = new Node(20);
root.right = new Node(30);
root.left.right = new Node(40);
root.left.right = new Node(50);
root.right.left = new Node(60);
root.right.right = new Node(70);
insertChildrenCount(root);
document.write( "A Random Node From Tree : " +
randomNode(root)+"<br>");
// This code is contributed by avanitrachhadiya2155
</script>
La complejidad temporal de randomNode es O(h) donde h es la altura del árbol. Tenga en cuenta que nos estamos moviendo hacia la derecha o hacia la izquierda a la vez.
Publicación traducida automáticamente
Artículo escrito por Aashish Chauhan y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA