[Powered by Google Translate] ¿Cómo representar a todos los miembros de su familia en una computadora?
Podríamos simplemente utilizar una lista,
pero hay una jerarquía clara aquí.
>> Digamos que estamos empezando con su bisabuela, Alice.
Ella tiene 2 hijos, Bob
y su abuelo, Charlie.
Charlie tiene 3 hijos,
su tío, Dave, su tía, Eva y su padre, Fred.
Usted es hijo único de Fred.
>> ¿Por qué la organización de los miembros de la familia de esta manera
ser mejor que la representación simple lista?
Una razón es que esta estructura jerárquica,
llamado un "árbol", contiene más información que una simple lista.
Sabemos que las relaciones familiares entre todos
simplemente mediante el examen del árbol.
Además, se puede acelerar
look-up tiempo tremendamente, si los datos del árbol está ordenado.
>> No podemos tomar ventaja de eso aquí, pero vamos a ver un ejemplo de esto pronto.
Cada persona está representado por un nodo en el árbol.
Los nodos pueden tener nodos secundarios
así como un nodo padre.
Estos son los términos técnicos,
incluso cuando se utilizan los árboles para cosas además de las familias.
Nodo de Alicia tiene 2 hijos y los padres no,
mientras que el nodo de Charlie tiene 3 hijos y los padres 1.
>> Un nodo hoja es uno que no tiene hijos
en el borde exterior del árbol.
El nodo superior del árbol, el nodo raíz,
no tiene padre.
>> Un árbol binario es un tipo específico de árbol,
en el que cada nodo tiene, como máximo, 2 niños.
Aquí está la estructura de un nodo de un árbol binario en C.
Cada nodo tiene algunos datos asociados con él
y 2 punteros a otros nodos.
>> En nuestro árbol genealógico,
los datos asociados era el nombre de cada persona.
Aquí es un int, aunque podría ser cualquier cosa.
Pues resulta que,
un árbol binario no sería una buena representación para una familia,
ya que las personas suelen tener más de 2 hijos.
>> Un árbol binario de búsqueda
es un tipo especial de árbol binario ordenado
que nos permite ver los valores rápidamente.
Usted puede haber notado
que todos los nodos por debajo de la raíz de un árbol
es la raíz de otro árbol, llamado 'subárbol.
Aquí, la raíz del árbol es 6,
y su hijo, 2, es la raíz de un subárbol.
>> En un árbol de búsqueda binario
todos los valores de un nodo es el subárbol derecho
son mayores que el valor del nodo. A continuación: 6.
Pues bien, los valores de subárbol izquierdo de un nodo
son menores que el valor del nodo.
Si tenemos que manejar valores duplicados,
podemos cambiar cualquiera de ellos a una desigualdad suelto,
el sentido de valores idénticos pueden caer ya sea en el lado izquierdo o derecho,
siempre y cuando sean coherentes al respecto en todo.
Este árbol es un árbol de búsqueda binaria
porque sigue estas reglas.
>> Así es como se vería si convirtiéramos todos los nodos en estructuras de C.
Tenga en cuenta que si un niño está desaparecido,
el puntero es nulo.
¿Cómo comprobar si 7 se encuentra en el árbol?
Partimos desde la raíz.
El siete es mayor que 6, por lo que si está en el árbol, debe estar a la derecha.
Entonces, es menos de 8, por lo que debe ser la izquierda.
Aquí, hemos encontrado 7.
Ahora, vamos a comprobar para 5.
Cinco es menor que 6, por lo que debe estar a la izquierda.
Cinco es mayor que 2,
por lo que debe ser correcto,
y también es mayor que 4, por lo que debe ser la derecha de nuevo.
Sin embargo, no hay un niño aquí.
El puntero es nulo.
Esto significa que 5 no es en nuestro árbol.
>> Podemos buscar en el árbol binario con el siguiente código:
En cada nodo, se comprueba si se ha encontrado
el valor que se busca.
Si no lo encuentra, se determina si debe ser
y en la izquierda o la derecha comprobar subárbol.
Este ciclo continuará el árbol
hasta que no hay ningún nodo hijo en la izquierda o la derecha.
>> Recuerde que 5 no estaba en el árbol.
¿Cómo se inserta?
El proceso es similar a búsqueda.
Nos iterar el árbol a partir de 6,
izquierda a 2,
derecho a 4,
ya la derecha otra vez, pero 4 no tiene hijos en este lado.
Esta será la nueva posición de 5,
y se iniciará sin hijos.
>> ¿A qué velocidad son operaciones en un árbol de búsqueda binaria?
Recuerde que Bigohnotation busca proporcionar un límite superior.
En el peor de los casos,
nuestro árbol podría ser simplemente una lista enlazada
lo que significa que la inserción, deleción, y búsqueda
podría tomar un tiempo proporcional al número de nodos en el árbol.
Esto es O (n).
>> Por ejemplo, el siguiente es un árbol binario de búsqueda válido.
Sin embargo, si tratamos de encontrar 9,
tenemos que atravesar cada nodo.
No es más que una lista enlazada.
Lo ideal sería que cada nodo
de nuestro árbol de búsqueda binaria para tener 2 hijos.
De esta manera, inserción, eliminación y búsqueda
tomaría, en el peor, O (log n) tiempo.
El árbol de delante podría ser más equilibrada,
como esta.
Ahora, mirando hacia arriba toma cualquier valor, como máximo, 3 pasos.
Este árbol está equilibrado,
significado que disponga de un mínimo de profundidad
en relación con el número de nodos.
>> Busca un valor en un árbol binario de búsqueda equilibrado
es similar a la búsqueda binaria en un arreglo ordenado.
De hecho, si no es necesario insertar o eliminar elementos,
se comportan exactamente de la misma manera.
Sin embargo, una estructura de árbol es mejor
para las inserciones y deleciones de manipulación
>> Mi nombre es Bannus Van der Kloot.
Esto es CS50.