Omitir lista | Conjunto 3 (Búsqueda y Eliminación)

En el artículo anterior Saltar lista | Conjunto 2 (Inserción) discutimos la estructura de los Nodes de omisión y cómo insertar un elemento en la lista de omisión. En este artículo discutiremos cómo buscar y eliminar un elemento de la lista de omisión.

Buscar un elemento en la lista de saltos

La búsqueda de un elemento es muy similar al enfoque para buscar un lugar para insertar un elemento en la lista Omitir. La idea básica es si –

  1. La clave del siguiente Node es menor que la clave de búsqueda, luego seguimos avanzando en el mismo nivel.
  2. 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 más bajo (0), si el elemento al lado del elemento más a la derecha (actualización [0]) tiene una clave igual a la clave de búsqueda, entonces hemos encontrado la clave; de ​​lo contrario, falla. A continuación se muestra el pseudocódigo para el elemento de búsqueda:

Search(list, searchKey)
x := list -> header
-- loop invariant: x -> key  level downto 0 do
    while x -> forward[i] -> key  forward[i]
x := x -> forward[0]
if x -> key = searchKey then return x -> value
else return failure

Considere este ejemplo donde queremos buscar la clave 17- 

searching key

Eliminación de un elemento de la lista Omitir

La eliminación de un elemento k está precedida por la ubicación del elemento en la lista Omitir utilizando el algoritmo de búsqueda mencionado anteriormente. Una vez que se encuentra el elemento, se reorganizan los punteros para eliminar la lista de formularios de elementos, tal como lo hacemos en la lista de enlaces individuales. Comenzamos desde el nivel más bajo y reorganizamos hasta que el elemento al lado de la actualización [i] no es k. Después de la eliminación del elemento, podría haber niveles sin elementos, por lo que también eliminaremos estos niveles al disminuir el nivel de la lista Omitir. A continuación se muestra el pseudocódigo para la eliminación:

Delete(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]
if x -> key = searchKey then
    for i := 0 to list -> level do
        if update[i] -> forward[i] ≠ x then break
        update[i] -> forward[i] := x -> forward[i]
    free(x)
    while list -> level > 0 and list -> header -> forward[list -> level] = NIL do
        list -> level := list -> level – 1

Considere este ejemplo en el que queremos eliminar el elemento 6: 

deletion

Aquí, en el nivel 3, no hay ningún elemento (flecha en rojo) después de eliminar el elemento 6. Por lo tanto, disminuiremos el nivel de la lista de omisiones en 1. A continuación se muestra el código para buscar y eliminar elementos de la lista de omisiones: 

Implementación:

C++

// C++ code for searching and deleting 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 deleteElement(int);
    void searchElement(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";
    }
};
  
// Delete element from skip list
void SkipList::deleteElement(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 possibly our desired node.*/
    current = current->forward[0];
  
    // If current node is target node
    if(current != NULL and current->key == key)
    {
        /* start from lowest level and rearrange
           pointers just like we do in singly linked list
           to remove target node */
        for(int i=0;i<=level;i++)
        {
            /* If at level i, next node is not target 
               node, break the loop, no need to move 
              further level */
            if(update[i]->forward[i] != current)
                break;
  
            update[i]->forward[i] = current->forward[i];
        }
  
        // Remove levels having no elements 
        while(level>0 &&
              header->forward[level] == 0)
            level--;
         cout<<"Successfully deleted key "<<key<<"\n";
    }
};
  
// Search for element in skip list
void SkipList::searchElement(int key)
{
    Node *current = header;
  
    /*    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] &&
               current->forward[i]->key < key)
            current = current->forward[i];
  
    }
  
    /* reached level 0 and advance pointer to 
       right, which is possibly our desired node*/
    current = current->forward[0];
  
    // If current node have key equal to
    // search key, we have found our target node
    if(current and current->key == key) 
        cout<<"Found 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();
  
    //Search for node 19
    lst.searchElement(19);
  
    //Delete node 19
    lst.deleteElement(19);
    lst.displayList();
}

Python

# Python3 code for searching and deleting 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))
  
    def deleteElement(self, search_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 < search_key):
                current = current.forward[i]
            update[i] = current
  
        ''' 
        reached level 0 and advance reference to 
        right, which is possibly our desired node
        ''' 
        current = current.forward[0]
  
        # If current node is target node
        if current != None and current.key == search_key:
  
            '''
            start from lowest level and rearrange references 
            just like we do in singly linked list
            to remove target node
            '''
            for i in range(self.level+1):
  
                '''
                If at level i, next node is not target 
                node, break the loop, no need to move 
                further level
                '''
                if update[i].forward[i] != current:
                    break
                update[i].forward[i] = current.forward[i]
  
            # Remove levels having no elements
            while(self.level>0 and\
                  self.header.forward[self.level] == None):
                self.level -= 1
            print("Successfully deleted {}".format(search_key))
  
    def searchElement(self, key): 
        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]
  
        # reached level 0 and advance reference to 
        # right, which is possibly our desired node
        current = current.forward[0]
  
        # If current node have key equal to
        # search key, we have found our target node
        if current and current.key == key:
            print("Found key ", 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()
  
    # Search for node 19
    lst.searchElement(19)
  
    # Delete node 19
    lst.deleteElement(19)
    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: 6 9 19 26 
Level 2: 19 
Found key: 19
Successfully deleted key 19

*****Skip List*****
Level 0: 3 6 7 9 12 17 21 25 26 
Level 1: 6 9 26 

Complete Interview Preparation - GFG

La complejidad temporal de la búsqueda y la eliminación es la misma – Complejidad temporal Peor caso:

  • Acceso – O(n)
  • Busca en)
  • Insertar – O(n)
  • Espacio – O (inicio de sesión)
  • Borrar – O(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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *