Se sabe que la implementación de un árbol es una estructura jerárquica, lo cual nos conlleva a que hay diferentes tipos de árboles, en la entrada anterior vimos lo que es un árbol binario, que cada hoja o nodo tiene únicamente cero, una o dos ramas o enlaces que apuntan hacia la derecha o izquierda, pues bien, además de este árbol hay muchos más, de los cuales les estaré hablando en esta semana.
Behavior tree
Un árbol de comportamiento (BT) es un modelo matemático de ejecución de planes utilizado en informática, robótica, sistemas de control y videojuegos. Describen las conmutaciones entre un conjunto finito de tareas de foma modular. Su fuerza viene de su capacidad de crear tareas muy complejas compuestas de tareas simples, sin preocuparse de cómo se implementan las tareas simples, sin preocuparse de cómo se implementan las tareas simples, sin preocuparse de cómo se implementan las tareas simples. Los árboles de comportamiento presentan algunas similitudes con las máquinas de estado jerárquico con la diferencia clave de que el bloque de construcción principal de un comportamiento es una tarea en un lugar de un estado. Su facilidad de comprensión humana hace menos propenso a errores y muy popular en la comunidad de desarrolladores de juegos.
Árboles AVL
Es un tipo de árbol binario ideado por los matemáticos Adelson Velskii y Landis. Fue el primer árbol de búsqueda binario auto balanceable que se ideó. El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores Georgii Adelson-Velskii y Yevgeniy Landis. Lo dieron a conocer en la publicación de un artículo en 1962. Los AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad 0(log n). El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.
Árbol Splay
Un árbol biselado o árbol splay es un árbol binario de búsqueda auto-balanceable, con la propiedad adicional de que a los elementos accedidos recientemente se accederá más rápidamente en accesos posteriores. Realiza operaciones básicas como pueden ser la inserción, la búsqueda y el borrado en un tiempo del orden de 0(log n). Para muchas secuencias no uniformes de operaciones, el árbol biselado se comporta mejor que otros árboles de búsqueda, incluso cuando el patrón específico de la secuencia es desconocido. Esta estructura de datos fue inventada por Robert y Daniel Sleator.
Todas las operaciones normales de un árbol binario de búsqueda son combinadas con una operación básica, llamada biselación. Esta operación consiste en reorganizar el árbol para un cierto elemento, colocando éste en la raíz. Una manera de hacerlo es realizando primero una búsqueda binaria en el árbol para encontrar el elemento en cuestión y, a continuación, usar rotaciones de árboles de una manera específica para traer el elemento a la cima. Alternativamente, un algoritmo "de arriba abajo" puede combinar la búsqueda y la reorganización del árbol en una sola fase.
Fuentes:
Árbol AVL
Behavior Tree
Árbol Splay
Behavior tree
Un árbol de comportamiento (BT) es un modelo matemático de ejecución de planes utilizado en informática, robótica, sistemas de control y videojuegos. Describen las conmutaciones entre un conjunto finito de tareas de foma modular. Su fuerza viene de su capacidad de crear tareas muy complejas compuestas de tareas simples, sin preocuparse de cómo se implementan las tareas simples, sin preocuparse de cómo se implementan las tareas simples, sin preocuparse de cómo se implementan las tareas simples. Los árboles de comportamiento presentan algunas similitudes con las máquinas de estado jerárquico con la diferencia clave de que el bloque de construcción principal de un comportamiento es una tarea en un lugar de un estado. Su facilidad de comprensión humana hace menos propenso a errores y muy popular en la comunidad de desarrolladores de juegos.
 |
| Representación gráfica de un "Behavior Tree" |
Árboles AVL
Es un tipo de árbol binario ideado por los matemáticos Adelson Velskii y Landis. Fue el primer árbol de búsqueda binario auto balanceable que se ideó. El árbol AVL toma su nombre de las iniciales de los apellidos de sus inventores Georgii Adelson-Velskii y Yevgeniy Landis. Lo dieron a conocer en la publicación de un artículo en 1962. Los AVL están siempre equilibrados de tal modo que para todos los nodos, la altura de la rama izquierda no difiere en más de una unidad de la altura de la rama derecha o viceversa. Gracias a esta forma de equilibrio (o balanceo), la complejidad de una búsqueda en uno de estos árboles se mantiene siempre en orden de complejidad 0(log n). El factor de equilibrio puede ser almacenado directamente en cada nodo o ser computado a partir de las alturas de los subárboles.
 |
| Representación gráfica de un árbol avl |
Árbol Splay
Un árbol biselado o árbol splay es un árbol binario de búsqueda auto-balanceable, con la propiedad adicional de que a los elementos accedidos recientemente se accederá más rápidamente en accesos posteriores. Realiza operaciones básicas como pueden ser la inserción, la búsqueda y el borrado en un tiempo del orden de 0(log n). Para muchas secuencias no uniformes de operaciones, el árbol biselado se comporta mejor que otros árboles de búsqueda, incluso cuando el patrón específico de la secuencia es desconocido. Esta estructura de datos fue inventada por Robert y Daniel Sleator.
Todas las operaciones normales de un árbol binario de búsqueda son combinadas con una operación básica, llamada biselación. Esta operación consiste en reorganizar el árbol para un cierto elemento, colocando éste en la raíz. Una manera de hacerlo es realizando primero una búsqueda binaria en el árbol para encontrar el elemento en cuestión y, a continuación, usar rotaciones de árboles de una manera específica para traer el elemento a la cima. Alternativamente, un algoritmo "de arriba abajo" puede combinar la búsqueda y la reorganización del árbol en una sola fase.
 |
| Representación gráfica de árbol splay |
Árbol AVL
Behavior Tree
Árbol Splay
Comentarios
Publicar un comentario