Un árbol es una estructura de datos jerárquica no lineal que consiste en Nodes que están conectados por bordes. Tree almacena datos de manera no secuencial para que operaciones como agregar, eliminar, actualizar o buscar se puedan realizar en mucho menos tiempo que lo que se necesitaría en estructuras de datos lineales.
El recorrido del árbol toma un tiempo logarítmico para las operaciones básicas, mientras que para las estructuras de datos lineales con el aumento de tamaño, la complejidad del tiempo aumenta linealmente. Por lo tanto, los recorridos de árboles son más rápidos porque log(n)<n.
En Lisp, para hacer un árbol usamos celdas con, como listas de listas. Atravesamos las celdas con para realizar el recorrido previo, posterior al pedido y en orden.
Diferentes funciones de árbol en Lisp:
Lisp tiene algunas funciones predefinidas que podríamos usar en estructuras de datos de árbol.
| S. No. | Función | Descripción |
|---|---|---|
| 1 | árbol de copia x y vecp opcional | Devuelve una copia del árbol de contras celdas x. Copia recursivamente tanto la dirección del coche como la del cdr. Si x no es una celda de contras, la función simplemente devuelve x sin cambios. Si el argumento opcional vecp es verdadero, esta función copia vectores (recursivamente) así como celdas contras. |
| 2 | árbol-igual xy & clave: prueba: prueba-no: clave | Compara dos árboles de contras celdas. Si xey son ambas celdas contras, sus coches y cdrs se comparan recursivamente. Si ni x ni y son una celda contras, se comparan mediante eql, o de acuerdo con la prueba especificada. La función :key, si se especifica, se aplica a los elementos de ambos árboles. |
| 3 | subst new old tree & key :test :test-not :key | Los elementos antiguos se reemplazan (sustituyen) con un elemento nuevo, en un árbol, que es un árbol de celdas contras. |
| 4 | nsubst nuevo árbol antiguo y clave: prueba: prueba-no: clave | Funciona igual que subst, la única diferencia es que destruye el árbol original. |
| 5 | sublis árbol de lista y clave: prueba: prueba-no: clave | Funciona como subst, excepto que toma una lista de asociaciones de pares viejos-nuevos. Cada elemento del árbol (después de aplicar la función :key), se compara con los autos de alista; si coincide, se reemplaza por el cdr correspondiente. |
| 6 | nsublis alist árbol y clave: prueba: prueba-no: clave | Funciona igual que sublis, pero es una versión destructiva. |
En lisp, el coche representa el primer elemento de la lista. cdr representa el resto de la lista dejando el primer elemento. car y cdr no elimina ningún elemento de la lista, solo devuelve un informe de cuáles son los elementos
Construyendo tu propio árbol:
Con la ayuda de las funciones de árbol y lista, podemos hacer un árbol de la siguiente manera:
Paso 1: función para crear un Node con elementos de datos en él.
Lisp
; the below function creates a node with items in it. (defun make-tree (item) (cons (cons item nil) nil) )
Paso 2: función para agregar Nodes secundarios.
Lisp
; Function below will take two tree nodes and ; add the second tree as the child of the first. (defun add-child (tree child) (setf (car tree) (append (car tree) child)) tree )
Paso 3: Función para definir el primer hijo.
Lisp
; Function below will take a tree node and return ; the first child of that node or nil, ; if this node does not have any child node. (defun first-child (tree) (if (null tree) nil (cdr (car tree)) ) )
Paso 4: Función para devolver el siguiente hermano de un Node dado.
Lisp
; it takes a tree node as argument, ; and returns a reference to the next sibling node, ; or nil, if the node does not have any (defun next-sibling (tree) (cdr tree) )
Paso 5: Función para devolver la información en un Node.
Lisp
;a function to return the information in a node (defun data (tree) (car (car tree)) )
Ahora construyamos un árbol completo combinando los códigos escritos arriba en un solo archivo.
Ejemplo:
Lisp
; Code for aLisp tree ; the below function creates a node with items in it. (defun make-tree (item) (cons (cons item nil) nil) ) ; Function below will take two tree ; nodes and add the second tree as the child of the ; first. (defun add-child (tree child) (setf (car tree) (append (car tree) child)) tree ) ; Function below will take a tree node and return ; the first child of that node or nil, ; if this node does not have any child node. (defun first-child (tree) (if (null tree) nil (cdr (car tree)) ) ) ; it takes a tree node as argument, and returns ; a reference to the next sibling node, ; or nil, if the node does not have any (defun next-sibling (tree) (cdr tree) ) ;a function to return the information in a node (defun data (tree) (car (car tree)) ) (setq tree '((1 3 (2 6 9) ( (4 7 8))))) (setq mytree (make-tree 60)) (write (data mytree)) (terpri) (write (first-child tree)) (terpri) (setq newtree (add-child tree mytree)) (terpri) (write newtree)
Producción:
Publicación traducida automáticamente
Artículo escrito por kishanpandeyrkt y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA