1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Bir kompüter bütün ailə üzvləri necə təmsil edəcək?

2
00:00:10,790 --> 00:00:12,390
Biz sadəcə, bir siyahısını istifadə edə bilər

3
00:00:12,390 --> 00:00:14,400
lakin aydın iyerarxiya burada var.

4
00:00:14,400 --> 00:00:17,110
>> Gəlin biz sizin böyük-nənəsi, Alice ilə başlayan etdiyiniz deyirlər.

5
00:00:17,110 --> 00:00:19,030
O, 2 oğulları, Bob var

6
00:00:19,030 --> 00:00:21,310
və babası, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie, 3 övladı var

8
00:00:23,190 --> 00:00:26,730
Sizin əmisi Dave, sizin xalası, Həvva və atası Fred.

9
00:00:26,730 --> 00:00:28,750
Siz Fred yalnız uşaq var.

10
00:00:28,750 --> 00:00:30,950
>> Niyə bu şəkildə ailə üzvləri təşkil edərdi

11
00:00:30,950 --> 00:00:34,010
sadə siyahısı təmsil daha yaxşı olacaq?

12
00:00:34,010 --> 00:00:36,630
Bir səbəbi bu iyerarxik struktur,

13
00:00:36,630 --> 00:00:39,660
adlandırıb 'ağac, bir sadə siyahısı daha çox məlumat var.

14
00:00:40,540 --> 00:00:43,520
Biz hər kəs arasında ailesel əlaqələr bilirik

15
00:00:43,520 --> 00:00:45,440
yalnız ağac araşdıraraq.

16
00:00:45,440 --> 00:00:47,250
Həmçinin, sürətləndirmək bilər

17
00:00:47,250 --> 00:00:50,010
göz-up vaxt böyük, ağac data sıralanır olunur.

18
00:00:50,010 --> 00:00:53,850
>> Biz burada istifadə edə bilməz, amma, biz tezliklə bu nümunə görəcəksiniz.

19
00:00:53,850 --> 00:00:56,150
Hər bir şəxs ağac bir node ilə təmsil olunur.

20
00:00:56,680 --> 00:00:58,370
Bölmələri uşaq qovşaqlarının ola bilər

21
00:00:58,370 --> 00:01:00,350
habelə valideyn node kimi.

22
00:01:00,350 --> 00:01:02,390
Bu, texniki şərtlər var

23
00:01:02,390 --> 00:01:05,220
ailələrin başqa şeylər üçün ağac istifadə edərək hətta.

24
00:01:05,220 --> 00:01:07,940
Alice in node, 2 uşaq və valideynləri var

25
00:01:07,940 --> 00:01:11,500
Charlie nin node 3 uşaq və 1 valideyn isə.

26
00:01:11,500 --> 00:01:14,330
>> A yarpaq node uşaqların olmayan biri

27
00:01:14,330 --> 00:01:16,410
ağac kənarda kənarında.

28
00:01:16,410 --> 00:01:18,520
Ağacın topmost node, kök node,

29
00:01:18,520 --> 00:01:20,240
heç bir valideyn var.

30
00:01:20,240 --> 00:01:23,170
>> A ikili ağac, ağac xüsusi bir növü

31
00:01:23,170 --> 00:01:26,720
hər node, ən azı, 2 övladı var.

32
00:01:26,720 --> 00:01:30,490
Burada C. ikili ağac bir node və struct edir

33
00:01:31,560 --> 00:01:34,530
Hər node ilə bağlı bəzi məlumatlar var

34
00:01:34,530 --> 00:01:36,520
digər qovşaqlarının və 2 göstəricilər.

35
00:01:36,520 --> 00:01:38,110
>> Bizim ailə ağac,

36
00:01:38,110 --> 00:01:40,900
bağlı data hər bir şəxsin adı oldu.

37
00:01:40,900 --> 00:01:43,850
Bir şey ola bilər, baxmayaraq Burada, bir int edir.

38
00:01:44,510 --> 00:01:46,200
O çıxır ki,

39
00:01:46,200 --> 00:01:48,990
ikili ağac, bir ailə üçün yaxşı təmsil olmaz

40
00:01:48,990 --> 00:01:51,960
insanlar tez-tez çox 2 övladı var-ci ildən.

41
00:01:51,960 --> 00:01:53,510
>> A ikili axtarış ağac

42
00:01:53,510 --> 00:01:56,380
binar ağac xüsusi, sifarişli növü

43
00:01:56,380 --> 00:01:58,090
bizə tez dəyərlər baxmaq üçün imkan verir.

44
00:01:58,740 --> 00:02:00,050
Siz qeyd edə bilər

45
00:02:00,050 --> 00:02:02,010
bir ağacın kökü aşağıda hər node

46
00:02:02,010 --> 00:02:04,620
digər ağac kökü, bir 'subtree. "adlanır

47
00:02:04,960 --> 00:02:07,090
Burada ağac kökü, 6

48
00:02:07,090 --> 00:02:09,860
və onun uşaq, 2, subtree köküdür.

49
00:02:09,860 --> 00:02:11,870
>> Ikili axtarış ağac

50
00:02:11,870 --> 00:02:15,790
bir node bütün dəyərlər sağ subtree var

51
00:02:15,790 --> 00:02:18,690
node dəyəri daha böyükdür. Burada: 6.

52
00:02:18,690 --> 00:02:22,640
Yaxşı, bir node sol subtree dəyərlər

53
00:02:24,540 --> 00:02:26,890
node dəyəri çox azdır.

54
00:02:26,890 --> 00:02:28,620
Biz cüt dəyərlər idarə etmək lazımdır,

55
00:02:28,620 --> 00:02:31,760
biz bir boş bərabərsizlik ya bu dəyişə bilərsiniz

56
00:02:31,760 --> 00:02:34,410
eyni dəyərlər sol və ya sağ ya düşə bilər, yəni

57
00:02:34,410 --> 00:02:37,400
kimi uzun biz ərzində bu barədə ardıcıl var.

58
00:02:37,400 --> 00:02:39,620
Bu ağac ikili axtarış ağac

59
00:02:39,620 --> 00:02:41,540
bu qaydalarına əməl edir.

60
00:02:42,320 --> 00:02:46,020
>> Bu C structs daxil bütün qovşaqlarının çevrilmişdir əgər görünür necə.

61
00:02:46,880 --> 00:02:48,410
Qeyd edək ki, bir uşaq itkin əgər,

62
00:02:48,410 --> 00:02:50,340
İmleci null edir.

63
00:02:50,340 --> 00:02:53,270
Necə 7 ağac olub olmadığını görmek üçün kontrol olsun?

64
00:02:53,270 --> 00:02:55,020
Biz kök-da başlanır.

65
00:02:55,020 --> 00:02:58,690
Bu ağac əgər yeddi 6 böyükdür, belə ki, bu, doğru olmalıdır.

66
00:02:59,680 --> 00:03:03,650
Sonra o, 8-dən az, belə ki, onu tərk etmək lazımdır.

67
00:03:03,650 --> 00:03:06,210
Burada 7 tapmışdır.

68
00:03:06,210 --> 00:03:08,160
İndi biz 5-kontrol edəcəyik.

69
00:03:08,160 --> 00:03:11,500
Beş 6 azdır, belə ki, sol olmalıdır.

70
00:03:11,500 --> 00:03:13,460
Beş, 2 daha böyük

71
00:03:13,460 --> 00:03:15,010
belə ki, doğru olmalıdır

72
00:03:15,010 --> 00:03:18,100
və bu da 4-dən böyük, belə ki, sağ yenidən olmalıdır.

73
00:03:18,100 --> 00:03:20,300
Lakin, heç bir uşaq burada var.

74
00:03:20,300 --> 00:03:22,000
Bu göstərici null edir.

75
00:03:22,000 --> 00:03:24,270
Bu 5 bizim ağac deyil deməkdir.

76
00:03:24,270 --> 00:03:27,250
>> Biz aşağıdakı kodu ilə ikili ağac axtarış edə bilərsiniz:

77
00:03:28,430 --> 00:03:31,140
Hər node-hazırda, biz gördük kontrol edin

78
00:03:31,140 --> 00:03:33,020
biz axtarır dəyəri.

79
00:03:33,020 --> 00:03:35,740
Biz bu tapmasanız olmalıdır, əgər biz müəyyən

80
00:03:35,740 --> 00:03:38,990
sol və ya sağ və ki subtree yoxlayın.

81
00:03:38,990 --> 00:03:41,160
Bu loop ağac aşağı davam edəcək

82
00:03:41,160 --> 00:03:44,190
sol və ya sağ ya heç bir uşaq node var qədər.

83
00:03:45,190 --> 00:03:48,600
>> 5 ağac olmadığını unutmayın.

84
00:03:48,600 --> 00:03:50,460
Biz bu daxil edə bilərəm?

85
00:03:50,460 --> 00:03:52,370
Prosesi axtarış benzer.

86
00:03:52,370 --> 00:03:54,830
Biz, 6 ildən başlayaraq ağac aşağı təkrarlamaq

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

88
00:03:57,040 --> 00:03:59,140
4 hüququ

89
00:03:59,140 --> 00:04:02,500
və sağ yenidən, lakin 4 bu tərəfində heç bir uşaq var.

90
00:04:02,500 --> 00:04:06,090
Bu, 5 yeni mövqe olacaq

91
00:04:06,090 --> 00:04:08,500
və heç bir uşaq ilə başlayacaq.

92
00:04:09,020 --> 00:04:12,220
>> Necə sürətli bir ikili axtarış ağac əməliyyatları var?

93
00:04:12,220 --> 00:04:15,410
Bigohnotation bir üst bound təmin etməyə çalışır unutmayın.

94
00:04:15,410 --> 00:04:17,390
Ən pis halda,

95
00:04:17,390 --> 00:04:19,480
bizim ağac sadəcə bir bağlı siyahı ola bilər

96
00:04:19,480 --> 00:04:22,220
ki, durub, silinməsi, və axtarış məna

97
00:04:22,220 --> 00:04:25,380
ağac ilə qovşaqlarının sayı mütənasib vaxt bilər.

98
00:04:25,380 --> 00:04:27,380
Bu O (n) edir.

99
00:04:27,380 --> 00:04:30,690
>> Məsələn, aşağıdakı cari ikili axtarış ağac.

100
00:04:31,850 --> 00:04:34,020
Lakin, biz 9 tapmaq üçün cəhd əgər,

101
00:04:34,020 --> 00:04:36,760
hər node axır var.

102
00:04:36,760 --> 00:04:39,120
Bu bağlı siyahı daha yaxşıdır.

103
00:04:39,120 --> 00:04:41,410
İdeal halda biz hər node istəyirəm

104
00:04:41,410 --> 00:04:44,120
bizim ikili axtarış ağac 2 övladı var.

105
00:04:44,120 --> 00:04:46,370
Bu yolla, durub, silinməsi və axtarış

106
00:04:46,370 --> 00:04:50,190
, ən pis halda, O (Giriş n) vaxt olardı.

107
00:04:50,190 --> 00:04:52,470
Əvvəl ağac, daha balanslı ola bilər

108
00:04:52,470 --> 00:04:54,140
bunu bəyənir.

109
00:04:54,140 --> 00:04:57,980
İndi, heç bir dəyəri axtarır 3 addımlar, ən azı edir.

110
00:04:57,980 --> 00:04:59,460
Bu ağac, balanslaşdırılmış edir

111
00:04:59,460 --> 00:05:01,190
ki, mənası bir minimal dərinliyi

112
00:05:01,190 --> 00:05:03,680
qovşaqlarının sayı nisbətən.

113
00:05:03,680 --> 00:05:06,300
>> Balanslaşdırılmış ikili axtarış ağac bir dəyər Axtarıram

114
00:05:06,300 --> 00:05:09,540
bir sıralanır array haqqında ikili axtarış kimi.

115
00:05:09,540 --> 00:05:12,290
Əslində, biz maddələr daxil və ya silmək üçün ehtiyac yoxdur, əgər

116
00:05:12,290 --> 00:05:15,150
onlar tam eyni şəkildə davranmaq.

117
00:05:15,150 --> 00:05:17,600
Lakin, bir ağac strukturu yaxşı

118
00:05:17,600 --> 00:05:19,530
user insertions ve silme üçün

119
00:05:20,360 --> 00:05:22,670
>> My name Bannus Van der Kloot edir.

120
00:05:22,670 --> 00:05:24,030
Bu CS50 edir.