Bloqueo y desbloqueo de recursos organizados en forma de árbol n-ario

Dado un árbol n-ario de recursos dispuestos jerárquicamente de tal manera que la altura del árbol es O (Log N) donde N es el número total de Nodes (o recursos). Un proceso necesita bloquear un Node de recursos para poder usarlo. Pero un Node no puede bloquearse si alguno de sus descendientes o antecesores está bloqueado. 
Se requieren las siguientes operaciones para un Node de recursos dado: 
 

• islock()- devuelve verdadero si un Node determinado está bloqueado y falso si no lo está. Un Node está bloqueado si lock() se ha ejecutado correctamente para el Node.
• Lock(): bloquea el Node dado si es posible y actualiza la información de bloqueo. El bloqueo solo es posible si los ancestros y los descendientes del Node actual no están bloqueados.
• unLock()- desbloquea el Node y actualiza la información.

Cómo diseñar Nodes de recursos e implementar las operaciones anteriores de manera que se logren las siguientes complejidades de tiempo. 
 

    islock()  O(1)
    Lock()    O(log N)
    unLock()  O(log N)

Le recomendamos encarecidamente que minimice su navegador y que pruebe esto usted mismo primero.  
Se da que los recursos deben almacenarse en forma de árbol n-ario. Ahora la pregunta es cómo aumentar el árbol para lograr los límites de complejidad anteriores. 

Algunas preguntas generales:

Q1. ¿Por qué establecer Lock = true solo no resuelve el propósito?
A1. Porque para los enfoques en los que nos movemos hacia el padre para verificar si el bloqueo es posible si llega una solicitud para cualquier Node entre un Node bloqueado y la raíz, entonces no hay forma de saber que un Node descendiente está bloqueado. Por lo tanto, se utilizan variables como isLockable para mantener esta información.

Q2. ¿Por qué no bloquear todos los Nodes desde el Node actual hasta la raíz?
A2. Porque el bloqueo, en general, es una operación que consume muchos recursos y realizar el bloqueo de todos los Nodes hasta la raíz sería una pérdida de recursos. Por lo tanto, se utilizan soluciones ligeras como la introducción de una variable isLockable.

Método 1 (Simple)
Una solución simple es almacenar una variable booleana isLocked con cada Node de recursos. La variable booleana isLocked es verdadera si el Node actual está bloqueado; de lo contrario, es falsa. 
Veamos cómo funcionan las operaciones usando este enfoque. 
 

• isLock(): Comprobar isLocked del Node dado.
• Lock(): si isLocked está configurado, entonces el Node no se puede bloquear. De lo contrario, verifique todos los descendientes y ancestros del Node y si alguno de ellos está bloqueado, entonces este Node tampoco se puede bloquear. Si ninguna de las condiciones anteriores es verdadera, bloquee este Node configurando isLocked como verdadero.
• unLock(): si isLocked de un Node dado es falso, no hay nada que hacer. De lo contrario, establezca isLocked como falso.

Complejidades de tiempo: 

isLock()  O(1) 
Lock()    O(N)
unLock()  O(1)

Lock is O(N) because there can be O(N) descendants. 

  
Método 2 (Complejidades de tiempo según la pregunta) 
La idea es aumentar el árbol con los siguientes tres campos: 
 

1. Un campo booleano está bloqueado (igual que el método anterior).
2. Parent-Pointer para acceder a todos los ancestros en tiempo O(Log n).
3. Recuento de descendientes bloqueados . Tenga en cuenta que un Node puede ser antepasado de muchos descendientes. Podemos verificar si alguno de los descendientes está bloqueado usando este conteo.

Veamos cómo funcionan las operaciones usando este Enfoque. 
 

• isLock(): Comprobar isLocked del Node dado.
• Lock(): Atraviesa todos los ancestros. Si ninguno de los ancestros está bloqueado, el recuento de descendientes bloqueados es 0 e isLocked es falso, establezca isLocked del Node actual como verdadero. E incremente el recuento de descendientes bloqueados para todos los antepasados. La complejidad del tiempo es O (Log N) ya que puede haber como máximo O (Log N) antepasados.
• unLock(): recorrer todos los ancestros y disminuir el recuento de descendientes bloqueados para todos los ancestros. Establezca isLocked del Node actual como falso. La complejidad del tiempo es O (Log N)

Gracias a Utkarsh Trivedi por sugerir este enfoque. 

Método 3 (Complejidades de tiempo según la pregunta y mejor uso de la memoria) La idea es aumentar el árbol con los siguientes tres campos:

1. Un campo booleano está bloqueado (igual que el método anterior).
2. Parent-Pointer para acceder a todos los ancestros en tiempo O(Log n).
3. es bloqueable. Podemos verificar si alguno de los descendientes está bloqueado usando esta variable. isLockable es verdadero si ninguno de los descendientes está bloqueado; de lo contrario, es falso.

Veamos cómo funcionan las operaciones usando este Enfoque.

• isLock(): Comprobar isLocked del Node dado.
• Lock(): Atraviesa todos los ancestros. Si ninguno de los ancestros está bloqueado, isLockable es verdadero e isLocked es falso, establezca isLocked del Node actual como verdadero. Y marque isLockable como falso para todos los antepasados. La complejidad del tiempo es O (Log N) ya que puede haber como máximo O (Log N) antepasados.
• unLock(): recorrer todos los ancestros y marcar isLockable como verdadero para todos los ancestros. Establezca isLocked del Node actual como falso. La complejidad del tiempo es O (Log N)

#include <bits/stdc++.h>
using namespace std;
 
class narytree {
public:
    bool isLock;
    bool isLockable;
    narytree* parent;
    vector<narytree*> children;
    narytree()
    {
        isLock = false;
        isLockable = true;
        parent = NULL;
    }
    narytree(narytree* parent)
    {
        isLock = false;
        isLockable = true;
        this->parent = parent;
    }
};
 
bool isLock(narytree* node) { return node->isLock; }
 
void Lock(narytree* node)
{
    if (node->isLockable == false)
        return;
 
    narytree* T = node;
    bool flag = false;
    while (T != NULL) {
        if (T->isLock == true) {
            flag = true;
            break;
        }
        T = T->parent;
    }
    if (flag)
        return;
    else {
        node->isLock = true;
        T = node;
        // marking isLockable as false for ancestor nodes.
        while (T != NULL) {
            T->isLockable = false;
            T = T->parent;
        }
    }
}
 
void unLock(narytree* node)
{
    if (node->isLock == false)
        return;
    narytree* T = node;
    node->isLock = false;
    // marking isLockable as true for ancestor nodes.
    while (T != NULL) {
        T->isLockable = true;
        T = T->parent;
    }
}
 
int main()
{
    // Creating N-Array Tree
    narytree* root = new narytree();
 
    narytree* t1 = new narytree(root);
    narytree* t2 = new narytree(root);
    narytree* t3 = new narytree(root);
 
    root->children.push_back(t1);
    root->children.push_back(t2);
    root->children.push_back(t3);
 
    narytree* t5 = new narytree(root->children[0]);
    root->children[0]->children.push_back(t5);
    narytree* t4 = new narytree(root->children[1]);
    root->children[1]->children.push_back(t4);
 
    // Locking t4 node.
    Lock(t4);
    //    Checking if the t4 node is locked.
    cout << "t4 node is locked:"
         << ((isLock(t4) == true) ? "true" : "false")
         << "\n";
    Lock(t2);
    cout << "t2 node is locked:"
         << ((isLock(t2) == true) ? "true" : "false")
         << "\n";
    // Unlocking t4 node.
    unLock(t4);
    //    Now we should be able to lock the tree.
    Lock(t2);
    cout << "t2 node is locked:"
         << ((isLock(t2) == true) ? "true" : "false");
 
    return 0;
}

Gracias a Adarsh ​​Singh por sugerir este enfoque. 

Este artículo es una contribución de Abhay Rathi . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.