Diferencia entre revisiones de «Árbol binario de búsqueda»
(→Árbol Binario de Búsqueda(ABB)) (Etiqueta: Artículo sin Fuentes o Bibliografía o Referencias o Enlaces externos) |
|||
| (No se muestran 2 ediciones intermedias de otro usuario) | |||
| Línea 1: | Línea 1: | ||
| − | + | {{Otros usos|ABB (desambiguación)}} | |
| − | + | {{Definición | |
| − | + | |nombre=Árbol binario de búsqueda | |
| − | === | + | |imagen= |
| − | Son árboles binarios en los que se cumple que para cada nodo, el valor de la clave de la raíz del subárbol izquierdo es menor que el valor de la clave del nodo y que el valor de la clave raíz del subárbol derecho es mayor que el valor de la clave del nodo. | + | |tamaño= |
| − | + | |concepto=Estructura de datos utilizada en informática | |
| − | + | }}<div align=justify> | |
| − | Las operaciones para un ABB son similares que las realizadas en un árbol binario general. | + | '''Árbol Binario de Búsqueda''' (ABB). Son árboles binarios en los que se cumple que para cada nodo, el valor de la clave de la [[raíz]] del subárbol izquierdo es menor que el valor de la clave del nodo y que el valor de la clave raíz del subárbol derecho es mayor que el valor de la clave del nodo. Las operaciones para un ABB son similares que las realizadas en un [[árbol]] binario general. |
| − | + | == Buscar un elemento == | |
| − | |||
Partiendo siempre del nodo raíz, el modo de buscar un elemento se define de forma recursiva. | Partiendo siempre del nodo raíz, el modo de buscar un elemento se define de forma recursiva. | ||
| − | + | *Si el árbol está vacío, se termina la búsqueda: el elemento no está en el árbol. | |
| − | + | *Si el valor del nodo raíz es igual que el del elemento que se busca, se termina la búsqueda con éxito. | |
| − | + | *Si el valor del nodo raíz es mayor que el elemento que se busca, se continua la búsqueda en el árbol izquierdo. | |
| − | + | *Si el valor del nodo raíz es menor que el elemento que se busca, se continua la búsqueda en el árbol derecho. | |
| − | == | + | == Insertar un elemento == |
| − | Para insertar un elemento se basa en el algoritmo de búsqueda. Si el elemento está en el árbol no se inserta. Si no lo está, se inserta a continuación del último nodo visitado.Se necesita un puntero auxiliar para conservar una referencia al padre del nodo raíz actual. El valor inicial para ese puntero es NULL. | + | Para insertar un elemento se basa en el [[algoritmo]] de búsqueda. Si el elemento está en el árbol no se inserta. Si no lo está, se inserta a continuación del último nodo visitado.Se necesita un puntero auxiliar para conservar una referencia al padre del nodo raíz actual. El valor inicial para ese puntero es NULL. |
| − | == | + | ==Fuente == |
Estructuras Dinámicas de Datos - Salvador Pozo Coronado (en www.conclase.net) | Estructuras Dinámicas de Datos - Salvador Pozo Coronado (en www.conclase.net) | ||
| + | [[Category:Ciencias_Aplicadas_y_Tecnologías]][[Category:Informática]][[Category:Programación]][[Category:Partes_de_programas]] | ||
| + | [[Category:Estructura_de_datos]][[Category:Árboles_(estructura)]] | ||
última versión al 16:01 30 jul 2015
| ||||
Árbol Binario de Búsqueda (ABB). Son árboles binarios en los que se cumple que para cada nodo, el valor de la clave de la raíz del subárbol izquierdo es menor que el valor de la clave del nodo y que el valor de la clave raíz del subárbol derecho es mayor que el valor de la clave del nodo. Las operaciones para un ABB son similares que las realizadas en un árbol binario general.
Buscar un elemento
Partiendo siempre del nodo raíz, el modo de buscar un elemento se define de forma recursiva.
- Si el árbol está vacío, se termina la búsqueda: el elemento no está en el árbol.
- Si el valor del nodo raíz es igual que el del elemento que se busca, se termina la búsqueda con éxito.
- Si el valor del nodo raíz es mayor que el elemento que se busca, se continua la búsqueda en el árbol izquierdo.
- Si el valor del nodo raíz es menor que el elemento que se busca, se continua la búsqueda en el árbol derecho.
Insertar un elemento
Para insertar un elemento se basa en el algoritmo de búsqueda. Si el elemento está en el árbol no se inserta. Si no lo está, se inserta a continuación del último nodo visitado.Se necesita un puntero auxiliar para conservar una referencia al padre del nodo raíz actual. El valor inicial para ese puntero es NULL.
Fuente
Estructuras Dinámicas de Datos - Salvador Pozo Coronado (en www.conclase.net)
