1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Como representar todos os membros da súa familia en un ordenador?

2
00:00:10,790 --> 00:00:12,390
Nós poderiamos simplemente usar unha lista

3
00:00:12,390 --> 00:00:14,400
pero non hai unha xerarquía clara aquí.

4
00:00:14,400 --> 00:00:17,110
>> Imos dicir que nós estamos comezando co seu bisavó, Alice.

5
00:00:17,110 --> 00:00:19,030
Ela ten dous fillos, Bob

6
00:00:19,030 --> 00:00:21,310
eo seu avó, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie ten 3 fillos,

8
00:00:23,190 --> 00:00:26,730
seu tío, Dave, súa tía, Eva, eo seu pai, Fred.

9
00:00:26,730 --> 00:00:28,750
Vostede é fillo único de Fred.

10
00:00:28,750 --> 00:00:30,950
>> Por que organizar os seus familiares, deste xeito

11
00:00:30,950 --> 00:00:34,010
ser mellor que a representación da lista simple?

12
00:00:34,010 --> 00:00:36,630
Unha razón é que esta estrutura xerárquica,

13
00:00:36,630 --> 00:00:39,660
chamado "árbore", contén máis informacións do que unha simple lista.

14
00:00:40,540 --> 00:00:43,520
Sabemos que as relacións familiares entre todos

15
00:00:43,520 --> 00:00:45,440
só a través do exame da árbore.

16
00:00:45,440 --> 00:00:47,250
Ademais, pode acelerar

17
00:00:47,250 --> 00:00:50,010
look-up de tempo tremenda, os datos da árbore está clasificada.

18
00:00:50,010 --> 00:00:53,850
>> Non podemos aproveitar de que aquí, pero imos ver un exemplo diso en breve.

19
00:00:53,850 --> 00:00:56,150
Cada persoa é representada por un nó na árbore.

20
00:00:56,680 --> 00:00:58,370
Nós pode ter nós fillo

21
00:00:58,370 --> 00:01:00,350
así como un nó pai.

22
00:01:00,350 --> 00:01:02,390
Estes son os termos técnicos,

23
00:01:02,390 --> 00:01:05,220
mesmo cando se usa árbores para cousas alén de familias.

24
00:01:05,220 --> 00:01:07,940
Nó de Alicia ten dous fillos e non dos pais,

25
00:01:07,940 --> 00:01:11,500
mentres que no de Charlie ten 3 fillos e unha nai.

26
00:01:11,500 --> 00:01:14,330
>> Un nodo folla é aquel que non ten fillos

27
00:01:14,330 --> 00:01:16,410
no bordo exterior da árbore.

28
00:01:16,410 --> 00:01:18,520
O nodo máis alto da árbore, o nodo raíz,

29
00:01:18,520 --> 00:01:20,240
non ten pai.

30
00:01:20,240 --> 00:01:23,170
>> Unha árbore binaria é un tipo específico de árbore,

31
00:01:23,170 --> 00:01:26,720
en que cada nodo ten como máximo, 2 nenos.

32
00:01:26,720 --> 00:01:30,490
Aquí é a estrutura dun nodo dunha árbore binaria en C.

33
00:01:31,560 --> 00:01:34,530
Cada nodo ten algúns datos asociados

34
00:01:34,530 --> 00:01:36,520
e dous punteiros para outros nós.

35
00:01:36,520 --> 00:01:38,110
>> Na nosa árbore de familia,

36
00:01:38,110 --> 00:01:40,900
os datos asociados era o nome de cada persoa.

37
00:01:40,900 --> 00:01:43,850
Aquí é un int, que podería ser calquera cousa.

38
00:01:44,510 --> 00:01:46,200
Como se ve,

39
00:01:46,200 --> 00:01:48,990
unha árbore binaria non sería unha boa representación para unha familia,

40
00:01:48,990 --> 00:01:51,960
xa que as persoas moitas veces teñen máis de dous fillos.

41
00:01:51,960 --> 00:01:53,510
>> Unha árbore de busca binaria

42
00:01:53,510 --> 00:01:56,380
é un tipo especial de árbore binaria ordenada

43
00:01:56,380 --> 00:01:58,090
que nos permite ollar os valores rapidamente.

44
00:01:58,740 --> 00:02:00,050
Debe ter notado

45
00:02:00,050 --> 00:02:02,010
que cada nodo abaixo da raíz dunha árbore

46
00:02:02,010 --> 00:02:04,620
é a raíz doutra árbore, chamado de "sub".

47
00:02:04,960 --> 00:02:07,090
Aquí, a raíz da árbore é de 6,

48
00:02:07,090 --> 00:02:09,860
eo seu fillo, 2, é a raíz dunha subárvore.

49
00:02:09,860 --> 00:02:11,870
>> Nunha árbore de busca binaria

50
00:02:11,870 --> 00:02:15,790
todos os valores dun nodo é subárvore dereita

51
00:02:15,790 --> 00:02:18,690
son maiores que o valor do nodo. Aquí: 6.

52
00:02:18,690 --> 00:02:22,640
Así, os valores na subárvore esquerda dun nodo

53
00:02:24,540 --> 00:02:26,890
son menos que o valor do nodo.

54
00:02:26,890 --> 00:02:28,620
Se necesitamos tratar con valores duplicados,

55
00:02:28,620 --> 00:02:31,760
podemos cambiar ou daqueles a unha desigualdade solto,

56
00:02:31,760 --> 00:02:34,410
significa valores idénticos poden caer ou á esquerda ou á dereita,

57
00:02:34,410 --> 00:02:37,400
sempre que sexan consistentes sobre el todo.

58
00:02:37,400 --> 00:02:39,620
Esta árbore é unha árbore de busca binaria

59
00:02:39,620 --> 00:02:41,540
porque segue estas regras.

60
00:02:42,320 --> 00:02:46,020
>> Isto é como ficaría se converteu todos os nós en estruturas C.

61
00:02:46,880 --> 00:02:48,410
Teña en conta que, se un neno está en falta,

62
00:02:48,410 --> 00:02:50,340
o punteiro é nulo.

63
00:02:50,340 --> 00:02:53,270
Como podemos comprobar, a ver se é 7 na árbore?

64
00:02:53,270 --> 00:02:55,020
Comezamos na raíz.

65
00:02:55,020 --> 00:02:58,690
Sete é superior a 6, polo que se está na árbore, debe ser para a dereita.

66
00:02:59,680 --> 00:03:03,650
A continuación, é inferior a 8, polo que debe ser deixado.

67
00:03:03,650 --> 00:03:06,210
Aquí, nós descubrimos 7.

68
00:03:06,210 --> 00:03:08,160
Agora, imos comprobar a 5.

69
00:03:08,160 --> 00:03:11,500
Cinco é inferior a 6, polo que debe ser á esquerda.

70
00:03:11,500 --> 00:03:13,460
Cinco é maior que 2,

71
00:03:13,460 --> 00:03:15,010
debería estar seguro,

72
00:03:15,010 --> 00:03:18,100
e tamén é maior que 4, entón debe estar seguro de novo.

73
00:03:18,100 --> 00:03:20,300
Con todo, non hai ningún neno aquí.

74
00:03:20,300 --> 00:03:22,000
O punteiro é nulo.

75
00:03:22,000 --> 00:03:24,270
Isto significa que, 5 non é na nosa árbore.

76
00:03:24,270 --> 00:03:27,250
>> Podemos buscar a árbore binaria co seguinte código:

77
00:03:28,430 --> 00:03:31,140
En cada nodo, imos comprobar a ver se temos atopado

78
00:03:31,140 --> 00:03:33,020
o valor que estamos a buscar.

79
00:03:33,020 --> 00:03:35,740
Se non atopalo, imos determinar se debe ser

80
00:03:35,740 --> 00:03:38,990
sobre a esquerda ou dereita e comprobar que subárvore.

81
00:03:38,990 --> 00:03:41,160
Este ciclo vai continuar a descender da árbore

82
00:03:41,160 --> 00:03:44,190
ata que non haxa ningún nodo fillo de ambos á esquerda ou cara á dereita.

83
00:03:45,190 --> 00:03:48,600
>> Lembre que 5 non estaba na árbore.

84
00:03:48,600 --> 00:03:50,460
Como podemos inserir-lo?

85
00:03:50,460 --> 00:03:52,370
O proceso é semellante a busca.

86
00:03:52,370 --> 00:03:54,830
Repetimos a árbore a partir do 6 de

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

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

89
00:03:59,140 --> 00:04:02,500
e de novo á dereita, pero 4 non ten fillo deste lado.

90
00:04:02,500 --> 00:04:06,090
Esta será a nova posición para 5,

91
00:04:06,090 --> 00:04:08,500
e el vai comezar sen fillos.

92
00:04:09,020 --> 00:04:12,220
>> O quão rápido son operacións nunha árbore de busca binaria?

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

94
00:04:15,410 --> 00:04:17,390
No peor dos casos,

95
00:04:17,390 --> 00:04:19,480
nosa árbore podería ser simplemente unha lista encadeada

96
00:04:19,480 --> 00:04:22,220
o que significa que a inserción, supresión e investigación

97
00:04:22,220 --> 00:04:25,380
pode levar tempo proporcional ao número de nós na árbore.

98
00:04:25,380 --> 00:04:27,380
Este é O (n).

99
00:04:27,380 --> 00:04:30,690
>> Por exemplo, o seguinte é unha árbore de busca binaria válido.

100
00:04:31,850 --> 00:04:34,020
No entanto, se tentar atopar 9,

101
00:04:34,020 --> 00:04:36,760
temos que atravesan cada nó.

102
00:04:36,760 --> 00:04:39,120
Non é mellor que unha lista ligada.

103
00:04:39,120 --> 00:04:41,410
Ideal, queremos cada nodo

104
00:04:41,410 --> 00:04:44,120
da nosa árbore de busca binaria de 2 fillos.

105
00:04:44,120 --> 00:04:46,370
Desta forma, a inserción, supresión e investigación

106
00:04:46,370 --> 00:04:50,190
levaría, no peor dos casos, o (log n).

107
00:04:50,190 --> 00:04:52,470
A árbore de antes podería ser máis equilibrado,

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

109
00:04:54,140 --> 00:04:57,980
Agora, mirando a calquera valor ten como máximo 3 pasos.

110
00:04:57,980 --> 00:04:59,460
Esta árbore é equilibrada,

111
00:04:59,460 --> 00:05:01,190
o que significa que é, ten unha profundidade mínima

112
00:05:01,190 --> 00:05:03,680
en relación ao número de nós.

113
00:05:03,680 --> 00:05:06,300
>> Á procura dun valor nunha árbore equilibrada de busca binaria

114
00:05:06,300 --> 00:05:09,540
é semellante ao de busca binaria nun array ordenado.

115
00:05:09,540 --> 00:05:12,290
En realidade, se nós non necesitamos inserir ou eliminar elementos,

116
00:05:12,290 --> 00:05:15,150
eles se comportan exactamente da mesma maneira.

117
00:05:15,150 --> 00:05:17,600
Con todo, a estrutura da árbore é mellor

118
00:05:17,600 --> 00:05:19,530
para insercións e borrados de manipulación

119
00:05:20,360 --> 00:05:22,670
>> O meu nome é Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Este é CS50.