Cita: Solo que si se le quiere agregar o quitar un nuevo elemento hay que actualizar todos los nodos de toda la tabla, me parece algo lioso.
En efecto, las operaciones de ABM son muy costosas, depende el caso, pero por lo general la cantidad de veces que un menu es modificado es insignificante en relacion a la cantidad de veces que se muestra.
Depende del contexto, pero personalmente prefiero esperar unos segundos una unica vez cuando modifico a tener que esperarlos cada vez que quiero ver el menu.
El modelo que menciones esta bueno como alternativa pero es mas complejo, tiene la complejidad del modelo de adyacencia + la complejidad del modelo de conjunto anidado + un extra propio. Las operaciones basicas indispensables se vuelven mas tediosas pero las complejas mas simples. Depende el contexto puede ser util.