Ya hemos discutido la idea de Skip list y cómo funcionan en Skip List | Serie 1 (Introducción) . En este artículo, discutiremos cómo insertar un elemento en la lista Omitir.
Decidir el nivel de los Nodes
Cada elemento de la lista está representado por un Node, el nivel del Node se elige aleatoriamente mientras se inserta en la lista. El nivel no depende del número de elementos en el Node. El nivel para el Node se decide mediante el siguiente algoritmo:
randomLevel() lvl := 1 //random() that returns a random value in [0...1) while random() < p and lvl < MaxLevel do lvl := lvl + 1 return lvl
MaxLevel es el límite superior del número de niveles en la lista de omisión. Se puede determinar como – 
. El algoritmo anterior asegura que el nivel aleatorio nunca será mayor que MaxLevel. Aquí p es la fracción de los Nodes con punteros de nivel i que también tienen punteros de nivel i+1 y N es el número de Nodes en la lista.
Estructura del Node
Cada Node lleva una clave y una array directa que lleva punteros a Nodes de un nivel diferente. Un Node de nivel i transporta punteros i hacia delante indexados de 0 a i.
Inserción en la lista de saltos
Comenzaremos desde el nivel más alto de la lista y compararemos la clave del siguiente Node del Node actual con la clave que se insertará. La idea básica es Si –
- La clave del siguiente Node es menor que la clave que se insertará, luego seguimos avanzando en el mismo nivel
- La clave del siguiente Node es mayor que la clave que se insertará, luego almacenamos el puntero al Node actual i en la actualización [i] y bajamos un nivel y continuamos nuestra búsqueda.
En el nivel 0, definitivamente encontraremos una posición para insertar la clave dada. A continuación se muestra el pseudocódigo para el algoritmo de inserción:
Insert(list, searchKey)
local update[0...MaxLevel+1]
x := list -> header
for i := list -> level downto 0 do
while x -> forward[i] -> key forward[i]
update[i] := x
x := x -> forward[0]
lvl := randomLevel()
if lvl > list -> level then
for i := list -> level + 1 to lvl do
update[i] := list -> header
list -> level := lvl
x := makeNode(lvl, searchKey, value)
for i := 0 to level do
x -> forward[i] := update[i] -> forward[i]
update[i] -> forward[i] := x
Aquí update[i] mantiene el puntero al Node en el nivel i desde el cual bajamos al nivel i-1 y el puntero del Node a la izquierda en la posición de inserción en el nivel 0. Considere este ejemplo donde queremos insertar la clave 17 –
El siguiente es el código para la inserción de la clave en la lista Omitir –
C++
// C++ code for inserting element in skip list
#include <bits/stdc++.h>
using namespace std;
// Class to implement node
class Node
{
public:
int key;
// Array to hold pointers to node of different level
Node **forward;
Node(int, int);
};
Node::Node(int key, int level)
{
this->key = key;
// Allocate memory to forward
forward = new Node*[level+1];
// Fill forward array with 0(NULL)
memset(forward, 0, sizeof(Node*)*(level+1));
};
// Class for Skip list
class SkipList
{
// Maximum level for this skip list
int MAXLVL;
// P is the fraction of the nodes with level
// i pointers also having level i+1 pointers
float P;
// current level of skip list
int level;
// pointer to header node
Node *header;
public:
SkipList(int, float);
int randomLevel();
Node* createNode(int, int);
void insertElement(int);
void displayList();
};
SkipList::SkipList(int MAXLVL, float P)
{
this->MAXLVL = MAXLVL;
this->P = P;
level = 0;
// create header node and initialize key to -1
header = new Node(-1, MAXLVL);
};
// create random level for node
int SkipList::randomLevel()
{
float r = (float)rand()/RAND_MAX;
int lvl = 0;
while (r < P && lvl < MAXLVL)
{
lvl++;
r = (float)rand()/RAND_MAX;
}
return lvl;
};
// create new node
Node* SkipList::createNode(int key, int level)
{
Node *n = new Node(key, level);
return n;
};
// Insert given key in skip list
void SkipList::insertElement(int key)
{
Node *current = header;
// create update array and initialize it
Node *update[MAXLVL+1];
memset(update, 0, sizeof(Node*)*(MAXLVL+1));
/* start from highest level of skip list
move the current pointer forward while key
is greater than key of node next to current
Otherwise inserted current in update and
move one level down and continue search
*/
for (int i = level; i >= 0; i--)
{
while (current->forward[i] != NULL &&
current->forward[i]->key < key)
current = current->forward[i];
update[i] = current;
}
/* reached level 0 and forward pointer to
right, which is desired position to
insert key.
*/
current = current->forward[0];
/* if current is NULL that means we have reached
to end of the level or current's key is not equal
to key to insert that means we have to insert
node between update[0] and current node */
if (current == NULL || current->key != key)
{
// Generate a random level for node
int rlevel = randomLevel();
// If random level is greater than list's current
// level (node with highest level inserted in
// list so far), initialize update value with pointer
// to header for further use
if (rlevel > level)
{
for (int i=level+1;i<rlevel+1;i++)
update[i] = header;
// Update the list current level
level = rlevel;
}
// create new node with random level generated
Node* n = createNode(key, rlevel);
// insert node by rearranging pointers
for (int i=0;i<=rlevel;i++)
{
n->forward[i] = update[i]->forward[i];
update[i]->forward[i] = n;
}
cout << "Successfully Inserted key " << key << "\n";
}
};
// Display skip list level wise
void SkipList::displayList()
{
cout<<"\n*****Skip List*****"<<"\n";
for (int i=0;i<=level;i++)
{
Node *node = header->forward[i];
cout << "Level " << i << ": ";
while (node != NULL)
{
cout << node->key<<" ";
node = node->forward[i];
}
cout << "\n";
}
};
// Driver to test above code
int main()
{
// Seed random number generator
srand((unsigned)time(0));
// create SkipList object with MAXLVL and P
SkipList lst(3, 0.5);
lst.insertElement(3);
lst.insertElement(6);
lst.insertElement(7);
lst.insertElement(9);
lst.insertElement(12);
lst.insertElement(19);
lst.insertElement(17);
lst.insertElement(26);
lst.insertElement(21);
lst.insertElement(25);
lst.displayList();
}
Java
// Java code for inserting element in skip list
class GFG {
// Class to implement node
static class Node {
int key;
// Array to hold pointers to node of different level
Node forward[];
Node(int key, int level)
{
this.key = key;
// Allocate memory to forward
forward = new Node[level + 1];
}
};
// Class for Skip list
static class SkipList {
// Maximum level for this skip list
int MAXLVL;
// P is the fraction of the nodes with level
// i pointers also having level i+1 pointers
float P;
// current level of skip list
int level;
// pointer to header node
Node header;
SkipList(int MAXLVL, float P)
{
this.MAXLVL = MAXLVL;
this.P = P;
level = 0;
// create header node and initialize key to -1
header = new Node(-1, MAXLVL);
}
int randomLevel()
{
float r = (float)Math.random();
int lvl = 0;
while (r < P && lvl < MAXLVL) {
lvl++;
r = (float)Math.random();
}
return lvl;
}
Node createNode(int key, int level)
{
Node n = new Node(key, level);
return n;
}
// Insert given key in skip list
void insertElement(int key)
{
Node current = header;
// create update array and initialize it
Node update[] = new Node[MAXLVL + 1];
/* start from highest level of skip list
move the current pointer forward while
key is greater than key of node next to
current Otherwise inserted current in update
and move one level down and continue search
*/
for (int i = level; i >= 0; i--) {
while (current.forward[i] != null
&& current.forward[i].key < key)
current = current.forward[i];
update[i] = current;
}
/* reached level 0 and forward pointer to
right, which is desired position to
insert key.
*/
current = current.forward[0];
/* if current is NULL that means we have reached
to end of the level or current's key is not
equal to key to insert that means we have to
insert node between update[0] and current node
*/
if (current == null || current.key != key) {
// Generate a random level for node
int rlevel = randomLevel();
// If random level is greater than list's
// current level (node with highest level
// inserted in list so far), initialize
// update value with pointer to header for
// further use
if (rlevel > level) {
for (int i = level + 1; i < rlevel + 1;
i++)
update[i] = header;
// Update the list current level
level = rlevel;
}
// create new node with random level
// generated
Node n = createNode(key, rlevel);
// insert node by rearranging pointers
for (int i = 0; i <= rlevel; i++) {
n.forward[i] = update[i].forward[i];
update[i].forward[i] = n;
}
System.out.println(
"Successfully Inserted key " + key);
}
}
// Display skip list level wise
void displayList()
{
System.out.println("\n*****Skip List*****");
for (int i = 0; i <= level; i++) {
Node node = header.forward[i];
System.out.print("Level " + i + ": ");
while (node != null) {
System.out.print(node.key + " ");
node = node.forward[i];
}
System.out.println();
}
}
}
// Driver to test above code
public static void main(String[] args)
{
// create SkipList object with MAXLVL and P
SkipList lst = new SkipList(3, 0.5f);
lst.insertElement(3);
lst.insertElement(6);
lst.insertElement(7);
lst.insertElement(9);
lst.insertElement(12);
lst.insertElement(19);
lst.insertElement(17);
lst.insertElement(26);
lst.insertElement(21);
lst.insertElement(25);
lst.displayList();
}
}
// This code is contributed by Lovely Jain
Python
# Python3 code for inserting element in skip list
import random
class Node(object):
'''
Class to implement node
'''
def __init__(self, key, level):
self.key = key
# list to hold references to node of different level
self.forward = [None]*(level+1)
class SkipList(object):
'''
Class for Skip list
'''
def __init__(self, max_lvl, P):
# Maximum level for this skip list
self.MAXLVL = max_lvl
# P is the fraction of the nodes with level
# i references also having level i+1 references
self.P = P
# create header node and initialize key to -1
self.header = self.createNode(self.MAXLVL, -1)
# current level of skip list
self.level = 0
# create new node
def createNode(self, lvl, key):
n = Node(key, lvl)
return n
# create random level for node
def randomLevel(self):
lvl = 0
while random.random()<self.P and \
lvl<self.MAXLVL:lvl += 1
return lvl
# insert given key in skip list
def insertElement(self, key):
# create update array and initialize it
update = [None]*(self.MAXLVL+1)
current = self.header
'''
start from highest level of skip list
move the current reference forward while key
is greater than key of node next to current
Otherwise inserted current in update and
move one level down and continue search
'''
for i in range(self.level, -1, -1):
while current.forward[i] and \
current.forward[i].key < key:
current = current.forward[i]
update[i] = current
'''
reached level 0 and forward reference to
right, which is desired position to
insert key.
'''
current = current.forward[0]
'''
if current is NULL that means we have reached
to end of the level or current's key is not equal
to key to insert that means we have to insert
node between update[0] and current node
'''
if current == None or current.key != key:
# Generate a random level for node
rlevel = self.randomLevel()
'''
If random level is greater than list's current
level (node with highest level inserted in
list so far), initialize update value with reference
to header for further use
'''
if rlevel > self.level:
for i in range(self.level+1, rlevel+1):
update[i] = self.header
self.level = rlevel
# create new node with random level generated
n = self.createNode(rlevel, key)
# insert node by rearranging references
for i in range(rlevel+1):
n.forward[i] = update[i].forward[i]
update[i].forward[i] = n
print("Successfully inserted key {}".format(key))
# Display skip list level wise
def displayList(self):
print("\n*****Skip List******")
head = self.header
for lvl in range(self.level+1):
print("Level {}: ".format(lvl), end=" ")
node = head.forward[lvl]
while(node != None):
print(node.key, end=" ")
node = node.forward[lvl]
print("")
# Driver to test above code
def main():
lst = SkipList(3, 0.5)
lst.insertElement(3)
lst.insertElement(6)
lst.insertElement(7)
lst.insertElement(9)
lst.insertElement(12)
lst.insertElement(19)
lst.insertElement(17)
lst.insertElement(26)
lst.insertElement(21)
lst.insertElement(25)
lst.displayList()
main()
Producción
Successfully Inserted key 3 Successfully Inserted key 6 Successfully Inserted key 7 Successfully Inserted key 9 Successfully Inserted key 12 Successfully Inserted key 19 Successfully Inserted key 17 Successfully Inserted key 26 Successfully Inserted key 21 Successfully Inserted key 25 *****Skip List***** Level 0: 3 6 7 9 12 17 19 21 25 26 Level 1: 3 6 12 17 25 26 Level 2: 3 6 12 25 Level 3: 3 25
Nota: el nivel de los Nodes se decide aleatoriamente, por lo que la salida puede diferir.
Complejidad del tiempo
- Promedio:
- Lo peor:
en el próximo artículo, analizaremos la búsqueda y la eliminación en la lista de omisión.
Este artículo es una contribución de Atul Kumar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA