El algoritmo de puntero de salto es una técnica de diseño para algoritmos paralelos que operan en estructuras de puntero, como arrays o listas enlazadas. Este algoritmo se utiliza normalmente para determinar la raíz del bosque de un árbol enraizado.
En el algoritmo de puntero de salto, procesamos previamente un árbol para que uno pueda responder a las consultas para encontrar cualquier padre de cualquier Node en el árbol en la complejidad de tiempo de O(log n) .
El algoritmo de puntero de salto asocia hasta log 2 n punteros a cada vértice del árbol. Estos punteros se denominan punteros de salto porque saltan por el árbol hacia el Node raíz del árbol. Para cualquier Node del árbol de procesamiento, el algoritmo almacena una array de puentes de longitud l donde l = log2(profundidad(v)) . El i-ésimo elemento de esta array apunta al 2-ésimo padre del Node v . Esta estructura de datos nos ayuda a saltar hasta la mitad del árbol desde cualquier Node dado. Cuando se le pide al algoritmo que procese una consulta para encontrar cualquier padre de cualquier Node en el árbol, saltamos repetidamente hacia arriba en el árbol usando estos punteros. El número de saltos será como máximo log ny, por lo tanto, cualquier problema para encontrar el padre de cualquier Node en el árbol se puede responder en una complejidad de tiempo O (log n) .
En el puntero de salto, hay un puntero del Node N al padre j-ésimo de N, para
j = 1, 2, 4, 8, …, y así sucesivamente. Entonces almacenamos 2 i-ésimo padre de cada Node.
El algoritmo del puntero de salto básicamente funciona con el enfoque de la programación dinámica en la que usamos el resultado precalculado para encontrar el siguiente resultado . Haciendo algunos cálculos simples podemos calcular la fórmula matemática que para cualquier Node k, 2 j -th padre de k es igual a 2 j- 1th padre de 2 j- 1th padre de k .
La breve explicación de esta fórmula se da a continuación en la sección del algoritmo.
El uso más común de este algoritmo es para resolver las consultas en las que necesitamos encontrar el ancestro de cualquier Node en complejidad de tiempo O(log n).
Gráfico para implementar el algoritmo de puntero de salto:
Representación de la array de salto que almacena el padre 2^ith de todos los Nodes:
Ejemplos:
Input: 0th parent of node 2 Output: 0th parent of node 2 is = 2 Input: 2th parent of node 4 Output: 2th parent of node 4 is = 2 Input: 3rd parent of node 8 Output: 3rd parent of node 8 is = 1
Algoritmo :
aquí está el algoritmo para implementar el algoritmo de puntero de salto para encontrar cualquier padre de cualquier Node en el gráfico. Determinamos la array de salto usando programación dinámica . Aquí, denotamos el Node raíz como R e inicialmente asumimos que el padre del Node raíz es 0, lo que significa que no hay padre de este Node . Ahora, mirando el gráfico y la array que se muestra en el diagrama anterior, podemos entender fácilmente la fórmula anterior para determinar el 2 i th padre de cada Node. Si miramos el Node con valor 8, podemos ver que su padre 2 0 es 10 , ahora para encontrar su padre 2 1 vemos que su padre 2 1 es 2 0th padre del Node con valor 10 y aquí 10 es 2 0 th padre de 8 significa que 2 1 th padre de Node 8 es 2 0 th padre de 2 0 th padre de Node 8 . Del mismo modo, también podemos ver que 2 2 th padre del Node 8 es 5, que es 2 1 th padre del 2 1 th padre del Node 8, es decir, 2 1 th padre del Node con valor 9 .
Así, de esta manera, podemos calcular la array de punteros de salto para que todos los Nodes almacenen sus 2i- ésimos padres.
A continuación se muestra el pseudocódigo para calcular la array de punteros de salto que almacena el 2 i ésimo padre de todos los Nodes en el árbol.
jump[k][j] = it points 2^jth parent of k
= 2^j-1th parent of (2^j-1th parent of k)
= jump[jump[i][j-1][j-1]
Implementación : a continuación se muestra el código para implementar el algoritmo anterior para encontrar cualquier padre de cualquier Node en la complejidad de tiempo O (logn).
C++
// C++ program to implement Jump pointer algorithm
#include <bits/stdc++.h>
using namespace std;
int R = 0;
// n -> it represent total number of nodes
// len -> it is the maximum length of array
// to hold parent of each node.
// In worst case, the highest value of
// parent a node can have is n-1.
// 2 ^ len <= n-1
// len = O(log2n)
int getLen(int n)
{
int len = (int)(log(n) / log(2)) + 1;
return len;
}
// jump represent 2D matrix to hold parent of node in jump matrix
// here we pass reference of 2D matrix so that the change made
// occur directly to the original matrix
// len is same as defined above
// n is total nodes in graph
void set_jump_pointer(vector<vector<int> >& jump,
vector<int> node, int len, int n)
{
for (int j = 1; j <= len; j++)
for (int i = 0; i < n; i++)
jump[ node[i] ][j] = jump[jump[node[i] ][j - 1] ][j - 1];
}
// c -> it represent child
// p -> it represent parent
// i -> it represent node number
// p=0 means the node is root node
// here also we pass reference of 2D matrix
// and depth vector so that the change made
// occur directly to the original matrix and original vector
void constructGraph(vector<vector<int> >& jump,
vector<int>& node, vector<int>& isNode, int c, int p, int i)
{
// enter the node in node array
// it stores all the nodes in the graph
node[i] = c;
// to confirm that no child node have 2 parents
if (isNode == 0) {
isNode = 1;
// make parent of x as y
jump[0] = p;
}
return;
}
// function to jump to Lth parent of any node
void jumpPointer(vector<vector<int> >& jump,
vector<int> isNode, int x, int L, int n)
{
int j = 0, curr = x, k = L;
// to check if node is present in graph or not
if (x > n || isNode[x] == 0) {
cout << "Node is not present in graph " << endl;
return;
}
// in this loop we decrease the value of L by L/2 and
// increment j by 1 after each iteration, and check for set bit
// if we get set bit then we update x with jth parent of x
// as L becomes less than or equal to zero means
// we have jumped to Lth parent of node x
while (L > 0) {
// to check if last bit is 1 or not
if (L & 1)
x = jump[x][j];
// use of shift operator to make
// L = L/2 after every iteration
L = L >> 1;
j++;
}
cout << k << "th parent of node " << curr
<< " is = " << x << endl;
return;
}
// Driver code
int main()
{
// n represent number of nodes
int n = 11;
// function to calculate len
// len -> it is the maximum length of
// array to hold parent of each node.
int len = getLen(n);
// initialization of parent matrix
vector<vector<int> > jump(n+1, vector<int>(len+1));
// node array is used to store all nodes
vector<int> node(n+1);
// isNode is an array to check whether
// a node is present in graph or not
vector<int> isNode(n+1,0);
// R stores root node
R = 2;
// construction of graph
// here 0 represent that the node is root node
constructGraph(jump, node, isNode, 2, 0, 0);
constructGraph(jump, node, isNode, 5, 2, 1);
constructGraph(jump, node, isNode, 3, 5, 2);
constructGraph(jump, node, isNode, 4, 5, 3);
constructGraph(jump, node, isNode, 1, 5, 4);
constructGraph(jump, node, isNode, 7, 1, 5);
constructGraph(jump, node, isNode, 9, 1, 6);
constructGraph(jump, node, isNode, 10, 9, 7);
constructGraph(jump, node, isNode, 11, 10, 8);
constructGraph(jump, node, isNode, 6, 10, 9);
constructGraph(jump, node, isNode, 8, 10, 10);
// function to pre compute jump matrix
set_jump_pointer(jump, node, len, n);
// query to jump to parent using jump pointers
// query to jump to 1st parent of node 2
jumpPointer(jump, isNode, 2, 0, n);
// query to jump to 2nd parent of node 4
jumpPointer(jump, isNode, 4, 2, n);
// query to jump to 3rd parent of node 8
jumpPointer(jump, isNode, 8, 3, n);
// query to jump to 5th parent of node 20
jumpPointer(jump, isNode, 20, 5, n);
return 0;
}
Python3
# Python3 program to implement
# Jump pointer algorithm
import math
# Initialization of parent matrix
# suppose max range of a node is
# up to 1000 if there are 1000 nodes
# than also length of jump matrix
# will not exceed 10
jump = [[0 for j in range(10)]
for i in range(1000)]
# Node array is used to store all nodes
node = [0 for i in range(1000)]
# isNode is an array to check whether
# a node is present in graph or not
isNode = [0 for i in range(1000)]
# n -> it represent total number of nodes
# len -> it is the maximum length of array
# to hold parent of each node.
# In worst case, the highest value of
# parent a node can have is n-1.
# 2 ^ len <= n-1
# len = O(log2n)
def getLen(n):
len = int((math.log(n)) //
(math.log(2))) + 1
return len
# jump represent 2D matrix to hold parent
# of node in jump matrix here we pass
# reference of 2D matrix so that the
# change made occur directly to the
# original matrix len is same as
# defined above n is total nodes
# in graph
def set_jump_pointer(len, n):
global jump, node
for j in range(1,len + 1):
for i in range(0, n):
jump[node[i]][j] = jump[jump[node[i]][j - 1]][j - 1]
# c -> it represent child
# p -> it represent parent
# i -> it represent node number
# p=0 means the node is root node
# here also we pass reference of
# 2D matrix and depth vector so
# that the change made occur
# directly to the original matrix
# and original vector
def constructGraph(c, p, i):
global jump, node, isNode
# Enter the node in node array
# it stores all the nodes in the graph
node[i] = c
# To confirm that no child node
# have 2 parents
if (isNode == 0):
isNode = 1
# Make parent of x as y
jump[0] = p
return
# function to jump to Lth parent
# of any node
def jumpPointer(x, L):
j = 0
n = x
k = L
global jump, isNode
# To check if node is present in
# graph or not
if (isNode[x] == 0):
print("Node is not present in graph ")
return
# In this loop we decrease the value
# of L by L/2 and increment j by 1
# after each iteration, and check
# for set bit if we get set bit
# then we update x with jth parent
# of x as L becomes less than or
# equal to zero means we have
# jumped to Lth parent of node x
while (L > 0):
# To check if last bit is 1 or not
if ((L & 1)!=0):
x = jump[x][j]
# Use of shift operator to make
# L = L/2 after every iteration
L = L >> 1
j += 1
print(str(k) + "th parent of node " +
str(n) + " is = " + str(x))
return
# Driver code
if __name__=="__main__":
# n represent number of nodes
n = 11
# Function to calculate len
# len -> it is the maximum length of
# array to hold parent of each node.
len = getLen(n)
# R stores root node
R = 2
# Construction of graph
# here 0 represent that
# the node is root node
constructGraph(2, 0, 0)
constructGraph(5, 2, 1)
constructGraph(3, 5, 2)
constructGraph(4, 5, 3)
constructGraph(1, 5, 4)
constructGraph(7, 1, 5)
constructGraph(9, 1, 6)
constructGraph(10, 9, 7)
constructGraph(11, 10, 8)
constructGraph(6, 10, 9)
constructGraph(8, 10, 10)
# Function to pre compute jump matrix
set_jump_pointer(len, n)
# Query to jump to parent using jump pointers
# query to jump to 1st parent of node 2
jumpPointer(2, 0)
# Query to jump to 2nd parent of node 4
jumpPointer(4, 2)
# Query to jump to 3rd parent of node 8
jumpPointer(8, 3)
# Query to jump to 5th parent of node 20
jumpPointer(20, 5)
# This code is contributed by rutvik_56
0th parent of node 2 is = 2 2th parent of node 4 is = 2 3th parent of node 8 is = 1 Node is not present in graph
Complejidad de tiempo: O(logN) por consulta
Espacio auxiliar: O(N * logN)
Publicación traducida automáticamente
Artículo escrito por Aman Goyal 2 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA