1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] ¿Cómo representar a todos los miembros de su familia en una computadora?

2
00:00:10,790 --> 00:00:12,390
Podríamos simplemente utilizar una lista,

3
00:00:12,390 --> 00:00:14,400
pero hay una jerarquía clara aquí.

4
00:00:14,400 --> 00:00:17,110
>> Digamos que estamos empezando con su bisabuela, Alice.

5
00:00:17,110 --> 00:00:19,030
Ella tiene 2 hijos, Bob

6
00:00:19,030 --> 00:00:21,310
y su abuelo, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie tiene 3 hijos,

8
00:00:23,190 --> 00:00:26,730
su tío, Dave, su tía, Eva y su padre, Fred.

9
00:00:26,730 --> 00:00:28,750
Usted es hijo único de Fred.

10
00:00:28,750 --> 00:00:30,950
>> ¿Por qué la organización de los miembros de la familia de esta manera

11
00:00:30,950 --> 00:00:34,010
ser mejor que la representación simple lista?

12
00:00:34,010 --> 00:00:36,630
Una razón es que esta estructura jerárquica,

13
00:00:36,630 --> 00:00:39,660
llamado un "árbol", contiene más información que una simple lista.

14
00:00:40,540 --> 00:00:43,520
Sabemos que las relaciones familiares entre todos

15
00:00:43,520 --> 00:00:45,440
simplemente mediante el examen del árbol.

16
00:00:45,440 --> 00:00:47,250
Además, se puede acelerar

17
00:00:47,250 --> 00:00:50,010
look-up tiempo tremendamente, si los datos del árbol está ordenado.

18
00:00:50,010 --> 00:00:53,850
>> No podemos tomar ventaja de eso aquí, pero vamos a ver un ejemplo de esto pronto.

19
00:00:53,850 --> 00:00:56,150
Cada persona está representado por un nodo en el árbol.

20
00:00:56,680 --> 00:00:58,370
Los nodos pueden tener nodos secundarios

21
00:00:58,370 --> 00:01:00,350
así como un nodo padre.

22
00:01:00,350 --> 00:01:02,390
Estos son los términos técnicos,

23
00:01:02,390 --> 00:01:05,220
incluso cuando se utilizan los árboles para cosas además de las familias.

24
00:01:05,220 --> 00:01:07,940
Nodo de Alicia tiene 2 hijos y los padres no,

25
00:01:07,940 --> 00:01:11,500
mientras que el nodo de Charlie tiene 3 hijos y los padres 1.

26
00:01:11,500 --> 00:01:14,330
>> Un nodo hoja es uno que no tiene hijos

27
00:01:14,330 --> 00:01:16,410
en el borde exterior del árbol.

28
00:01:16,410 --> 00:01:18,520
El nodo superior del árbol, el nodo raíz,

29
00:01:18,520 --> 00:01:20,240
no tiene padre.

30
00:01:20,240 --> 00:01:23,170
>> Un árbol binario es un tipo específico de árbol,

31
00:01:23,170 --> 00:01:26,720
en el que cada nodo tiene, como máximo, 2 niños.

32
00:01:26,720 --> 00:01:30,490
Aquí está la estructura de un nodo de un árbol binario en C.

33
00:01:31,560 --> 00:01:34,530
Cada nodo tiene algunos datos asociados con él

34
00:01:34,530 --> 00:01:36,520
y 2 punteros a otros nodos.

35
00:01:36,520 --> 00:01:38,110
>> En nuestro árbol genealógico,

36
00:01:38,110 --> 00:01:40,900
los datos asociados era el nombre de cada persona.

37
00:01:40,900 --> 00:01:43,850
Aquí es un int, aunque podría ser cualquier cosa.

38
00:01:44,510 --> 00:01:46,200
Pues resulta que,

39
00:01:46,200 --> 00:01:48,990
un árbol binario no sería una buena representación para una familia,

40
00:01:48,990 --> 00:01:51,960
ya que las personas suelen tener más de 2 hijos.

41
00:01:51,960 --> 00:01:53,510
>> Un árbol binario de búsqueda

42
00:01:53,510 --> 00:01:56,380
es un tipo especial de árbol binario ordenado

43
00:01:56,380 --> 00:01:58,090
que nos permite ver los valores rápidamente.

44
00:01:58,740 --> 00:02:00,050
Usted puede haber notado

45
00:02:00,050 --> 00:02:02,010
que todos los nodos por debajo de la raíz de un árbol

46
00:02:02,010 --> 00:02:04,620
es la raíz de otro árbol, llamado 'subárbol.

47
00:02:04,960 --> 00:02:07,090
Aquí, la raíz del árbol es 6,

48
00:02:07,090 --> 00:02:09,860
y su hijo, 2, es la raíz de un subárbol.

49
00:02:09,860 --> 00:02:11,870
>> En un árbol de búsqueda binario

50
00:02:11,870 --> 00:02:15,790
todos los valores de un nodo es el subárbol derecho

51
00:02:15,790 --> 00:02:18,690
son mayores que el valor del nodo. A continuación: 6.

52
00:02:18,690 --> 00:02:22,640
Pues bien, los valores de subárbol izquierdo de un nodo

53
00:02:24,540 --> 00:02:26,890
son menores que el valor del nodo.

54
00:02:26,890 --> 00:02:28,620
Si tenemos que manejar valores duplicados,

55
00:02:28,620 --> 00:02:31,760
podemos cambiar cualquiera de ellos a una desigualdad suelto,

56
00:02:31,760 --> 00:02:34,410
el sentido de valores idénticos pueden caer ya sea en el lado izquierdo o derecho,

57
00:02:34,410 --> 00:02:37,400
siempre y cuando sean coherentes al respecto en todo.

58
00:02:37,400 --> 00:02:39,620
Este árbol es un árbol de búsqueda binaria

59
00:02:39,620 --> 00:02:41,540
porque sigue estas reglas.

60
00:02:42,320 --> 00:02:46,020
>> Así es como se vería si convirtiéramos todos los nodos en estructuras de C.

61
00:02:46,880 --> 00:02:48,410
Tenga en cuenta que si un niño está desaparecido,

62
00:02:48,410 --> 00:02:50,340
el puntero es nulo.

63
00:02:50,340 --> 00:02:53,270
¿Cómo comprobar si 7 se encuentra en el árbol?

64
00:02:53,270 --> 00:02:55,020
Partimos desde la raíz.

65
00:02:55,020 --> 00:02:58,690
El siete es mayor que 6, por lo que si está en el árbol, debe estar a la derecha.

66
00:02:59,680 --> 00:03:03,650
Entonces, es menos de 8, por lo que debe ser la izquierda.

67
00:03:03,650 --> 00:03:06,210
Aquí, hemos encontrado 7.

68
00:03:06,210 --> 00:03:08,160
Ahora, vamos a comprobar para 5.

69
00:03:08,160 --> 00:03:11,500
Cinco es menor que 6, por lo que debe estar a la izquierda.

70
00:03:11,500 --> 00:03:13,460
Cinco es mayor que 2,

71
00:03:13,460 --> 00:03:15,010
por lo que debe ser correcto,

72
00:03:15,010 --> 00:03:18,100
y también es mayor que 4, por lo que debe ser la derecha de nuevo.

73
00:03:18,100 --> 00:03:20,300
Sin embargo, no hay un niño aquí.

74
00:03:20,300 --> 00:03:22,000
El puntero es nulo.

75
00:03:22,000 --> 00:03:24,270
Esto significa que 5 no es en nuestro árbol.

76
00:03:24,270 --> 00:03:27,250
>> Podemos buscar en el árbol binario con el siguiente código:

77
00:03:28,430 --> 00:03:31,140
En cada nodo, se comprueba si se ha encontrado

78
00:03:31,140 --> 00:03:33,020
el valor que se busca.

79
00:03:33,020 --> 00:03:35,740
Si no lo encuentra, se determina si debe ser

80
00:03:35,740 --> 00:03:38,990
y en la izquierda o la derecha comprobar subárbol.

81
00:03:38,990 --> 00:03:41,160
Este ciclo continuará el árbol

82
00:03:41,160 --> 00:03:44,190
hasta que no hay ningún nodo hijo en la izquierda o la derecha.

83
00:03:45,190 --> 00:03:48,600
>> Recuerde que 5 no estaba en el árbol.

84
00:03:48,600 --> 00:03:50,460
¿Cómo se inserta?

85
00:03:50,460 --> 00:03:52,370
El proceso es similar a búsqueda.

86
00:03:52,370 --> 00:03:54,830
Nos iterar el árbol a partir de 6,

87
00:03:54,830 --> 00:03:57,040
izquierda a 2,

88
00:03:57,040 --> 00:03:59,140
derecho a 4,

89
00:03:59,140 --> 00:04:02,500
ya la derecha otra vez, pero 4 no tiene hijos en este lado.

90
00:04:02,500 --> 00:04:06,090
Esta será la nueva posición de 5,

91
00:04:06,090 --> 00:04:08,500
y se iniciará sin hijos.

92
00:04:09,020 --> 00:04:12,220
>> ¿A qué velocidad son operaciones en un árbol de búsqueda binaria?

93
00:04:12,220 --> 00:04:15,410
Recuerde que Bigohnotation busca proporcionar un límite superior.

94
00:04:15,410 --> 00:04:17,390
En el peor de los casos,

95
00:04:17,390 --> 00:04:19,480
nuestro árbol podría ser simplemente una lista enlazada

96
00:04:19,480 --> 00:04:22,220
lo que significa que la inserción, deleción, y búsqueda

97
00:04:22,220 --> 00:04:25,380
podría tomar un tiempo proporcional al número de nodos en el árbol.

98
00:04:25,380 --> 00:04:27,380
Esto es O (n).

99
00:04:27,380 --> 00:04:30,690
>> Por ejemplo, el siguiente es un árbol binario de búsqueda válido.

100
00:04:31,850 --> 00:04:34,020
Sin embargo, si tratamos de encontrar 9,

101
00:04:34,020 --> 00:04:36,760
tenemos que atravesar cada nodo.

102
00:04:36,760 --> 00:04:39,120
No es más que una lista enlazada.

103
00:04:39,120 --> 00:04:41,410
Lo ideal sería que cada nodo

104
00:04:41,410 --> 00:04:44,120
de nuestro árbol de búsqueda binaria para tener 2 hijos.

105
00:04:44,120 --> 00:04:46,370
De esta manera, inserción, eliminación y búsqueda

106
00:04:46,370 --> 00:04:50,190
tomaría, en el peor, O (log n) tiempo.

107
00:04:50,190 --> 00:04:52,470
El árbol de delante podría ser más equilibrada,

108
00:04:52,470 --> 00:04:54,140
como esta.

109
00:04:54,140 --> 00:04:57,980
Ahora, mirando hacia arriba toma cualquier valor, como máximo, 3 pasos.

110
00:04:57,980 --> 00:04:59,460
Este árbol está equilibrado,

111
00:04:59,460 --> 00:05:01,190
significado que disponga de un mínimo de profundidad

112
00:05:01,190 --> 00:05:03,680
en relación con el número de nodos.

113
00:05:03,680 --> 00:05:06,300
>> Busca un valor en un árbol binario de búsqueda equilibrado

114
00:05:06,300 --> 00:05:09,540
es similar a la búsqueda binaria en un arreglo ordenado.

115
00:05:09,540 --> 00:05:12,290
De hecho, si no es necesario insertar o eliminar elementos,

116
00:05:12,290 --> 00:05:15,150
se comportan exactamente de la misma manera.

117
00:05:15,150 --> 00:05:17,600
Sin embargo, una estructura de árbol es mejor

118
00:05:17,600 --> 00:05:19,530
para las inserciones y deleciones de manipulación

119
00:05:20,360 --> 00:05:22,670
>> Mi nombre es Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Esto es CS50.