1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] Bagaimana Anda mewakili semua anggota keluarga Anda di komputer?

2
00:00:10,790 --> 00:00:12,390
Kami hanya bisa menggunakan daftar,

3
00:00:12,390 --> 00:00:14,400
tapi ada hirarki yang jelas di sini.

4
00:00:14,400 --> 00:00:17,110
>> Katakanlah kita mulai dengan besar-nenek Anda, Alice.

5
00:00:17,110 --> 00:00:19,030
Dia memiliki 2 anak laki-laki, Bob

6
00:00:19,030 --> 00:00:21,310
dan Anda kakek, Charlie.

7
00:00:21,310 --> 00:00:23,190
Charlie memiliki 3 anak,

8
00:00:23,190 --> 00:00:26,730
Anda paman, Dave, bibimu, Eve, dan ayahmu, Fred.

9
00:00:26,730 --> 00:00:28,750
Anda adalah anak tunggal Fred.

10
00:00:28,750 --> 00:00:30,950
>> Mengapa mengorganisir anggota keluarga Anda dengan cara ini

11
00:00:30,950 --> 00:00:34,010
lebih baik daripada representasi daftar sederhana?

12
00:00:34,010 --> 00:00:36,630
Salah satu alasannya adalah bahwa struktur hirarkis,

13
00:00:36,630 --> 00:00:39,660
disebut 'pohon,' berisi informasi lebih dari daftar sederhana.

14
00:00:40,540 --> 00:00:43,520
Kita tahu hubungan keluarga antara orang

15
00:00:43,520 --> 00:00:45,440
hanya dengan memeriksa pohon.

16
00:00:45,440 --> 00:00:47,250
Selain itu, dapat mempercepat

17
00:00:47,250 --> 00:00:50,010
look-up waktu yang sangat, jika data pohon diurutkan.

18
00:00:50,010 --> 00:00:53,850
>> Kita tidak bisa mengambil keuntungan dari itu di sini, tapi kami akan melihat contoh ini segera.

19
00:00:53,850 --> 00:00:56,150
Setiap orang diwakili oleh simpul di pohon.

20
00:00:56,680 --> 00:00:58,370
Node dapat memiliki node anak

21
00:00:58,370 --> 00:01:00,350
serta simpul orangtua.

22
00:01:00,350 --> 00:01:02,390
Ini adalah istilah-istilah teknis,

23
00:01:02,390 --> 00:01:05,220
bahkan ketika menggunakan pohon untuk hal-hal selain keluarga.

24
00:01:05,220 --> 00:01:07,940
Simpul Alice memiliki 2 anak-anak dan tidak ada orang tua,

25
00:01:07,940 --> 00:01:11,500
sedangkan simpul Charlie memiliki 3 anak dan 1 orangtua.

26
00:01:11,500 --> 00:01:14,330
>> Sebuah simpul daun adalah salah satu yang tidak memiliki anak

27
00:01:14,330 --> 00:01:16,410
di tepi luar dari pohon.

28
00:01:16,410 --> 00:01:18,520
Simpul paling atas pohon, simpul akar,

29
00:01:18,520 --> 00:01:20,240
memiliki orangtua tidak.

30
00:01:20,240 --> 00:01:23,170
>> Sebuah pohon biner adalah jenis tertentu pohon,

31
00:01:23,170 --> 00:01:26,720
di mana setiap node memiliki, paling banyak, 2 anak-anak.

32
00:01:26,720 --> 00:01:30,490
Berikut adalah struct dari simpul dari pohon biner di C.

33
00:01:31,560 --> 00:01:34,530
Setiap node memiliki beberapa data yang terkait dengan itu

34
00:01:34,530 --> 00:01:36,520
dan 2 pointer ke node lain.

35
00:01:36,520 --> 00:01:38,110
>> Dalam pohon keluarga kami,

36
00:01:38,110 --> 00:01:40,900
data yang terkait adalah nama setiap orang.

37
00:01:40,900 --> 00:01:43,850
Berikut ini adalah int, meskipun itu bisa berupa apa saja.

38
00:01:44,510 --> 00:01:46,200
Ternyata,

39
00:01:46,200 --> 00:01:48,990
pohon biner tidak akan menjadi representasi yang baik untuk keluarga,

40
00:01:48,990 --> 00:01:51,960
karena orang sering memiliki lebih dari 2 anak.

41
00:01:51,960 --> 00:01:53,510
>> Sebuah pohon pencarian biner

42
00:01:53,510 --> 00:01:56,380
adalah jenis, khusus memerintahkan pohon biner

43
00:01:56,380 --> 00:01:58,090
yang memungkinkan kita untuk melihat nilai cepat.

44
00:01:58,740 --> 00:02:00,050
Anda mungkin telah memperhatikan

45
00:02:00,050 --> 00:02:02,010
bahwa setiap node di bawah akar pohon

46
00:02:02,010 --> 00:02:04,620
adalah akar dari pohon lain, disebut 'subtree.'

47
00:02:04,960 --> 00:02:07,090
Di sini, akar pohon adalah 6,

48
00:02:07,090 --> 00:02:09,860
dan anaknya, 2, adalah akar dari subtree.

49
00:02:09,860 --> 00:02:11,870
>> Dalam sebuah pohon pencarian biner

50
00:02:11,870 --> 00:02:15,790
semua nilai dari node benar subtree

51
00:02:15,790 --> 00:02:18,690
lebih besar dari nilai node. Berikut: 6.

52
00:02:18,690 --> 00:02:22,640
Nah, nilai-nilai dalam subtree kiri node

53
00:02:24,540 --> 00:02:26,890
kurang dari nilai node.

54
00:02:26,890 --> 00:02:28,620
Jika kita perlu untuk menangani nilai ganda,

55
00:02:28,620 --> 00:02:31,760
kita dapat mengubah salah satu dari mereka ke ketimpangan yang longgar,

56
00:02:31,760 --> 00:02:34,410
yang berarti nilai yang identik dapat jatuh baik di kiri atau kanan,

57
00:02:34,410 --> 00:02:37,400
asalkan kita konsisten tentang hal itu seluruh.

58
00:02:37,400 --> 00:02:39,620
Pohon ini adalah pohon pencarian biner

59
00:02:39,620 --> 00:02:41,540
karena mengikuti aturan-aturan ini.

60
00:02:42,320 --> 00:02:46,020
>> Ini adalah bagaimana hal itu akan terlihat jika kita berpaling semua node dalam structs C.

61
00:02:46,880 --> 00:02:48,410
Perhatikan bahwa jika seorang anak hilang,

62
00:02:48,410 --> 00:02:50,340
pointer adalah null.

63
00:02:50,340 --> 00:02:53,270
Bagaimana kita periksa untuk melihat apakah 7 adalah di pohon?

64
00:02:53,270 --> 00:02:55,020
Kami mulai dari akar.

65
00:02:55,020 --> 00:02:58,690
Tujuh lebih besar dari 6, jadi jika itu di pohon, itu harus ke kanan.

66
00:02:59,680 --> 00:03:03,650
Kemudian, itu adalah kurang dari 8, sehingga harus ditinggalkan.

67
00:03:03,650 --> 00:03:06,210
Di sini, kami telah menemukan 7.

68
00:03:06,210 --> 00:03:08,160
Sekarang, kita akan memeriksa 5.

69
00:03:08,160 --> 00:03:11,500
Lima kurang dari 6, sehingga harus ke kiri.

70
00:03:11,500 --> 00:03:13,460
Lima lebih besar dari 2,

71
00:03:13,460 --> 00:03:15,010
sehingga harus benar,

72
00:03:15,010 --> 00:03:18,100
dan juga lebih besar dari 4, sehingga harus benar lagi.

73
00:03:18,100 --> 00:03:20,300
Namun, ada tidak ada anak di sini.

74
00:03:20,300 --> 00:03:22,000
Pointer adalah null.

75
00:03:22,000 --> 00:03:24,270
Ini berarti bahwa 5 tidak di pohon kami.

76
00:03:24,270 --> 00:03:27,250
>> Kita bisa mencari pohon biner dengan kode berikut:

77
00:03:28,430 --> 00:03:31,140
Pada setiap node, kita periksa untuk melihat apakah kita telah menemukan

78
00:03:31,140 --> 00:03:33,020
nilai yang kita cari.

79
00:03:33,020 --> 00:03:35,740
Jika kita tidak menemukannya, kita menentukan apakah harus

80
00:03:35,740 --> 00:03:38,990
di kiri atau kanan dan periksa subtree.

81
00:03:38,990 --> 00:03:41,160
Loop ini akan terus turun pohon

82
00:03:41,160 --> 00:03:44,190
sampai tidak ada simpul anak pada salah satu bagian kiri atau kanan.

83
00:03:45,190 --> 00:03:48,600
>> Ingat bahwa 5 tidak di pohon.

84
00:03:48,600 --> 00:03:50,460
Bagaimana kita masukkan?

85
00:03:50,460 --> 00:03:52,370
Proses ini terlihat mirip dengan mencari.

86
00:03:52,370 --> 00:03:54,830
Kami iterate bawah pohon mulai dari 6,

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

88
00:03:57,040 --> 00:03:59,140
hak untuk 4,

89
00:03:59,140 --> 00:04:02,500
dan kanan lagi, tapi 4 memiliki anak tidak di sisi ini.

90
00:04:02,500 --> 00:04:06,090
Ini akan menjadi posisi baru untuk 5,

91
00:04:06,090 --> 00:04:08,500
dan akan mulai tanpa anak.

92
00:04:09,020 --> 00:04:12,220
>> Seberapa cepat operasi pada pohon pencarian biner?

93
00:04:12,220 --> 00:04:15,410
Ingat bahwa Bigohnotation berusaha untuk memberikan batas atas.

94
00:04:15,410 --> 00:04:17,390
Dalam kasus terburuk,

95
00:04:17,390 --> 00:04:19,480
pohon kami hanya bisa menjadi linked list

96
00:04:19,480 --> 00:04:22,220
yang berarti bahwa penyisipan, penghapusan, dan pencarian

97
00:04:22,220 --> 00:04:25,380
bisa memakan waktu sebanding dengan jumlah node dalam pohon.

98
00:04:25,380 --> 00:04:27,380
Ini adalah O (n).

99
00:04:27,380 --> 00:04:30,690
>> Sebagai contoh, berikut ini adalah sebuah pohon biner yang valid pencarian.

100
00:04:31,850 --> 00:04:34,020
Namun, jika kita mencoba untuk menemukan 9,

101
00:04:34,020 --> 00:04:36,760
kita harus melintasi setiap node.

102
00:04:36,760 --> 00:04:39,120
Hal ini tidak lebih baik dari sebuah linked list.

103
00:04:39,120 --> 00:04:41,410
Idealnya, kita ingin setiap node

104
00:04:41,410 --> 00:04:44,120
dari pohon pencarian biner kami memiliki 2 anak.

105
00:04:44,120 --> 00:04:46,370
Dengan cara ini, penyisipan, penghapusan dan pencarian

106
00:04:46,370 --> 00:04:50,190
akan mengambil, paling buruk, O (log n) waktu.

107
00:04:50,190 --> 00:04:52,470
Pohon dari sebelumnya bisa lebih seimbang,

108
00:04:52,470 --> 00:04:54,140
seperti ini.

109
00:04:54,140 --> 00:04:57,980
Sekarang, mencari nilai apapun membutuhkan, paling, 3 langkah.

110
00:04:57,980 --> 00:04:59,460
Pohon ini seimbang,

111
00:04:59,460 --> 00:05:01,190
makna yang memiliki kedalaman minimal

112
00:05:01,190 --> 00:05:03,680
relatif terhadap jumlah node.

113
00:05:03,680 --> 00:05:06,300
>> Mencari nilai dalam sebuah pohon pencarian biner seimbang

114
00:05:06,300 --> 00:05:09,540
mirip dengan pencarian biner pada array diurutkan.

115
00:05:09,540 --> 00:05:12,290
Padahal, jika kita tidak perlu memasukkan atau menghapus item,

116
00:05:12,290 --> 00:05:15,150
mereka berperilaku dengan cara yang persis sama.

117
00:05:15,150 --> 00:05:17,600
Namun, struktur pohon lebih baik

118
00:05:17,600 --> 00:05:19,530
untuk penanganan sisipan dan penghapusan

119
00:05:20,360 --> 00:05:22,670
>> Nama saya Bannus Van der Kloot.

120
00:05:22,670 --> 00:05:24,030
Ini adalah CS50.