Tree Datastructure Flashcards
Como se le llama a un nodo que no tiene hijos?
Se le llama leaf
A que se le llama completed tree
Quiere decir que el tree puede o no tener dos hijos, pero en su ultimo nivel deben de terminar a la derecha, de lo contrario no se considera como completo
A que se le llama full tree
Se le llama tree lleno a que sus hijos o terminan en nada o terminan con dos hijos, es decir cualquier nodo no puede tener un solo hijo, debe tener dos o ninguno
A que se le llama perfect tree
Se le llama perfect tree a que es completed y full, es decir, tambien una propiedad de este es que su ultimo nivel es el mas grande, debe de cumplir la que la longitud sea 2 a la n -1, donde n es el numero de niveles, ejemplo si tenemos un tree de 3 niveles, deberiamos de decir 2x2x2 = 8 - 1 = 7, 7 son los nodos para que sea un perfect tree
A que se le llama pre order traversal
De la familia de los depth-first, Se le llama asi al algoritmo que visita todo el tree de la siguiente manera para cada uno de sus nodos, esto por medio de recursion y un stack para ir imprimiendo, aqui root sera el primero que se imprimira
Visita el nodo actual
Visita el nodo de la izquierda
Visita el nodo de la derecha
Su complejidad en tiempo es O(n)
A que se le llama in order traversal
De la familia de los depth-first, Se le llama asi al algoritmo que recorre el tree de la siguiente manera para cada uno de sus nodos, esto por medio de recursion y un stack para ir imprimiendo, aqui se imprimiran en orden acsencente
visita el nodo izquierda
visita el nodo actual
visita el nodo de la derecha
Su complejidad es de O(n)
A que se le llama post order traversal
De la familia de los depth-first, Se le llama asi al algorimo que recorre el tree de la siguiente manera para cada uno de sus nodos, esto por medio de recursion y un stack para ir imprimiendo, aqui root sera el ultimo en imprimirse
Visita el nodo de la izquierda
Visita el nodo de la derecha
Visita el nodo actual
Su complejidad es de O(n)
A que se le llama in level order traversal
De la familia de los breadth-first, Se le llama asi al algotimo que recorre por niveles, es decir hasta que no se terminen el nivel en donde estamos no nos movemos al que sigue, aqui se utiliza queue e iteracion
Que es un binary tree
Es un tree que tiene la restriccion de que todos los elementos de la izquierda deben de ser menores que el nodo root y los de la derecha mayores con respecto a root, esto en todos sus niveles, la complejidad es de (log n) para insertar y para buscar, tambien debe de tener a lo mucho dos hijos, no mas, si tiene 3 por ejemplo se le considera terneary tree
Que es un heap
Es un tipo de tree que tiene ciertas caracteristicas, se conoce el heap max y el heap min, ambos se utilizan para priority queues y el min en root tiene al numero menor y el max al numero mayor en su root
A que se refiere con que un tree este balanceado
No se pretende tener un perfect tree, simplemente se busca que este lo mas balanceado posible para garantizar complejidad de (log n) en su insercion y busqueda, algunas tecnicas son red black flag y AVL
Como se representa un heap max o min
Un heap min o max se representa mediante un array
Como se identifica a un nodo de la izquirda en un heap min
(2 * parentIndex) + 1
Como se identifica a un nodo de la derecha en un heap min
(2 * parentIndex) + 2
Como se identifica a un parent sabiendo el indice uno de sus hijos?
(childenIdex - 1 ) /2
