Categoría: Binary Search Tree

Encuentre el recuento máximo de Nodes duplicados en un árbol de búsqueda binaria

Posted on by Rudeus Greyrat

Dado un árbol de búsqueda binario (BST) con duplicados, encuentre el Node (el elemento que ocurre con más frecuencia) en el BST dado. Si el BST contiene dos o más de estos Nodes, imprima cualquiera de ellos. Nota: No podemos utilizar ningún espacio adicional. (Suponga que el espacio de pila implícito incurrido debido a la recursividad … Continue reading «Encuentre el recuento máximo de Nodes duplicados en un árbol de búsqueda binaria»

Suma total excepto adyacente de un Node dado en BST

Posted on by Rudeus Greyrat

Dado un BST y un Node clave, encuentre la suma total en BST, excepto aquellos Nodes que son adyacentes al Node clave.  Ejemplos: 1:-Primero encuentre la suma total de BST  2:-Busque el Node clave y rastree su Node principal. 3:-Si el Node clave está presente, reste la suma de su Node adyacente de la suma total  … Continue reading «Suma total excepto adyacente de un Node dado en BST»

Aplicaciones, ventajas y desventajas del árbol de búsqueda binario

Posted on by Rudeus Greyrat

Binary Search Tree (BST) es un árbol binario especial que tiene las siguientes propiedades:  El subárbol izquierdo contiene solo las claves que son menores que la clave del Node.  El subárbol derecho contiene solo las claves que son mayores que la clave del Node. El subárbol izquierdo y derecho debe ser un árbol de búsqueda … Continue reading «Aplicaciones, ventajas y desventajas del árbol de búsqueda binario»

Imprimir Nodes de un árbol de búsqueda binaria en orden de nivel superior y orden de nivel inferior invertido alternativamente

Posted on by Rudeus Greyrat

Dado un árbol de búsqueda binario , la tarea es imprimir los Nodes del BST en el siguiente orden: Si el BST contiene niveles numerados del 1 al N , el orden de impresión es el nivel 1 , el nivel N , el nivel 2 , el nivel N – 1 , y así … Continue reading «Imprimir Nodes de un árbol de búsqueda binaria en orden de nivel superior y orden de nivel inferior invertido alternativamente»

Árbol rojo negro vs árbol AVL

Posted on by Rudeus Greyrat

En esta publicación, compararemos Red-Black Tree y AVL Tree.  Árbol negro rojo :  Propiedades :   El autoequilibrio se proporciona pintando cada Node con dos colores (rojo o negro). Cuando se modifica el árbol, se reorganiza y pinta un nuevo árbol. Requiere 1 bit de información de color para cada Node en el árbol. Complejidad temporal: … Continue reading «Árbol rojo negro vs árbol AVL»

Número de elementos más pequeños que la raíz usando el recorrido de preorden de un BST

Posted on by Rudeus Greyrat

Dado un recorrido de preorden de un BST. La tarea es encontrar el número de elementos menor que la raíz. Ejemplos:   Input: preorder[] = {3, 2, 1, 0, 5, 4, 6} Output: 3 Input: preorder[] = {5, 4, 3, 2, 1} Output: 4 Para un árbol de búsqueda binaria, un recorrido de preorden tiene la forma:   … Continue reading «Número de elementos más pequeños que la raíz usando el recorrido de preorden de un BST»

¿Cómo manejar los duplicados en el árbol de búsqueda binaria?

Posted on by Rudeus Greyrat

En un árbol de búsqueda binaria (BST), todas las claves del subárbol izquierdo de una clave deben ser más pequeñas y todas las claves del subárbol derecho deben ser mayores. Entonces, un árbol de búsqueda binario , por definición, tiene claves distintas.  ¿Cómo permitir duplicados donde cada inserción inserta una clave más con un valor … Continue reading «¿Cómo manejar los duplicados en el árbol de búsqueda binaria?»

Nodes de hoja del pedido anticipado de un árbol de búsqueda binario – Part 1

Posted on by Rudeus Greyrat

Dado un recorrido de preorden de un árbol de búsqueda binario. La tarea es imprimir los Nodes de hoja del árbol de búsqueda binaria del pedido previo dado. Ejemplos:  Input : preorder[] = {890, 325, 290, 530, 965}; Output : 290 530 965 Explanation : Tree represented is, 890 / \ 325 965 / \ … Continue reading «Nodes de hoja del pedido anticipado de un árbol de búsqueda binario – Part 1»

Encuentre si hay un triplete en un BST equilibrado que suma cero

Posted on by Rudeus Greyrat

Dado un árbol de búsqueda binario equilibrado (BST), escriba una función isTripletPresent() que devuelva verdadero si hay un triplete en BST dado con suma igual a 0, de lo contrario, devuelve falso. La complejidad de tiempo esperada es O (n ^ 2) y solo se puede usar O (Logn) espacio adicional. Puede modificar el árbol … Continue reading «Encuentre si hay un triplete en un BST equilibrado que suma cero»

Cuente los Nodes BST que se encuentran en un rango determinado

Posted on by Rudeus Greyrat

Dado un árbol de búsqueda binario (BST) y un rango, cuente el número de Nodes que se encuentran en el rango dado. Ejemplos:   Input: 10 / \ 5 50 / / \ 1 40 100 Range: [5, 45] Output: 3 There are three nodes in range, 5, 10 and 40 C++ // C++ program to … Continue reading «Cuente los Nodes BST que se encuentran en un rango determinado»