1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [ნაწილი 7] [Less კომფორტული]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [ჰარვარდის უნივერსიტეტის]

3
00:00:04,890 --> 00:00:07,000
[ეს არის CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> კეთილი იყოს ნაწილი 7.

5
00:00:09,080 --> 00:00:11,330
მადლობა ქარიშხალი Sandy,

6
00:00:11,330 --> 00:00:13,440
ნაცვლად, რომელმაც ჩვეულებრივი მონაკვეთზე ამ კვირაში,

7
00:00:13,440 --> 00:00:17,650
ვაკეთებთ ამ მსვლელობა მეშვეობით, გავლით მონაკვეთზე კითხვები.

8
00:00:17,650 --> 00:00:22,830
მე ვაპირებ იყოს შემდეგ ერთად პრობლემა უცნობია 6 სპეციფიკაცია,

9
00:00:22,830 --> 00:00:25,650
და გადის ყველა კითხვას

10
00:00:25,650 --> 00:00:27,770
სექცია კითხვები მონაკვეთზე.

11
00:00:27,770 --> 00:00:30,940
თუ არის რამე კითხვა,

12
00:00:30,940 --> 00:00:32,960
გთხოვთ დაპოსტოთ ამ თემაზე CS50 განიხილავს.

13
00:00:32,960 --> 00:00:35,480
>> კარგად. მოდით დავიწყოთ.

14
00:00:35,480 --> 00:00:40,780
მარჯვენა ახლა მე ეძებს გვერდი 3 პრობლემა Set სპეციფიკაცია.

15
00:00:40,780 --> 00:00:44,110
ჩვენ ვაპირებთ დავიწყოთ ლაპარაკი ბინარული ხეები

16
00:00:44,110 --> 00:00:47,850
რადგან იმ ბევრი შესაბამისობა ამ კვირაში პრობლემა კომპლექტი -

17
00:00:47,850 --> 00:00:49,950
Huffman ხე კოდირების.

18
00:00:49,950 --> 00:00:55,000
ერთი პირველი მონაცემები სტრუქტურები ჩვენ ვისაუბრეთ on CS50 იყო მასივი.

19
00:00:55,000 --> 00:01:00,170
გახსოვდეთ, რომ მასივი არის თანმიმდევრობა ელემენტები -

20
00:01:00,170 --> 00:01:04,019
ყველა მსგავსი ტიპის - შენახული უფლება მომდევნო ერთმანეთს მეხსიერებაში.

21
00:01:04,019 --> 00:01:14,420
თუ მაქვს მთელი მასივი, რომ მე შემიძლია შევაჩერო გამოყენებისას ყუთები-ნომრები-რიცხვებით სტილი -

22
00:01:14,420 --> 00:01:20,290
ვთქვათ მაქვს 5 წლის პირველ ყუთი, მაქვს 7 მეორე,

23
00:01:20,290 --> 00:01:27,760
მაშინ მე 8, 10, 20 და საბოლოო ყუთში.

24
00:01:27,760 --> 00:01:33,000
გახსოვდეთ, ორი მართლაც კარგი ამ მასივი

25
00:01:33,000 --> 00:01:38,800
ვართ, რომ გვაქვს ამ მუდმივ დროში ხელმისაწვდომობის კონკრეტული ელემენტს

26
00:01:38,800 --> 00:01:40,500
 მასივში, თუ ჩვენ ვიცით მისი ინდექსი.

27
00:01:40,500 --> 00:01:44,670
მაგალითად, თუ მინდა დაიბრუნოს მესამე ელემენტია მასივი -

28
00:01:44,670 --> 00:01:47,870
ზე ინდექსი 2 გამოყენებით ჩვენი ნულოვანი დაფუძნებული ინდექსირებას სისტემა -

29
00:01:47,870 --> 00:01:52,220
მე სიტყვასიტყვით უბრალოდ უნდა გავაკეთოთ მარტივი მათემატიკური გაანგარიშება,

30
00:01:52,220 --> 00:01:56,170
hop ამ თანამდებობაზე მასივში,

31
00:01:56,170 --> 00:01:57,840
გაიყვანოს 8 რომ ინახება იქ,

32
00:01:57,840 --> 00:01:59,260
და მე კარგი წასვლა.

33
00:01:59,260 --> 00:02:03,350
>> ერთი ცუდი რამ ამ მასივი - რომ ჩვენ ვისაუბრეთ

34
00:02:03,350 --> 00:02:05,010
როდესაც ჩვენ განვიხილეთ უკავშირდება სიები -

35
00:02:05,010 --> 00:02:09,120
ის არის, რომ თუ მინდა ჩადეთ ელემენტს ამ მასივი,

36
00:02:09,120 --> 00:02:11,090
მე ვაპირებ უნდა გავაკეთოთ ზოგიერთი თავიანთ გარშემო.

37
00:02:11,090 --> 00:02:12,940
მაგალითად, ამ მასივი უფლება აქ

38
00:02:12,940 --> 00:02:16,850
არის დახარისხებული მიზნით - დახარისხების აღმავალი შეკვეთა -

39
00:02:16,850 --> 00:02:19,440
5, მაშინ 7, მაშინ 8, შემდეგ 10 და შემდეგ 20 -

40
00:02:19,440 --> 00:02:23,100
მაგრამ თუ მინდა ჩადეთ ნომერი 9 ამ მასივი,

41
00:02:23,100 --> 00:02:27,460
მე ვაპირებ უნდა გადაეტანა ზოგიერთი ელემენტები, რათა სივრცეში.

42
00:02:27,460 --> 00:02:30,440
ჩვენ შეგვიძლია დავხატოთ ამ აქ.

43
00:02:30,440 --> 00:02:35,650
მე ვაპირებ უნდა გადავიდეთ 5, 7, და შემდეგ 8;

44
00:02:35,650 --> 00:02:38,720
შექმნა უფსკრული სად შემიძლია დააყენა 9,

45
00:02:38,720 --> 00:02:45,910
და შემდეგ 10 და 20 შეიძლება წავიდეს უფლება 9.

46
00:02:45,910 --> 00:02:49,450
ეს არის სახის ტკივილი, რადგან უარესი სცენარით -

47
00:02:49,450 --> 00:02:54,350
როდესაც ჩვენ მქონე ჩასვათ ან დასაწყისში ან ბოლოში

48
00:02:54,350 --> 00:02:56,040
საქართველოს მასივი, დამოკიდებულია, როგორ ჩვენ გადავიდა -

49
00:02:56,040 --> 00:02:58,850
ჩვენ შეიძლება დასრულდება მდე მქონე გადაეტანა ყველა ელემენტები

50
00:02:58,850 --> 00:03:00,750
რომ ჩვენ გაკეთებული შენახვის მასივში.

51
00:03:00,750 --> 00:03:03,810
>> ასე რომ, რა იყო პირიქით ამ?

52
00:03:03,810 --> 00:03:09,260
პირიქით ეს იყო წასვლა ჩვენი დაკავშირებული სიაში მეთოდით რომელშიც -

53
00:03:09,260 --> 00:03:19,820
ნაცვლად შენახვის ელემენტები 5, 7, 8, 10, 20 და ყველა მომდევნო ერთმანეთს მეხსიერება -

54
00:03:19,820 --> 00:03:25,630
რაც ჩვენ ნაცვლად გააკეთა, შესანახად მათ სახის სადაც არ გვინდოდა შესანახად მათ

55
00:03:25,630 --> 00:03:32,470
ამ დაკავშირებული სიაში კვანძების რომელიც მე ხატვის აქ, სახის დროებითი.

56
00:03:32,470 --> 00:03:42,060
და შემდეგ ჩვენ უკავშირდება მათი ერთად გამოყენებით ამ შემდეგი პოინტერები.

57
00:03:42,060 --> 00:03:44,370
შემიძლია აქვს მაჩვენებელი 5 დან 7,

58
00:03:44,370 --> 00:03:46,420
კურსორი საწყისი 7 დან 8,

59
00:03:46,420 --> 00:03:47,770
კურსორი საწყისი 8 დან 10,

60
00:03:47,770 --> 00:03:51,220
და ბოლოს, კურსორი საწყისი 10 დან 20,

61
00:03:51,220 --> 00:03:54,880
და შემდეგ null კურსორი at 20 მიუთითებს, რომ იქ არაფერი დარჩა.

62
00:03:54,880 --> 00:03:59,690
ვაჭრობის საგანი, რომ გვაქვს აქ

63
00:03:59,690 --> 00:04:05,360
ის არის, რომ ახლა თუ გვინდა ჩადეთ ნომერი 9 ჩვენს დახარისხებული სია,

64
00:04:05,360 --> 00:04:08,270
ყველა ჩვენ უნდა გავაკეთოთ არის შექმნას ახალი კვანძის, 9,

65
00:04:08,270 --> 00:04:12,290
WIRE ის აღვნიშნო, რომ შესაბამის ადგილზე,

66
00:04:12,290 --> 00:04:20,630
და შემდეგ ხელახლა მავთულის 8 აღვნიშნო ქვემოთ 9.

67
00:04:20,630 --> 00:04:25,660
რომ საკმაოდ სწრაფად, თუ ვთქვათ ვიცით ზუსტად სად გვინდა ჩადეთ 9.

68
00:04:25,660 --> 00:04:32,610
მაგრამ ვაჭრობის სანაცვლოდ არის ის, რომ ჩვენ ახლა დაკარგა მუდმივი დროში ხელმისაწვდომობის

69
00:04:32,610 --> 00:04:36,230
რაიმე ელემენტს ჩვენს მონაცემთა სტრუქტურას.

70
00:04:36,230 --> 00:04:40,950
მაგალითად, თუ მინდა, რომ იპოვოთ მეოთხე ელემენტს ამ დაკავშირებული სიაში,

71
00:04:40,950 --> 00:04:43,510
მე ვაპირებ უნდა იწყება დასაწყისშივე სია

72
00:04:43,510 --> 00:04:48,930
და მუშაობა ჩემი გზას დათვლის node-by-node სანამ მე მეოთხე.

73
00:04:48,930 --> 00:04:55,870
>> იმისათვის, რომ უკეთ ხელმისაწვდომობის შესრულება ვიდრე უკავშირდება სია -

74
00:04:55,870 --> 00:04:59,360
არამედ შეინარჩუნოს ზოგიერთი სარგებელი, რომ ჩვენ გვქონდა

75
00:04:59,360 --> 00:05:01,800
თვალსაზრისით Insertion დროში საწყისი უკავშირდება სია -

76
00:05:01,800 --> 00:05:05,750
ორობითი ხე აპირებს უნდა გამოვიყენოთ ცოტა მეტი მეხსიერება.

77
00:05:05,750 --> 00:05:11,460
კერძოდ, ნაცვლად მხოლოდ ერთი მქონე მაჩვენებელი წელს ორობითი ხე კვანძში -

78
00:05:11,460 --> 00:05:13,350
მოსწონს დაკავშირებული სიაში კვანძის აკეთებს -

79
00:05:13,350 --> 00:05:16,950
ჩვენ ვაპირებთ დაამატოთ მეორე მომცეთ ორობითი ხე კვანძში.

80
00:05:16,950 --> 00:05:19,950
და არა მხოლოდ ერთი მქონე მომცეთ შემდეგი ელემენტს,

81
00:05:19,950 --> 00:05:24,420
ჩვენ ვაპირებთ აქვს მომცეთ მარცხენა ბავშვი და მარჯვნივ შვილი.

82
00:05:24,420 --> 00:05:26,560
>> მოდით დავხატოთ სურათი, ნახოთ კიდევ რა, რომ რეალურად გამოიყურება.

83
00:05:26,560 --> 00:05:31,350
ისევ და ისევ, მე ვაპირებ გამოიყენოთ ეს ყუთები და ისრებით.

84
00:05:31,350 --> 00:05:37,150
ორობითი ხე კვანძის დაიწყება off ერთად უბრალოდ მარტივი ყუთში.

85
00:05:37,150 --> 00:05:40,940
ის აპირებს ფართი ღირებულება,

86
00:05:40,940 --> 00:05:47,280
და მაშინ ის ასევე აპირებს ფართი მარცხენა ბავშვი და მარჯვნივ შვილი.

87
00:05:47,280 --> 00:05:49,280
მე ვაპირებ წარწერა ისინი აქ.

88
00:05:49,280 --> 00:05:57,560
ჩვენ ვაპირებთ აქვს მარცხენა ბავშვი, და შემდეგ ჩვენ ვაპირებთ აქვს უფლება ბავშვს.

89
00:05:57,560 --> 00:05:59,920
არსებობს ბევრი სხვადასხვა გზა ამით.

90
00:05:59,920 --> 00:06:02,050
ზოგჯერ, სივრცე და კომფორტი,

91
00:06:02,050 --> 00:06:06,460
მე რეალურად გავამახვილო ეს მოსწონს მე ვაკეთებ აქ ბოლოში

92
00:06:06,460 --> 00:06:10,910
სადაც მე ვაპირებ აქვს ღირებულების ზედა,

93
00:06:10,910 --> 00:06:14,060
და შემდეგ უფლება ბავშვის ქვედა-უფლებას,

94
00:06:14,060 --> 00:06:16,060
და მარცხენა ბავშვის ქვედა მარცხენა.

95
00:06:16,060 --> 00:06:20,250
უკან ამ ყველაზე დიაგრამაზე,

96
00:06:20,250 --> 00:06:22,560
ჩვენ გვაქვს ღირებულება ძალიან ზევით,

97
00:06:22,560 --> 00:06:25,560
მაშინ მარცხენა ბავშვის მაჩვენებელი, ხოლო შემდეგ ჩვენ გვაქვს უფლება და შვილის მაჩვენებელი.

98
00:06:25,560 --> 00:06:30,110
>> პრობლემის Set სპეციფიკაცია,

99
00:06:30,110 --> 00:06:33,110
ვსაუბრობთ ხატვის კვანძში, რომელსაც აქვს ღირებულება 7,

100
00:06:33,110 --> 00:06:39,750
და შემდეგ მარცხენა ბავშვის მაჩვენებელი, არის null, და მარჯვენა ბავშვის მაჩვენებელი, არის null.

101
00:06:39,750 --> 00:06:46,040
ჩვენ შეგიძლიათ ან წერენ კაპიტალის NULL წელს ფართი

102
00:06:46,040 --> 00:06:51,610
ორივე მარცხენა და ბავშვის უფლება ბავშვის, ან ჩვენ შეგვიძლია დავხატოთ ამ დახრილი ხაზი

103
00:06:51,610 --> 00:06:53,750
მეშვეობით თითოეულ ყუთები მიუთითოს, რომ ეს null.

104
00:06:53,750 --> 00:06:57,560
მე ვაპირებ ამას მხოლოდ იმიტომ, რომ მარტივი.

105
00:06:57,560 --> 00:07:03,700
რა ხედავთ აქ ორი გზა diagramming ძალიან მარტივი ორობითი ხე კვანძში

106
00:07:03,700 --> 00:07:07,960
სადაც ჩვენ გვყავს ღირებულება 7 და null ბავშვის პოინტერები.

107
00:07:07,960 --> 00:07:15,220
>> მეორე ნაწილი ჩვენი სპეციფიკაცია საუბრობს როგორ დავუკავშირდეთ უკავშირდება სიები -

108
00:07:15,220 --> 00:07:18,270
გახსოვდეთ, ჩვენ მხოლოდ ჰქონდა გამართავს შესახებ, რომ ძალიან პირველად ელემენტს სია

109
00:07:18,270 --> 00:07:20,270
უნდა გვახსოვდეს სრული სია -

110
00:07:20,270 --> 00:07:26,140
ანალოგიურად, ერთად ორობითი ხე, ჩვენ მხოლოდ უნდა გაიმართება ერთ მომცეთ ხე

111
00:07:26,140 --> 00:07:31,120
იმისათვის, რომ შევინარჩუნოთ კონტროლს მთელი მონაცემები სტრუქტურა.

112
00:07:31,120 --> 00:07:36,150
ეს სპეციალური ელემენტს ხე ეწოდება root node ხე.

113
00:07:36,150 --> 00:07:43,360
მაგალითად, თუ ამ ერთი კვანძის - ამ კვანძის შემცველი ღირებულება 7

114
00:07:43,360 --> 00:07:45,500
ერთად null მარცხენა და მარჯვენა ბავშვის პოინტერები -

115
00:07:45,500 --> 00:07:47,360
იყო მხოლოდ ღირებულების ჩვენი ხე,

116
00:07:47,360 --> 00:07:50,390
მაშინ ეს იქნება ჩვენი ძირეული კვანძის.

117
00:07:50,390 --> 00:07:52,240
ეს თავიდანვე ჩვენი ხე.

118
00:07:52,240 --> 00:07:58,530
ჩვენ ვხედავთ ამ პატარა უფრო ნათლად ერთხელ ჩვენ ვიწყებთ დასძინა მეტი კვანძების ჩვენი ხე.

119
00:07:58,530 --> 00:08:01,510
ნება მომეცით დახევის up ახალი გვერდი.

120
00:08:01,510 --> 00:08:05,000
>> ახლა ჩვენ ვაპირებთ მიაპყროს ხე, რომელსაც აქვს 7 ზე root,

121
00:08:05,000 --> 00:08:10,920
და 3 შიგნით მარცხენა ბავშვი და 9 შიგნით უფლება შვილი.

122
00:08:10,920 --> 00:08:13,500
ისევ და ისევ, ეს საკმაოდ მარტივია.

123
00:08:13,500 --> 00:08:26,510
გვაქვს 7, მიაპყროს კვანძის ამისთვის 3, კვანძში, 9,

124
00:08:26,510 --> 00:08:32,150
და მე ვაპირებ მითითებული მარცხენა ბავშვის მაჩვენებელი 7 დან აღვნიშნო, რომ კვანძის შემცველი 3,

125
00:08:32,150 --> 00:08:37,850
და მარჯვენა ბავშვის მაჩვენებელი of კვანძის შემცველი 7 დან კვანძის შემცველი 9.

126
00:08:37,850 --> 00:08:42,419
ახლა, მას შემდეგ, რაც 3 და 9 არ აქვთ ბავშვებს,

127
00:08:42,419 --> 00:08:48,500
ჩვენ სხვებისათვის ყველა მათი შვილი მითითებას იყოს null.

128
00:08:48,500 --> 00:08:56,060
აქ, root ჩვენი ხე შეესაბამება კვანძის შემცველი ნომერი 7.

129
00:08:56,060 --> 00:09:02,440
თქვენ ხედავთ, რომ, თუ ყველა ჩვენ გვაქვს არის მომცეთ, რომ ძირეული კვანძის,

130
00:09:02,440 --> 00:09:07,330
ჩვენ შეგვიძლია მაშინ გავლა ჩვენი ხე და დაშვების ორივე შვილი კვანძების -

131
00:09:07,330 --> 00:09:10,630
ორივე 3 და 9.

132
00:09:10,630 --> 00:09:14,820
არ უნდა შეინარჩუნოს მითითებას თითოეული კვანძის on ხე.

133
00:09:14,820 --> 00:09:22,080
კარგად. ახლა ჩვენ ვაპირებთ დაამატოთ კიდევ ერთი კვანძის ამ დიაგრამაზე.

134
00:09:22,080 --> 00:09:25,370
ჩვენ ვაპირებთ დაამატოთ კვანძის შემცველი 6,

135
00:09:25,370 --> 00:09:34,140
და ჩვენ ვაპირებთ დაამატოთ ეს როგორც უფლება ბავშვი კვანძის შემცველი 3.

136
00:09:34,140 --> 00:09:41,850
ამისათვის, მე ვაპირებ, რომ წაშალოს null მაჩვენებელი წელს 3-node

137
00:09:41,850 --> 00:09:47,750
და მავთული ის აღვნიშნო, რომ კვანძის შემცველი 6. კარგად.

138
00:09:47,750 --> 00:09:53,800
>> ამ ეტაპზე, მოდით წავიდეთ მეტი ცოტა ტერმინოლოგიას.

139
00:09:53,800 --> 00:09:58,230
უნდა დაიწყოს, იმ მიზეზით, რომ ამ ეწოდება ორობითი ხე კერძოდ

140
00:09:58,230 --> 00:10:00,460
არის ის, რომ მას აქვს ორი შვილი მითითებას.

141
00:10:00,460 --> 00:10:06,020
არსებობს სხვა სახის ხეები, რომ უფრო მეტი ბავშვი პოინტერები.

142
00:10:06,020 --> 00:10:10,930
კერძოდ, რა გააკეთეთ "შეეცდება" პრობლემების Set 5.

143
00:10:10,930 --> 00:10:19,310
თქვენ შეამჩნევთ, რომ რომ ცდილობენ, გქონდათ 27 სხვადასხვა მითითებას სხვადასხვა ბავშვებს -

144
00:10:19,310 --> 00:10:22,410
ერთი თითოეული 26 ასო ინგლისურ ანბანში,

145
00:10:22,410 --> 00:10:25,410
და შემდეგ 27 ამისთვის აპოსტროფი -

146
00:10:25,410 --> 00:10:28,900
ასე, რომ მსგავსი ტიპის ხე.

147
00:10:28,900 --> 00:10:34,070
მაგრამ აქ, რადგან ეს ორობითი, ჩვენ მხოლოდ ორი ბავშვი პოინტერები.

148
00:10:34,070 --> 00:10:37,880
>> გარდა ამისა root node რომ ჩვენ ვისაუბრეთ,

149
00:10:37,880 --> 00:10:41,470
ჩვენ ასევე სროლა გარშემო ეს ტერმინი "ბავშვი. '

150
00:10:41,470 --> 00:10:44,470
რას ნიშნავს ერთი კვანძის იყოს ბავშვის სხვა კვანძის?

151
00:10:44,470 --> 00:10:54,060
ეს სიტყვასიტყვით ნიშნავს, რომ ბავშვის კვანძში არის ბავშვის სხვა კვანძის

152
00:10:54,060 --> 00:10:58,760
თუ ეს სხვა კვანძის ერთი მისი შვილი პოინტერები მითითებული აღვნიშნო, რომ კვანძის.

153
00:10:58,760 --> 00:11:01,230
დააყენოს ამ შევიდა უფრო კონკრეტული ვადები,

154
00:11:01,230 --> 00:11:11,170
თუ 3 აღნიშნულია, რომ ერთი ბავშვის პოინტერები 7, მაშინ 3 არის ბავშვი 7.

155
00:11:11,170 --> 00:11:14,510
თუ ჩვენ უნდა გაერკვნენ, რა შვილები არიან 7 -

156
00:11:14,510 --> 00:11:18,510
ასევე, ჩვენ ვხედავთ, რომ 7 აქვს მომცეთ 3 და მომცეთ 9,

157
00:11:18,510 --> 00:11:22,190
ასე 9 და 3 არიან შვილები 7.

158
00:11:22,190 --> 00:11:26,650
ცხრა ვიზიტორების ბავშვებს, რადგან მისი შვილი მითითებები null,

159
00:11:26,650 --> 00:11:30,940
და 3 აქვს მხოლოდ ერთი შვილი, 6.

160
00:11:30,940 --> 00:11:37,430
ექვსი ასევე ვიზიტორების ბავშვებს, რადგან ორივე მისი მითითებები null, რომელიც ჩვენ მიაპყროს ახლავე.

161
00:11:37,430 --> 00:11:45,010
>> გარდა ამისა, ჩვენ საუბრობენ მშობლები კერძოდ კვანძში,

162
00:11:45,010 --> 00:11:51,100
და ეს არის, როგორც თქვენ მინდა ველით, საპირისპირო ამ ბავშვს აღწერა.

163
00:11:51,100 --> 00:11:58,620
თითოეული კვანძის აქვს მხოლოდ ერთი მშობლის - ნაცვლად ორი, როგორც თქვენ შეიძლება ველოდოთ ერთად ადამიანები.

164
00:11:58,620 --> 00:12:03,390
მაგალითად, მშობელი 3 არის 7.

165
00:12:03,390 --> 00:12:10,800
მშობელი 9 ასევე 7 და მშობელი 6 არის 3. ბევრი მას.

166
00:12:10,800 --> 00:12:15,720
ჩვენ ასევე გვაქვს თვალსაზრისით ლაპარაკი grandparents და შვილიშვილები,

167
00:12:15,720 --> 00:12:18,210
და ზოგადად ვსაუბრობთ წინაპართა

168
00:12:18,210 --> 00:12:20,960
და შთამომავლები კერძოდ კვანძში.

169
00:12:20,960 --> 00:12:25,710
წინაპარი კვანძის - ან წინაპრების, არამედ საქართველოს კვანძში -

170
00:12:25,710 --> 00:12:32,730
არის ყველა კვანძების, რომ ცრუობენ გზაზე საწყისი root to რომ კვანძის.

171
00:12:32,730 --> 00:12:36,640
მაგალითად, თუ მე ვერ კვანძის 6,

172
00:12:36,640 --> 00:12:46,430
შემდეგ წინაპრების ვაპირებთ იყოს როგორც 3 და 7.

173
00:12:46,430 --> 00:12:55,310
წინაპრები 9, მაგალითად, - თუ მე ეძებს კვანძის 9 -

174
00:12:55,310 --> 00:12:59,990
მაშინ წინაპარი 9 არის მხოლოდ 7.

175
00:12:59,990 --> 00:13:01,940
და შთამომავლები არიან ზუსტად საპირისპირო.

176
00:13:01,940 --> 00:13:05,430
თუკი მინდა შევხედოთ ყველა შთამომავლები 7,

177
00:13:05,430 --> 00:13:11,020
მაშინ უნდა შევხედოთ ყველა კვანძების ქვეშ იგი.

178
00:13:11,020 --> 00:13:16,950
ასე რომ, მე მაქვს 3, 9, და 6 როგორც შთამომავლები 7.

179
00:13:16,950 --> 00:13:24,170
>> საბოლოო ვადა, რომ ჩვენ ვსაუბრობთ არის ამ ცნება მყოფი ძმა.

180
00:13:24,170 --> 00:13:27,980
ძმა - სახის შემდეგ გასწვრივ ამ ოჯახის თვალსაზრისით -

181
00:13:27,980 --> 00:13:33,150
არიან კვანძების, რომლებიც ამავე დონის ხე.

182
00:13:33,150 --> 00:13:42,230
ასე რომ, 3 და 9 არიან ძმა რადგან ისინი ამავე დონის ხე.

183
00:13:42,230 --> 00:13:46,190
ორივე ერთი და იგივე მშობელი, 7.

184
00:13:46,190 --> 00:13:51,400
6 ვიზიტორების ძმა რადგან 9 არ აქვს არც შვილი.

185
00:13:51,400 --> 00:13:55,540
და 7 არ აქვს ძმა რადგან root ჩვენი ხე,

186
00:13:55,540 --> 00:13:59,010
და არსებობს მხოლოდ ოდესმე 1 root.

187
00:13:59,010 --> 00:14:02,260
7 ჰქონდეს ძმა იქ უნდა იყოს კვანძის ზემოთ 7.

188
00:14:02,260 --> 00:14:07,480
იქ უნდა იყოს მშობელი 7, რომლის დროსაც 7 აღარ იყოს ფესვი ხე.

189
00:14:07,480 --> 00:14:10,480
მაშინ ეს ახალი მშობელი 7 ასევე უნდა ჰქონდეს ბავშვს,

190
00:14:10,480 --> 00:14:16,480
და რომ ბავშვი ამის შემდეგ იქნება ძმა, 7.

191
00:14:16,480 --> 00:14:21,040
>> კარგად. მოძრავი.

192
00:14:21,040 --> 00:14:24,930
როდესაც ჩვენ დავიწყეთ ჩვენი განხილვა ორობითი ხეები,

193
00:14:24,930 --> 00:14:28,790
ჩვენ ვისაუბრეთ იმაზე, თუ როგორ ვაპირებდით გამოიყენოს მათ

194
00:14:28,790 --> 00:14:32,800
მოიპოვოს უპირატესობა ორივე კოლექტორები და დაკავშირებული სიები.

195
00:14:32,800 --> 00:14:37,220
და გზა ჩვენ ვაპირებთ, რომ არის ამ შეკვეთით ქონება.

196
00:14:37,220 --> 00:14:41,080
ჩვენ ვამბობთ, რომ ორობითი ხის უბრძანა, შესაბამისად სპეციფიკაცია,

197
00:14:41,080 --> 00:14:45,740
თუ თითოეული კვანძის ჩვენს ხე, ყველა მის შთამომავლობის მარცხენა -

198
00:14:45,740 --> 00:14:48,670
მარცხენა ბავშვი და ყველა მარცხენა ბავშვის შთამომავლები -

199
00:14:48,670 --> 00:14:54,510
აქვს ნაკლებად ღირებულებები, და ყველა კვანძების მარჯვენა -

200
00:14:54,510 --> 00:14:57,770
უფლება ბავშვი და ყველა უფლება ბავშვის შთამომავლები -

201
00:14:57,770 --> 00:15:02,800
აქვს კვანძების მეტი ღირებულების მიმდინარე კვანძის რომ ჩვენ შევხედავთ.

202
00:15:02,800 --> 00:15:07,850
Just სიმარტივის, ჩვენ ვაპირებთ ვივარაუდოთ, რომ არ არსებობს დუბლიკატი კვანძების ჩვენი ხე.

203
00:15:07,850 --> 00:15:11,180
მაგალითად, ამ ხის ჩვენ არ ვაპირებთ გამკლავება შემთხვევაში

204
00:15:11,180 --> 00:15:13,680
სადაც ჩვენ გვყავს ღირებულება 7 ზე root

205
00:15:13,680 --> 00:15:16,720
 და მაშინ ჩვენ ასევე გვაქვს ღირებულება 7 სხვაგან ხე.

206
00:15:16,720 --> 00:15:24,390
ამ შემთხვევაში, თქვენ შეამჩნევთ, რომ ეს ხე მართლაც უბრძანა.

207
00:15:24,390 --> 00:15:26,510
ჩვენ გვყავს ღირებულება 7 ზე root.

208
00:15:26,510 --> 00:15:29,720
ყველაფერი მარცხნივ 7 -

209
00:15:29,720 --> 00:15:35,310
თუ გაუქმება ყველა ამ პატარა ნიშნების აქ -

210
00:15:35,310 --> 00:15:40,450
ყველაფერი მარცხნივ 7 - 3 და 6 -

211
00:15:40,450 --> 00:15:49,410
იმ ღირებულებების ორივე არანაკლებ 7 და ყველაფერი მარჯვნივ - რომელიც მხოლოდ ამ 9 -

212
00:15:49,410 --> 00:15:53,450
მეტია 7.

213
00:15:53,450 --> 00:15:58,650
>> ეს არ არის მხოლოდ დაავალა ხე შემცველი ამ ღირებულებების,

214
00:15:58,650 --> 00:16:03,120
მაგრამ მოდით დავხატოთ რამდენიმე მათგანი.

215
00:16:03,120 --> 00:16:05,030
არსებობს ფაქტიურად მთელი bunch of გზები, რომ ჩვენ შეგვიძლია ამის გაკეთება.

216
00:16:05,030 --> 00:16:09,380
მე ვაპირებ გამოვიყენო სტენოგრამის მხოლოდ შენარჩუნება რამ მარტივი აქ -

217
00:16:09,380 --> 00:16:11,520
ვიდრე ხატვის მთლიანი ყუთები და ისრებით -

218
00:16:11,520 --> 00:16:14,220
მე უბრალოდ აპირებს გავამახვილო ნომრები და დაამატოთ ისრებით დამაკავშირებელი მათ.

219
00:16:14,220 --> 00:16:22,920
დასაწყებად, ჩვენ უბრალოდ დავწეროთ ჩვენი ორიგინალური ხე, სადაც ჩვენ გვქონდა 7, შემდეგ 3,

220
00:16:22,920 --> 00:16:25,590
და შემდეგ 3 აღნიშნა თავში უფლება 6,

221
00:16:25,590 --> 00:16:30,890
და 7 ჰქონდა უფლება ბავშვი რომ იყო 9.

222
00:16:30,890 --> 00:16:33,860
კარგად. რა არის სხვა გზა, რომ ჩვენ შეეძლო დაეწერა ეს ხე?

223
00:16:33,860 --> 00:16:38,800
იმის მაგივრად რომ 3 იყოს მარცხენა ბავშვი 7,

224
00:16:38,800 --> 00:16:41,360
ჩვენ შეგვიძლია აგრეთვე აქვს 6 იქნება მარცხენა ბავშვი 7,

225
00:16:41,360 --> 00:16:44,470
და მაშინ 3 იქნება მარცხენა ბავშვი 6.

226
00:16:44,470 --> 00:16:48,520
რომ გამოიყურება ასე, ხე სწორედ აქ, სადაც მე მოხვდით 7,

227
00:16:48,520 --> 00:16:57,860
მაშინ 6, მაშინ 3 და 9 მარჯვენა.

228
00:16:57,860 --> 00:17:01,490
ჩვენ ასევე არ აქვს 7 როგორც ჩვენი ძირეული კვანძის.

229
00:17:01,490 --> 00:17:03,860
ჩვენ შეგვიძლია აგრეთვე აქვს 6 როგორც ჩვენი ძირეული კვანძის.

230
00:17:03,860 --> 00:17:06,470
რა, რომ გამოიყურებოდეს?

231
00:17:06,470 --> 00:17:09,230
თუ ჩვენ ვაპირებთ, რომ შევინარჩუნოთ ეს უბრძანა ქონება,

232
00:17:09,230 --> 00:17:12,970
ყველაფერი მარცხნივ 6 უნდა იყოს ნაკლები.

233
00:17:12,970 --> 00:17:16,540
არსებობს მხოლოდ ერთი საშუალება, და რომ 3.

234
00:17:16,540 --> 00:17:19,869
მაგრამ შემდეგ, როგორც უფლება ბავშვი 6, ჩვენ გვაქვს ორი გზა.

235
00:17:19,869 --> 00:17:25,380
პირველი, ჩვენ შეგვეძლო 7 და შემდეგ 9,

236
00:17:25,380 --> 00:17:28,850
ან ჩვენ შეგვიძლია დავხატოთ მას - როგორც მე უნდა გავაკეთოთ აქ -

237
00:17:28,850 --> 00:17:34,790
სადაც ჩვენ გვყავს 9 როგორც უფლება ბავშვი 6,

238
00:17:34,790 --> 00:17:39,050
და შემდეგ 7 როგორც მარცხენა ბავშვი 9.

239
00:17:39,050 --> 00:17:44,240
>> ახლა, 7 და 6 არ არის ერთადერთი შესაძლო ღირებულებების root.

240
00:17:44,240 --> 00:17:50,200
ჩვენ შეგვიძლია აგრეთვე აქვს 3 იყოს root.

241
00:17:50,200 --> 00:17:52,240
რა მოხდება თუ 3 არის root?

242
00:17:52,240 --> 00:17:54,390
აქ რამ კიდევ ცოტა საინტერესო.

243
00:17:54,390 --> 00:17:58,440
სამი არა აქვს ღირებულებები, რომლებიც ნაკლები,

244
00:17:58,440 --> 00:18:02,070
ისე, რომ მთელი მარცხენა მხარე ხის უბრალოდ იქნება null.

245
00:18:02,070 --> 00:18:03,230
აქ არ იქნება არაფერი არსებობს.

246
00:18:03,230 --> 00:18:07,220
მარჯვნივ, ჩვენ შეგვიძლია ჩამოვთვალოთ რამ აღმავალი შეკვეთა.

247
00:18:07,220 --> 00:18:15,530
ჩვენ შეგვეძლო 3, მაშინ 6, მაშინ 7, მაშინ 9.

248
00:18:15,530 --> 00:18:26,710
ან, შეიძლება გავაკეთოთ 3, მაშინ 6, შემდეგ 9, შემდეგ 7.

249
00:18:26,710 --> 00:18:35,020
ან, შეიძლება გავაკეთოთ 3, მაშინ 7, მაშინ 6, შემდეგ 9.

250
00:18:35,020 --> 00:18:40,950
ან, 3, 7 - რეალურად არა, ჩვენ ვერ 7 უქმნით.

251
00:18:40,950 --> 00:18:43,330
სწორედ ჩვენი ერთი რამ არსებობს.

252
00:18:43,330 --> 00:18:54,710
ჩვენ შეგვიძლია გავაკეთოთ 9, და შემდეგ 9 შეგვიძლია 6 და შემდეგ 7.

253
00:18:54,710 --> 00:19:06,980
ან, შეგვიძლია გავაკეთოთ 3, შემდეგ 9, შემდეგ 7 და შემდეგ 6.

254
00:19:06,980 --> 00:19:12,490
>> ერთი რამ გავამახვილო თქვენი ყურადღება აქ არის

255
00:19:12,490 --> 00:19:14,510
რომ ეს ხეები ხართ პატარა უცნაური ორიენტირებული.

256
00:19:14,510 --> 00:19:17,840
კერძოდ, თუ დავაკვირდებით 4 ხეები მარჯვენა მხარეს -

257
00:19:17,840 --> 00:19:20,930
მე შემოხაზეს მათ, აქ -

258
00:19:20,930 --> 00:19:28,410
ამ ხეები გამოიყურებოდეს თითქმის ზუსტად ისევე უკავშირდება სიაში.

259
00:19:28,410 --> 00:19:32,670
თითოეული კვანძის აქვს მხოლოდ ერთი შვილი,

260
00:19:32,670 --> 00:19:38,950
და ამიტომ ჩვენ არ გვაქვს ამ ხის მსგავსი სტრუქტურა, რომელიც ჩვენ ვხედავთ, მაგალითად,

261
00:19:38,950 --> 00:19:44,720
 ამ ერთი მარტოხელა ხე მეტი აქ ქვედა მარცხენა.

262
00:19:44,720 --> 00:19:52,490
ეს ხეები ფაქტობრივად მოუწოდა degenerate ბინარული ხეები,

263
00:19:52,490 --> 00:19:54,170
და ჩვენ ვსაუბრობთ ამ უფრო მომავალში -

264
00:19:54,170 --> 00:19:56,730
განსაკუთრებით თუ კი მიიღოს სხვა კომპიუტერულ მეცნიერებათა კურსებს.

265
00:19:56,730 --> 00:19:59,670
ეს ჯიშებია degenerate.

266
00:19:59,670 --> 00:20:03,780
ისინი არ ძალიან სასარგებლო, რადგან, მართლაც, ამ სტრუქტურის lends თავად

267
00:20:03,780 --> 00:20:08,060
 საძიებელი ჯერ მსგავსი უკავშირდება სიაში.

268
00:20:08,060 --> 00:20:13,050
ჩვენ არ მიიღოთ ისარგებლოს დამატებითი მეხსიერება - ეს ზედმეტი მიმთითებელი -

269
00:20:13,050 --> 00:20:18,840
რადგან ჩვენი სტრუქტურა მყოფი ცუდი ამ გზით.

270
00:20:18,840 --> 00:20:24,700
იმის ნაცვლად, რომ წასულიყვნენ და შესამუშაევბლად ბინარული ხეები, რომ აქვს 9 საათზე ფესვი,

271
00:20:24,700 --> 00:20:27,220
რაც საბოლოო შემთხვევაში, რომ ჩვენ გვყავს,

272
00:20:27,220 --> 00:20:32,380
ჩვენ ნაცვლად, ამ ეტაპზე, მიმდინარეობს გაიგო ცოტა ამ სხვა ვადა

273
00:20:32,380 --> 00:20:36,150
ჩვენ ვიყენებთ, როდესაც საუბარია ხეები, რომელსაც სიმაღლე.

274
00:20:36,150 --> 00:20:45,460
>> სიმაღლე ხე არის დაშორება root to ყველაზე შორეულ კვანძში,

275
00:20:45,460 --> 00:20:48,370
ან საკმაოდ რაოდენობის hops რომ თქვენ უნდა გააკეთოთ, რათა

276
00:20:48,370 --> 00:20:53,750
იწყება root და შემდეგ დასრულდება up ყველაზე შორეულ-node in ხე.

277
00:20:53,750 --> 00:20:57,330
დავხედოთ ზოგიერთი ხეები, რომ ჩვენ შედგენილი უფლება აქ,

278
00:20:57,330 --> 00:21:07,870
ვხედავთ, რომ თუ ავიღებთ ამ ხის ზედა მარცხენა კუთხეში და ჩვენ იწყება 3,

279
00:21:07,870 --> 00:21:14,510
მაშინ ჩვენ უნდა გააკეთოთ 1 hop მისაღებად 6, მეორე hop მისაღებად 7,

280
00:21:14,510 --> 00:21:20,560
და მესამე hop მისაღებად 9.

281
00:21:20,560 --> 00:21:26,120
ასე რომ, სიმაღლე ამ ხე არის 3.

282
00:21:26,120 --> 00:21:30,640
ჩვენ შეგვიძლია იგივე გავაკეთოთ სავარჯიშო სხვა ხეები განსაზღვრავდა ამ მწვანე,

283
00:21:30,640 --> 00:21:40,100
და ჩვენ ვხედავთ, რომ სიმაღლე ყველა ამ ხეები ასევე მართლაც 3.

284
00:21:40,100 --> 00:21:45,230
სწორედ იმ ნაწილს, რომელსაც ხდის მათ degenerate -

285
00:21:45,230 --> 00:21:53,750
რომ მათი სიმაღლე მხოლოდ ერთი ნაკლები რაოდენობის კვანძების მთელი ხე.

286
00:21:53,750 --> 00:21:58,400
თუ დავაკვირდებით ამ სხვა ხე რომ ალყაშემორტყმული წითელი, მეორეს მხრივ,

287
00:21:58,400 --> 00:22:03,920
ჩვენ ვხედავთ, რომ ყველაზე შორეული-ფოთოლი კვანძების არიან 6 და 9 -

288
00:22:03,920 --> 00:22:06,940
წასვლამდე მყოფი იმ კვანძების, რომ არ მყავს ბავშვები.

289
00:22:06,940 --> 00:22:11,760
ამიტომ, რათა მიიღონ root node ან 6 ან 9,

290
00:22:11,760 --> 00:22:17,840
ჩვენ უნდა გააკეთოთ ერთი hop მისაღებად 7 და შემდეგ მეორე hop მისაღებად 9,

291
00:22:17,840 --> 00:22:21,240
ანალოგიურად, მხოლოდ მეორე hop საწყისი 7 მისაღებად 6.

292
00:22:21,240 --> 00:22:29,080
ასე რომ, სიმაღლე ამ ხის გამო აქ არის მხოლოდ 2.

293
00:22:29,080 --> 00:22:35,330
თქვენ შეგიძლიათ უკან და გავაკეთოთ, რომ ყველა სხვა ხეები, რომ ჩვენ ადრე ისაუბრეს

294
00:22:35,330 --> 00:22:37,380
დაწყებული 7 და 6,

295
00:22:37,480 --> 00:22:42,500
და თქვენ ნახავთ, რომ სიმაღლე ყველა იმ ხეები ასევე 2.

296
00:22:42,500 --> 00:22:46,320
>> მიზეზი ჩვენ ვსაუბრობთ უბრძანა ბინარული ხეები

297
00:22:46,320 --> 00:22:50,250
და რატომ ისინი ზემოთ არის, რადგან თქვენ შეგიძლიათ ძებნის საშუალებით მათ

298
00:22:50,250 --> 00:22:53,810
ძალიან გავს გზა ძებნას მეტი დახარისხებული მასივი.

299
00:22:53,810 --> 00:22:58,720
ეს არის სადაც ვსაუბრობთ მისაღებად რომ გაუმჯობესებული lookup დრო

300
00:22:58,720 --> 00:23:02,730
მეტი მარტივი უკავშირდება სიაში.

301
00:23:02,730 --> 00:23:05,010
With უკავშირდება სია - თუ გინდათ იპოვოთ განსაკუთრებული ელემენტს -

302
00:23:05,010 --> 00:23:07,470
თქვენ საუკეთესო აპირებს გარკვეული ხაზოვანი ძებნა

303
00:23:07,470 --> 00:23:10,920
სადაც თქვენ დაიწყოს დასაწყისში სიაში და ჰოპ ერთი მიერ ერთი -

304
00:23:10,920 --> 00:23:12,620
ერთი კვანძის ერთი კვანძის -

305
00:23:12,620 --> 00:23:16,060
მთელი სია, სანამ თქვენთვის რასაც თქვენ ეძებს.

306
00:23:16,060 --> 00:23:19,440
ამასთან, თუ თქვენ გაქვთ ორობითი ხე რომ ინახება ამ ლამაზი ფორმატში,

307
00:23:19,440 --> 00:23:23,300
შეგიძლიათ რეალურად მიიღოთ მეტი ორობითი ძებნა გრძელდება

308
00:23:23,300 --> 00:23:25,160
სადაც თქვენ გათიშე და დაიპყროთ

309
00:23:25,160 --> 00:23:29,490
და ძებნის საშუალებით შესაბამისი ნახევარში ხე თითოეული ნაბიჯი.

310
00:23:29,490 --> 00:23:32,840
ვნახოთ, როგორ, რომ სამუშაოები.

311
00:23:32,840 --> 00:23:38,850
>> თუ ჩვენ გვაქვს - ისევ, რომ დაუბრუნდეს ჩვენს ორიგინალური ხე -

312
00:23:38,850 --> 00:23:46,710
ჩვენ ვიწყებთ დილის 7, ჩვენ გვაქვს 3 მარცხენა, 9 მარჯვენა,

313
00:23:46,710 --> 00:23:51,740
და ქვეშ 3 გვაქვს 6.

314
00:23:51,740 --> 00:24:01,880
თუ გვინდა, რომ მოძებნოთ ნომერი 6 ამ ხეს, ჩვენ გვინდა იწყება root.

315
00:24:01,880 --> 00:24:08,910
ჩვენ გვინდა შევადაროთ ღირებულების ჩვენ ვეძებთ, ამბობენ 6,

316
00:24:08,910 --> 00:24:12,320
ღირებულების შენახული კვანძში, რომ ჩვენ გაკეთებული ეძებს, 7,

317
00:24:12,320 --> 00:24:21,200
ნახავთ, რომ 6 მართლაც არანაკლებ 7, ასე რომ ჩვენ გვინდა გადავა მარცხნივ.

318
00:24:21,200 --> 00:24:25,530
თუ ღირებულება 6 იყო აღემატება 7, გვექნებოდა ნაცვლად გადავიდა უფლება.

319
00:24:25,530 --> 00:24:29,770
მას შემდეგ, რაც ჩვენ ვიცით, რომ - გამო სტრუქტურა ჩვენი უბრძანა ორობითი ხე -

320
00:24:29,770 --> 00:24:33,910
ყველა ღირებულებების არანაკლებ 7 ვაპირებთ ინახება მარცხნივ 7,

321
00:24:33,910 --> 00:24:40,520
არ საჭიროებას კი გადაიტვირთოთ გადახედეთ მარჯვენა მხარეს ხე.

322
00:24:40,520 --> 00:24:43,780
ერთხელ ჩვენ გადავა მარცხნივ და ჩვენ ახლა კვანძის შემცველი 3,

323
00:24:43,780 --> 00:24:48,110
ჩვენ შეგვიძლია გავაკეთოთ, რომ იგივე შედარებით, სადაც შევადარებთ 3 და 6.

324
00:24:48,110 --> 00:24:52,430
და ჩვენ ვხედავთ, რომ სანამ 6 - ღირებულება ჩვენ ვეძებთ - მეტია 3,

325
00:24:52,430 --> 00:24:58,580
ჩვენ შეგვიძლია წასვლა მარჯვენა მხარეს კვანძის შემცველი 3.

326
00:24:58,580 --> 00:25:02,670
იქ არ არის მარცხენა მხარეს აქ, რათა შევძლოთ და არ უგულებელყო რომ.

327
00:25:02,670 --> 00:25:06,510
მაგრამ ჩვენ მხოლოდ ვიცით, რომ რადგან ჩვენ ეძებს ხის თავად,

328
00:25:06,510 --> 00:25:08,660
და ვხედავთ, რომ ხე არ აქვს შვილი.

329
00:25:08,660 --> 00:25:13,640
>> ასევე საკმაოდ ადვილად გამოიყურებოდეს up 6 ამ ხეს თუ ვაკეთებთ მას საკუთარ თავს, როგორც ადამიანი,

330
00:25:13,640 --> 00:25:16,890
მაგრამ მოდით დაიცვას ამ პროცესში მექანიკურად მოსწონს კომპიუტერის ყველაფერს გააკეთებს

331
00:25:16,890 --> 00:25:18,620
ნამდვილად მესმის ალგორითმი.

332
00:25:18,620 --> 00:25:26,200
ამ ეტაპზე, ჩვენ ახლა ეძებს კვანძში, რომელიც შეიცავს 6,

333
00:25:26,200 --> 00:25:29,180
და ჩვენ ვეძებთ ღირებულება 6,

334
00:25:29,180 --> 00:25:31,740
ასე რომ, მართლაც, ჩვენ ნაპოვნი შესაბამისი კვანძის.

335
00:25:31,740 --> 00:25:35,070
ჩვენ ვნახეთ ღირებულება 6 ჩვენს ხე, და ჩვენ ვერ შეწყვეტენ ჩვენი ძიება.

336
00:25:35,070 --> 00:25:37,330
ამ ეტაპზე, დამოკიდებულია რა ხდება,

337
00:25:37,330 --> 00:25:41,870
ჩვენ შეგვიძლია ვთქვათ, დიახ, ჩვენ მოვნახეთ ღირებულება 6, ის არსებობს ჩვენს ხე.

338
00:25:41,870 --> 00:25:47,640
ან, თუ ჩვენ გეგმავს ჩადეთ კვანძის ან რაღაც, ჩვენ შეგვიძლია გავაკეთოთ, რომ ამ ეტაპზე.

339
00:25:47,640 --> 00:25:53,010
>> მოდით რამდენიმე lookups უბრალოდ, თუ რამდენად ამ სამუშაოები.

340
00:25:53,010 --> 00:25:59,390
მოდით შევხედოთ რა მოხდება თუ ჩვენ უნდა შევეცადოთ და ეძებოთ ღირებულება 10.

341
00:25:59,390 --> 00:26:02,970
თუ ჩვენ უნდა გამოიყურებოდეს up ღირებულება 10, გვინდა იწყება root.

342
00:26:02,970 --> 00:26:07,070
მე მინდა ვხედავ, რომ 10 მეტია 7, ასე რომ ჩვენ გვინდა გადავა უფლება.

343
00:26:07,070 --> 00:26:13,640
მე მინდა მოხვედრა 9 და შედარების 9 დან 10 და ვხედავ, რომ 9 მართლაც არანაკლებ 10.

344
00:26:13,640 --> 00:26:16,210
ასე რომ კიდევ ერთხელ, ჩვენ გვინდა ცდილობენ გადავიდეს უფლება.

345
00:26:16,210 --> 00:26:20,350
მაგრამ ამ ეტაპზე, ჩვენ გვინდა რომ ჩვენ დროს null კვანძში.

346
00:26:20,350 --> 00:26:23,080
არაფერია იქ. არაფერია აქ 10 უნდა იყოს.

347
00:26:23,080 --> 00:26:29,360
ეს არის სადაც შეგვიძლია ანგარიშს მარცხი - რომ არსებობს ნამდვილად არ 10 წლის ხე.

348
00:26:29,360 --> 00:26:35,420
და ბოლოს, მოდით გავლა შემთხვევაში ჩვენ ცდილობს გამოიყურებოდეს up 1 in ხე.

349
00:26:35,420 --> 00:26:38,790
ეს არის მსგავსი რა მოხდება თუ გადავხედავთ up 10, გარდა ნაცვლად აპირებს უფლება,

350
00:26:38,790 --> 00:26:41,260
ჩვენ ვაპირებთ წასვლა მარცხენა.

351
00:26:41,260 --> 00:26:46,170
ჩვენ იწყება 7 და ვხედავ, რომ 1 ნაკლებია, ვიდრე 7, ასე რომ ჩვენ გადავა მარცხნივ.

352
00:26:46,170 --> 00:26:51,750
ჩვენ მისაღებად 3 და ვხედავ, რომ 1 არის არანაკლებ 3, ასე რომ კიდევ ერთხელ ვცდილობთ გადასვლის მარცხენა.

353
00:26:51,750 --> 00:26:59,080
ამ ეტაპზე ჩვენ გვაქვს null კვანძში, ამიტომ კიდევ ერთხელ შეგვიძლია ანგარიშს უკმარისობა.

354
00:26:59,080 --> 00:27:10,260
>> თუ გსურთ გაიგოთ უფრო მეტი ბინარული ხეები,

355
00:27:10,260 --> 00:27:14,420
არსებობს მთელი bunch of fun პატარა პრობლემები, რომელიც შეგიძლიათ გააკეთოთ მათთან.

356
00:27:14,420 --> 00:27:19,450
მე გთავაზობთ პრაქტიკოსი ნახაზი აქედან დიაგრამების ერთი მიერ ერთი

357
00:27:19,450 --> 00:27:21,910
და შემდეგ მთელი საქართველოს სხვადასხვა ნაბიჯები,

358
00:27:21,910 --> 00:27:25,060
რადგან ეს მოვა სუპერ მოსახერხებელი

359
00:27:25,060 --> 00:27:27,480
არა მხოლოდ მაშინ, როდესაც თქვენ აკეთებთ Huffman კოდირების პრობლემა კომპლექტი

360
00:27:27,480 --> 00:27:29,390
არამედ მომავალი კურსები -

361
00:27:29,390 --> 00:27:32,220
მხოლოდ სასწავლო როგორ შესამუშაევბლად ამ მონაცემების სტრუქტურებისა და ვფიქრობ მეშვეობით პრობლემები

362
00:27:32,220 --> 00:27:38,000
ერთად კალამი და ქაღალდი ან, ამ შემთხვევაში, iPad და Stylus.

363
00:27:38,000 --> 00:27:41,000
>> ამ ეტაპზე, თუმცა, ჩვენ ვაპირებთ გადაადგილება დაკავდით კოდირების პრაქტიკა

364
00:27:41,000 --> 00:27:44,870
და ფაქტობრივად თამაში ამ ბინარული ხეები და ვხედავ.

365
00:27:44,870 --> 00:27:52,150
მე ვაპირებ გადართოთ უკან მეტი ჩემს კომპიუტერში.

366
00:27:52,150 --> 00:27:58,480
ამ ნაწილში მონაკვეთზე, ნაცვლად გამოყენებით CS50 Run ან CS50 სივრცეები,

367
00:27:58,480 --> 00:28:01,500
მე ვაპირებ გამოვიყენო ელექტრო მოწყობილობების.

368
00:28:01,500 --> 00:28:04,950
>> შემდეგ ერთად პრობლემა Set სპეციფიკაცია,

369
00:28:04,950 --> 00:28:07,740
მე ვხედავ, რომ მე უნდა გაიხსნას ელექტრო მოწყობილობების,

370
00:28:07,740 --> 00:28:11,020
გადასვლა ჩემს Dropbox ფოლდერი, შექმენით ფოლდერი მოუწოდა ნაწილი 7,

371
00:28:11,020 --> 00:28:15,730
და შემდეგ შევქმნათ ფაილი სახელად binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Here We Go. მაქვს ელექტრო უკვე ღია.

373
00:28:22,050 --> 00:28:25,910
მე ვაპირებ დახევის up ტერმინალში.

374
00:28:25,910 --> 00:28:38,250
მე ვაპირებ წასვლა Dropbox საქაღალდეში, მიიღოს დირექტორია მოუწოდა section7,

375
00:28:38,250 --> 00:28:42,230
და ვხედავ ეს სრულიად ცარიელი.

376
00:28:42,230 --> 00:28:48,860
ახლა მე ვაპირებ გახსენით binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
კარგად. Here We Go - ცარიელი ფაილი.

378
00:28:51,750 --> 00:28:54,330
>> მოდით დავუბრუნდეთ სპეციფიკაცია.

379
00:28:54,330 --> 00:28:59,850
სპეციფიკაცია სთხოვს, რათა შეიქმნას ახალი ტიპის განსაზღვრება

380
00:28:59,850 --> 00:29:03,080
ამისთვის ორობითი ხე კვანძის შემცველი int ღირებულებებს -

381
00:29:03,080 --> 00:29:07,110
ისევე, როგორც ღირებულებების, რომ ჩვენ მიიპყრო გარეთ ჩვენს diagramming ადრე.

382
00:29:07,110 --> 00:29:11,740
ჩვენ ვაპირებთ გამოვიყენოთ ეს boilerplate typedef, რომ ჩვენ გავაკეთეთ უფლება აქ

383
00:29:11,740 --> 00:29:14,420
რომ თქვენ უნდა აღიაროს საწყისი პრობლემა Set 5 -

384
00:29:14,420 --> 00:29:19,190
თუ თქვენ არ hash table გზა დაპყრობის speller პროგრამა.

385
00:29:19,190 --> 00:29:22,540
თქვენ ასევე უნდა აღიაროს იგი გასულ კვირას სექციაში

386
00:29:22,540 --> 00:29:23,890
სადაც ჩვენ ვისაუბრეთ უკავშირდება სიები.

387
00:29:23,890 --> 00:29:27,870
გვაქვს ამ typedef of struct კვანძში,

388
00:29:27,870 --> 00:29:34,430
და ჩვენ, ამ struct კვანძში ამ სახელით struct კვანძის წინასწარ

389
00:29:34,430 --> 00:29:39,350
ასე, რომ ჩვენ შეგვიძლია შემდეგ უწოდებს, რადგან ჩვენ გვინდა struct კვანძის პოინტერები

390
00:29:39,350 --> 00:29:45,740
როგორც ნაწილი ჩვენი struct, მაგრამ ჩვენ მაშინ ალყაში აქცევს ამ -

391
00:29:45,740 --> 00:29:47,700
უფრო სწორად, თან ერთვის ამ - ში typedef

392
00:29:47,700 --> 00:29:54,600
ასე რომ, მოგვიანებით კოდი, ჩვენ შეგვიძლია ეხება ამ struct როგორც მხოლოდ კვანძის ნაცვლად struct კვანძში.

393
00:29:54,600 --> 00:30:03,120
>> ეს იქნება ძალიან ჰგავს საგნით დაკავშირებული სიაში განმარტება, რომ ჩვენ ვნახეთ გასულ კვირას.

394
00:30:03,120 --> 00:30:20,070
ამისათვის მოდით დავიწყო წერილობით გარეთ boilerplate.

395
00:30:20,070 --> 00:30:23,840
ჩვენ ვიცით, რომ ჩვენ გვყავს მთელ რიცხვს ღირებულება,

396
00:30:23,840 --> 00:30:32,170
ამიტომ ჩვენ დასვა int ღირებულება, ხოლო შემდეგ ნაცვლად, რომელმაც მხოლოდ ერთი მომცეთ შემდეგი ელემენტს -

397
00:30:32,170 --> 00:30:33,970
როგორც ჩვენ შემოიერთა საგნით დაკავშირებული სიები -

398
00:30:33,970 --> 00:30:38,110
ჩვენ ვაპირებთ აქვს მარცხნივ და მარჯვნივ ბავშვის პოინტერები.

399
00:30:38,110 --> 00:30:42,880
რომ საკმაოდ მარტივია ძალიან - struct კვანძის * მარცხენა ბავშვი;

400
00:30:42,880 --> 00:30:51,190
და struct კვანძის * უფლება ბავშვის. ზემოთ.

401
00:30:51,190 --> 00:30:54,740
რომ ჰგავს საკმაოდ კარგი დასაწყისია.

402
00:30:54,740 --> 00:30:58,530
მოდით დავუბრუნდეთ სპეციფიკაცია.

403
00:30:58,530 --> 00:31:05,030
>> ახლა ჩვენ უნდა განაცხადოს გლობალური კვანძის * ცვლადი ამისთვის ფესვი ხე.

404
00:31:05,030 --> 00:31:10,590
ჩვენ ვაპირებთ, რომ ეს გლობალური ისევე ჩვენ მივიღეთ პირველი მაჩვენებელი ჩვენს უკავშირდება სიაში ასევე გლობალური.

405
00:31:10,590 --> 00:31:12,690
ეს იმდენად, რომ ფუნქციების, რომ ჩვენ წერენ

406
00:31:12,690 --> 00:31:16,180
ჩვენ არ გვაქვს შენარჩუნება გავლით გარშემო ამ root -

407
00:31:16,180 --> 00:31:19,620
თუმცა ჩვენ ვხედავთ, რომ თუ გვინდა დავწეროთ ამ ფუნქციების რეკურსიული,

408
00:31:19,620 --> 00:31:22,830
ეს შესაძლოა უკეთესი კი არ უნდა გაიაროს ეს გარშემო, როგორც გლობალური პირველ რიგში

409
00:31:22,830 --> 00:31:28,090
და ნაცვლად ინიციალიზაცია იგი ადგილობრივად თქვენს მთავარ ფუნქციას.

410
00:31:28,090 --> 00:31:31,960
მაგრამ ჩვენ გავაკეთებთ გლობალურად უნდა დაიწყოს.

411
00:31:31,960 --> 00:31:39,920
ისევ და ისევ, ჩვენ მივცემ რამდენიმე ფართების, და მე ვაპირებ განაცხადოს კვანძის * root.

412
00:31:39,920 --> 00:31:46,770
უბრალოდ, დარწმუნდით, რომ მე არ დატოვებენ ამ uninitialized, მე ვაპირებ ვაყენებთ მას ტოლი null.

413
00:31:46,770 --> 00:31:52,210
ახლა კი, მთავარი ფუნქცია - რაც ჩვენ წერენ მართლაც სწრაფად სწორედ აქ -

414
00:31:52,210 --> 00:32:00,450
int ძირითადი (int argc, const char * argv []) -

415
00:32:00,450 --> 00:32:10,640
და მე ვაპირებ დაიწყება გამოცხადების ჩემი argv მასივს როგორც const მხოლოდ ისე, რომ მე ვიცი

416
00:32:10,640 --> 00:32:14,550
რომ ეს არგუმენტებია არგუმენტს, რომელიც მე ალბათ არ მინდა ცვლილებები.

417
00:32:14,550 --> 00:32:18,390
თუკი მინდა ცვლილებები მათ მე უნდა სავარაუდოდ მიღების ასლები მათ.

418
00:32:18,390 --> 00:32:21,740
თქვენ ნახავთ ამ ბევრს კოდი.

419
00:32:21,740 --> 00:32:25,440
ეს ჯარიმა ან გზა. ეს ჯარიმა უნდა დატოვონ, როგორც - გამომრჩეს const თუ გსურთ.

420
00:32:25,440 --> 00:32:28,630
მე, როგორც წესი, დააყენოს ის მხოლოდ ისე, რომ მე შეგახსენებთ თავს

421
00:32:28,630 --> 00:32:33,650
 რომ მე ალბათ არ მინდა ცვლილებები იმ არგუმენტებს.

422
00:32:33,650 --> 00:32:39,240
>> როგორც ყოველთვის, მე ვაპირებ მოიცავს ამ დაბრუნების 0 ხაზის დასასრულს მთავარ.

423
00:32:39,240 --> 00:32:45,730
აქ, მე ვრთავ ჩემი root node.

424
00:32:45,730 --> 00:32:48,900
როგორც იგი დგას ახლავე, მაქვს კურსორი რომ მითითებული null,

425
00:32:48,900 --> 00:32:52,970
ამიტომ მიუთითებს არაფერი.

426
00:32:52,970 --> 00:32:57,480
იმისათვის, რომ რეალურად შეიქმენით კვანძში,

427
00:32:57,480 --> 00:32:59,250
მე ჯერ უნდა გამოყოს მეხსიერება ამისთვის.

428
00:32:59,250 --> 00:33:05,910
მე ვაპირებ ამას მიერ მიღების მეხსიერების შესახებ ბევრი გამოყენებით malloc.

429
00:33:05,910 --> 00:33:10,660
მე ვაპირებ მითითებული root ტოლია შედეგად malloc,

430
00:33:10,660 --> 00:33:19,550
და მე ვაპირებ გამოვიყენო sizeof ოპერატორის გამოთვლა ზომის კვანძი.

431
00:33:19,550 --> 00:33:24,990
მიზეზი იმისა, რომ გამოვიყენო sizeof კვანძის ნაცვლად, ვთქვათ,

432
00:33:24,990 --> 00:33:37,020
აკეთებს რაღაც მსგავსი - malloc (4 + 4 +4) ან malloc 12 -

433
00:33:37,020 --> 00:33:40,820
ეს იმიტომ მინდა ჩემი კოდი უნდა იყოს, როგორც თავსებადი შეიძლება.

434
00:33:40,820 --> 00:33:44,540
მინდა შეძლებს მიიღოს ამ. გ ფაილი, კომპილირება on ელექტრო მოწყობილობების,

435
00:33:44,540 --> 00:33:48,820
და შემდეგ კომპილირება ჩემს 64-bit Mac -

436
00:33:48,820 --> 00:33:52,040
ან სრულიად განსხვავებული არქიტექტურა -

437
00:33:52,040 --> 00:33:54,640
და მინდა ამ ყველა მუშაობას იმავე.

438
00:33:54,640 --> 00:33:59,510
>> თუ მე მიღების დაშვებების შესახებ ზომა ცვლადები -

439
00:33:59,510 --> 00:34:02,070
ზომა int ან ზომის მიმთითებელი -

440
00:34:02,070 --> 00:34:06,070
მაშინ მე ასევე მიღების დაშვებების შესახებ სახის არქიტექტურის

441
00:34:06,070 --> 00:34:10,440
რომელზედაც ჩემი კოდი წარმატებით შეგიძლიათ კომპილაციის როდესაც აწარმოებს.

442
00:34:10,440 --> 00:34:15,030
ყოველთვის გამოიყენეთ sizeof ნაცვლად ხელით შემაჯამებელი struct სფეროებში.

443
00:34:15,030 --> 00:34:20,500
სხვა მიზეზი არის ის, რომ იქ შესაძლოა padding რომ შემდგენელი აყენებს შევიდა struct.

444
00:34:20,500 --> 00:34:26,570
მაშინაც კი, მხოლოდ შემაჯამებელი ინდივიდუალური სფეროებში არ არის რაღაც, რომ თქვენ, როგორც წესი, გსურთ,

445
00:34:26,570 --> 00:34:30,340
ასე, რომ წაშალოთ ხაზი.

446
00:34:30,340 --> 00:34:33,090
ახლა ნამდვილად ინიციალიზაცია ამ ძირეული კვანძის,

447
00:34:33,090 --> 00:34:36,489
მე ვაპირებ უნდა შეაერთედ წელს ფასეულობების თითოეული მისი სხვადასხვა სფეროში.

448
00:34:36,489 --> 00:34:41,400
მაგალითად, ღირებულება ვიცი მინდა ინიციალიზაცია დან 7,

449
00:34:41,400 --> 00:34:46,920
და ახლა მე ვაპირებ მითითებული მარცხენა ბავშვი იყოს null

450
00:34:46,920 --> 00:34:55,820
და უფლება ბავშვს ასევე null. მშვენიერია

451
00:34:55,820 --> 00:35:02,670
ჩვენ გავაკეთეთ ის ნაწილი სპეც.

452
00:35:02,670 --> 00:35:07,390
>> სპეციფიკაცია ქვემოთ ბოლოში გვერდზე 3 მკითხავს, ​​რომ შევქმნათ კიდევ სამი კვანძების -

453
00:35:07,390 --> 00:35:10,600
ერთი შემცველი 3, ერთი შემცველი 6, და ერთი 9 -

454
00:35:10,600 --> 00:35:14,210
და შემდეგ WIRE მათ ასე გამოიყურება ზუსტად ისევე, ჩვენი ხე დიაგრამაზე

455
00:35:14,210 --> 00:35:17,120
რომ ჩვენ ვსაუბრობთ ადრე.

456
00:35:17,120 --> 00:35:20,450
მოდით, რომ საკმაოდ სწრაფად აქ.

457
00:35:20,450 --> 00:35:26,270
თქვენ ნახავთ მართლაც სწრაფად, რომ მე ვაპირებ წერა bunch of დუბლიკატი კოდი.

458
00:35:26,270 --> 00:35:32,100
მე ვაპირებ შექმნას კვანძის * და მე ვაპირებ მოვუწოდო მას სამი.

459
00:35:32,100 --> 00:35:36,000
მე ვაპირებ ვაყენებთ მას ტოლი malloc (sizeof (კვანძის)).

460
00:35:36,000 --> 00:35:41,070
მე ვაპირებ მითითებული სამი> ღირებულება = 3.

461
00:35:41,070 --> 00:35:54,780
სამი -> left_child = NULL; სამი -> მარჯვენა _child = NULL; ისევე.

462
00:35:54,780 --> 00:36:01,150
რომ გამოიყურება საკმაოდ მსგავსი ინიციალიზაციისას ფესვი, და სწორედ ის, რაც

463
00:36:01,150 --> 00:36:05,760
მე ვაპირებ უნდა გავაკეთოთ, თუ დავიწყო ინიციალიზაციისას 6 და 9 ისევე.

464
00:36:05,760 --> 00:36:20,720
მე გავაკეთებ, რომ ნამდვილად სწრაფად აქ - ფაქტობრივად, მე ვაპირებ პატარა ასლი და პასტა,

465
00:36:20,720 --> 00:36:46,140
და დარწმუნდით, რომ მე - კარგად.

466
00:36:46,470 --> 00:37:09,900
 ახლა მაქვს ეს გადაწერა და შემიძლია წავიდეთ წინ და დაადგინა ამ ტოლია 6.

467
00:37:09,900 --> 00:37:14,670
თქვენ ხედავთ, რომ ამ იღებს awhile და არ არის სუპერ ეფექტური.

468
00:37:14,670 --> 00:37:22,610
რაღაც ცოტა, ჩვენ წერენ ფუნქცია რომ ამას ჩვენთვის.

469
00:37:22,610 --> 00:37:32,890
მინდა ჩანაცვლება ამ 9, შეცვლის, რომ 6.

470
00:37:32,890 --> 00:37:37,360
>> ახლა ჩვენ მივიღეთ ყველა ჩვენი კვანძების შექმნა და ინიციალიზაცია.

471
00:37:37,360 --> 00:37:41,200
გვაქვს ჩვენი ძირეული მითითებული ტოლია 7, ან შეიცავს ღირებულება 7,

472
00:37:41,200 --> 00:37:46,510
ჩვენი კვანძის შემცველი 3, ჩვენი კვანძის შემცველი 6, და ჩვენი კვანძის შემცველი 9.

473
00:37:46,510 --> 00:37:50,390
ამ ეტაპზე, ყველა ჩვენ უნდა გავაკეთოთ არის მავთულის ყველაფერი up.

474
00:37:50,390 --> 00:37:53,020
მიზეზი მე ინიციალიზაცია ყველა მითითებას null მხოლოდ ისე, რომ მე დარწმუნდით, რომ

475
00:37:53,020 --> 00:37:56,260
მე არ მაქვს რაიმე uninitialized პოინტერები იქ შემთხვევით.

476
00:37:56,260 --> 00:38:02,290
და ასევე წლიდან, ამ ეტაპზე, მე მხოლოდ უნდა რეალურად დააკავშირებს კვანძების ერთმანეთს -

477
00:38:02,290 --> 00:38:04,750
to პირობა, რომ ისინი რეალურად უკავშირდება - მე არ უნდა გაიაროს და მიიღოს

478
00:38:04,750 --> 00:38:08,240
დარწმუნებული ვარ, რომ ყველა nulls არიან იქ სათანადო ადგილებში.

479
00:38:08,240 --> 00:38:15,630
>> დასაწყისი ფესვი, მე ვიცი, რომ root მარცხენა ბავშვი არის 3.

480
00:38:15,630 --> 00:38:21,250
მე ვიცი, რომ ძირეული უფლება ბავშვი 9.

481
00:38:21,250 --> 00:38:24,880
ამის შემდეგ, მხოლოდ სხვა ბავშვს რომ მე არ დაუტოვებიათ ფიქრი

482
00:38:24,880 --> 00:38:39,080
არის 3 უფლება ბავშვს, რომელიც არის 6.

483
00:38:39,080 --> 00:38:44,670
ამ ეტაპზე, ეს ყველაფერი გამოიყურება საკმაოდ კარგი.

484
00:38:44,670 --> 00:38:54,210
ჩვენ წაშალოთ ზოგიერთი ხაზები.

485
00:38:54,210 --> 00:38:59,540
ახლა ყველაფერი გამოიყურება საკმაოდ კარგი.

486
00:38:59,540 --> 00:39:04,240
მოდით დავუბრუნდეთ ჩვენი სპეციფიკაცია და რა უნდა გავაკეთოთ შემდეგი.

487
00:39:04,240 --> 00:39:07,610
>> ამ ეტაპზე, ჩვენ უნდა დავწეროთ ფუნქცია ე.წ. "შეიცავს"

488
00:39:07,610 --> 00:39:14,150
ერთად პროტოტიპი 'bool შეიცავს (int value).

489
00:39:14,150 --> 00:39:17,060
და ამ შეიცავს ფუნქციის დაბრუნებას აპირებს ჭეშმარიტი

490
00:39:17,060 --> 00:39:21,200
 თუ ხე მიუთითა ჩვენი გლობალური root ცვლადი

491
00:39:21,200 --> 00:39:26,950
 შეიცავს ღირებულება შევიდა ფუნქცია და ცრუ სხვაგვარად.

492
00:39:26,950 --> 00:39:29,000
მოდით წავიდეთ წინ და გაგვაჩნია.

493
00:39:29,000 --> 00:39:35,380
ეს იქნება ზუსტად ისევე lookup, რომ ჩვენ მიერ ხელით iPad უბრალოდ ცოტა წინ.

494
00:39:35,380 --> 00:39:40,130
მოდით zoom უკან ცოტა და გადახვევა up.

495
00:39:40,130 --> 00:39:43,130
ჩვენ ვაპირებთ დააყენა ამ ფუნქციის უფლება ზემოთ ჩვენი მთავარი ფუნქცია

496
00:39:43,130 --> 00:39:48,990
ისე, რომ ჩვენ არ გვაქვს რაიმე სახის prototyping.

497
00:39:48,990 --> 00:39:55,960
ასე რომ, bool შეიცავს (int value).

498
00:39:55,960 --> 00:40:00,330
იქ ჩვენ წავიდეთ. იქ ჩვენი boilerplate დეკლარაციას.

499
00:40:00,330 --> 00:40:02,900
უბრალოდ დარწმუნდით, რომ ეს ხელს კომპილაციის,

500
00:40:02,900 --> 00:40:06,820
მე ვაპირებ წავიდეთ წინ და უბრალოდ დააყენეთ თანაბარი დაბრუნების ცრუ.

501
00:40:06,820 --> 00:40:09,980
ახლავე ამ ფუნქციის მხოლოდ ხელს არაფერი და ყოველთვის აცხადებს, რომ

502
00:40:09,980 --> 00:40:14,010
ღირებულება, რომ ჩვენ ვეძებთ არ არის ხე.

503
00:40:14,010 --> 00:40:16,280
>> ამ ეტაპზე, ეს ალბათ კარგი იდეა -

504
00:40:16,280 --> 00:40:19,600
მას შემდეგ, რაც ჩვენ წერილობით მთელი bunch of კოდი და ჩვენ კი არ სცადა ტესტირების ამაზე -

505
00:40:19,600 --> 00:40:22,590
რომ დავრწმუნდეთ, რომ ყველა ადგენს.

506
00:40:22,590 --> 00:40:27,460
არსებობს რამდენიმე რამ, რომ ჩვენ უნდა გავაკეთოთ, რათა დავრწმუნდეთ, რომ ეს ხელს რეალურად ადგენენ.

507
00:40:27,460 --> 00:40:33,530
პირველი, თუ ჩვენ გამოყენებით ნებისმიერი ფუნქციების ნებისმიერ ბიბლიოთეკების, რომ ჩვენ ჯერ არ შედის.

508
00:40:33,530 --> 00:40:37,940
ფუნქციების ჩვენ გამოიყენება იმდენად, რამდენადაც არიან malloc,

509
00:40:37,940 --> 00:40:43,310
და მაშინ ჩვენ ასევე იყენებს ამ ტიპის - ამ არასტანდარტული ტიპი სახელწოდებით "bool' -

510
00:40:43,310 --> 00:40:45,750
რაც შედის სტანდარტულ bool header ფაილი.

511
00:40:45,750 --> 00:40:53,250
ჩვენ ნამდვილად გვინდა მოიცავს სტანდარტული bool.h ამისთვის bool ტიპის,

512
00:40:53,250 --> 00:40:59,230
და ჩვენ ასევე გვინდა # მოიცავს სტანდარტული lib.h სტანდარტული ბიბლიოთეკები

513
00:40:59,230 --> 00:41:03,530
რომელიც მოიცავს malloc და თავისუფალი, და ყველა რომ.

514
00:41:03,530 --> 00:41:08,660
ასე რომ, zoom out, ჩვენ ვაპირებთ დატოვა.

515
00:41:08,660 --> 00:41:14,190
მოდით ვეცადოთ და დარწმუნდით, რომ ეს რეალურად გააკეთა კომპილირების.

516
00:41:14,190 --> 00:41:18,150
ჩვენ ვხედავთ, რომ ეს ასეა, ასე ჩვენ სწორ გზაზე.

517
00:41:18,150 --> 00:41:22,990
>> მოდით გახსენით binary_tree.c ერთხელ.

518
00:41:22,990 --> 00:41:34,530
იგი ადგენს. მოდით დაცემას და დარწმუნდით, რომ ჩვენ ჩადეთ სერიოზული მოწოდებები ჩვენი შეიცავს ფუნქცია -

519
00:41:34,530 --> 00:41:40,130
უბრალოდ, დარწმუნდით, რომ ეს ყველაფერი კარგად და კარგი.

520
00:41:40,130 --> 00:41:43,170
მაგალითად, როდესაც ჩვენ გავაკეთეთ რამდენიმე lookups ჩვენს ხე ადრე,

521
00:41:43,170 --> 00:41:48,500
ჩვენ შევეცადეთ ეძებოთ ღირებულებების 6, 10 და 1, და ვიცოდით, რომ 6 იყო ხე,

522
00:41:48,500 --> 00:41:52,220
10 არ იყო ხე, და 1 არ იყო ხის ან.

523
00:41:52,220 --> 00:41:57,230
მოდით გამოვიყენოთ იმ ნიმუშის მოუწოდებს როგორც გზა გაერკვნენ თუ არა

524
00:41:57,230 --> 00:41:59,880
ჩვენი შეიცავს ფუნქცია მუშაობს.

525
00:41:59,880 --> 00:42:05,210
იმისათვის, რომ გავაკეთოთ, მე ვაპირებ გამოიყენოთ printf ფუნქცია,

526
00:42:05,210 --> 00:42:10,280
და ჩვენ ვაპირებთ ამობეჭდოთ შედეგი ზარი შეიცავს.

527
00:42:10,280 --> 00:42:13,280
მე ვაპირებ მა სტრიქონი "შეიცავს (% d) = რადგან

528
00:42:13,280 --> 00:42:20,470
 ჩვენ ვაპირებთ plug in ღირებულება, რომ ჩვენ ვაპირებთ ვეძებოთ,

529
00:42:20,470 --> 00:42:27,130
და =% s \ n "და გამოიყენოს, რომ როგორც ჩვენი სტრიქონში.

530
00:42:27,130 --> 00:42:30,720
ჩვენ უბრალოდ აპირებს ვხედავ - სიტყვასიტყვით ამობეჭდოთ ეკრანზე -

531
00:42:30,720 --> 00:42:32,060
რა ჰგავს ფუნქცია ზარი.

532
00:42:32,060 --> 00:42:33,580
ეს არ არის რეალურად ფუნქცია ზარი.

533
00:42:33,580 --> 00:42:36,760
 ეს არის მხოლოდ string განკუთვნილია ჰგავს ფუნქცია ზარი.

534
00:42:36,760 --> 00:42:41,140
>> ახლა ჩვენ ვაპირებთ შეაერთედ წელს ღირებულებებს.

535
00:42:41,140 --> 00:42:43,580
ჩვენ ვაპირებთ შევეცადოთ შეიცავს წლის 6,

536
00:42:43,580 --> 00:42:48,340
და მერე რა ჩვენ ვაპირებთ აქ არის გამოიყენოს რომ ternary ოპერატორს.

537
00:42:48,340 --> 00:42:56,340
ვნახოთ - შეიცავს 6 - ასე, ახლა მე შეიცავდა 6 და თუ შეიცავს 6 მართალია,

538
00:42:56,340 --> 00:43:01,850
სიმებიანი რომ ჩვენ ვაპირებთ გააგზავნეთ% s ფორმატი ხასიათი

539
00:43:01,850 --> 00:43:04,850
იქნება სტრიქონი "ჭეშმარიტი".

540
00:43:04,850 --> 00:43:07,690
მოდით გადახვევა მეტი ცოტა.

541
00:43:07,690 --> 00:43:16,210
წინააღმდეგ შემთხვევაში, ჩვენ გვინდა გაგზავნას სტრიქონი "ცრუ" თუ შეიცავს 6 ანაზღაურება ყალბი.

542
00:43:16,210 --> 00:43:19,730
ეს არის პატარა Goofy ორიენტირებული, მაგრამ მე გაერკვნენ შეიძლება ასევე ილუსტრაციას

543
00:43:19,730 --> 00:43:23,780
რა ternary ოპერატორი ჰგავს რადგან ჩვენ არ გვინახავს მისი awhile.

544
00:43:23,780 --> 00:43:27,670
ეს იქნება ლამაზი, მოსახერხებელი გზა გაერკვნენ, თუ ჩვენი შეიცავს ფუნქცია მუშაობს.

545
00:43:27,670 --> 00:43:30,040
მე ვაპირებ გადახვევა უკან მეტი მარცხნივ,

546
00:43:30,040 --> 00:43:39,900
და მე ვაპირებ და ჩასვით ეს ხაზი რამდენჯერმე.

547
00:43:39,900 --> 00:43:44,910
იგი შეიცვალა ზოგიერთი ამ ფასეულობების გარშემო,

548
00:43:44,910 --> 00:43:59,380
ასე რომ, ეს იქნება 1 და ეს იქნება 10.

549
00:43:59,380 --> 00:44:02,480
>> ამ ეტაპზე გვაქვს ლამაზი შეიცავს ფუნქციას.

550
00:44:02,480 --> 00:44:06,080
გვაქვს გარკვეული ტესტები, და ვნახავთ, თუ ეს სამუშაოები.

551
00:44:06,080 --> 00:44:08,120
ამ ეტაპზე ჩვენ წერილობითი კიდევ რამდენიმე კოდი.

552
00:44:08,120 --> 00:44:13,160
ახლა დაეტოვებინა გარეთ და დარწმუნდით, რომ ყველაფერი ჯერ კიდევ ადგენს.

553
00:44:13,160 --> 00:44:20,360
Quit გარეთ, და ახლა მოდით შევეცადოთ მიღების ორობითი ხე ერთხელ.

554
00:44:20,360 --> 00:44:22,260
ასევე, ის ჰგავს გვაქვს შეცდომა,

555
00:44:22,260 --> 00:44:26,930
და ჩვენ მივიღეთ ეს ცალსახად ვაცხადებთ ბიბლიოთეკის ფუნქცია printf.

556
00:44:26,930 --> 00:44:39,350
როგორც ჩანს, ჩვენ უნდა წავიდეს და # მოიცავს standardio.h.

557
00:44:39,350 --> 00:44:45,350
და ამ ყველაფერს უნდა შეადგინოს. ჩვენ ყველა კარგი.

558
00:44:45,350 --> 00:44:50,420
ახლა მოდით შევეცადოთ გაშვებული ორობითი ხე და ვნახოთ, რა მოხდება.

559
00:44:50,420 --> 00:44:53,520
აქ ვართ,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
და ჩვენ ვხედავთ, რომ, როგორც ველოდით -

561
00:44:55,190 --> 00:44:56,910
იმიტომ, რომ ჩვენ არ განხორციელდა შეიცავს გაუკეთებია,

562
00:44:56,910 --> 00:44:59,800
უფრო სწორად, ჩვენ უბრალოდ დასვა დაბრუნების ცრუ -

563
00:44:59,800 --> 00:45:03,300
ჩვენ ვხედავთ, რომ ეს მხოლოდ დაბრუნების ცრუ ყველა მათგანი,

564
00:45:03,300 --> 00:45:06,180
ასე რომ ყველა მუშაობს დიდი ნაწილი საკმაოდ კარგად.

565
00:45:06,180 --> 00:45:11,860
>> მოდით დავუბრუნდეთ და რეალურად განახორციელებს შეიცავს ამ ეტაპზე.

566
00:45:11,860 --> 00:45:17,490
მე ვაპირებ გადახვევა down, მიუახლოვდით, და -

567
00:45:17,490 --> 00:45:22,330
გახსოვდეთ, ალგორითმი, რომ ჩვენ გამოყენებული იყო, რომ ჩვენ დაიწყო ძირეული კვანძის

568
00:45:22,330 --> 00:45:28,010
და შემდეგ ყოველ კვანძში, რომ ჩვენ ვაწყდებით, ჩვენ შედარებით,

569
00:45:28,010 --> 00:45:32,380
და ეფუძნება, რომ შედარებით ჩვენ არც გადავა მარცხენა ბავშვის ან მარჯვნივ შვილი.

570
00:45:32,380 --> 00:45:39,670
ეს აპირებს გამოიყურებოდეს ძალიან ჰგავს ორობითი ძებნა კოდი, რომ ჩვენ წერდა ადრე ვადით.

571
00:45:39,670 --> 00:45:47,810
როდესაც ჩვენ ვიწყებთ off, ჩვენ ვიცით, რომ ჩვენ გვინდა გაიმართება მიმდინარე კვანძის

572
00:45:47,810 --> 00:45:54,050
რომ ჩვენ შევხედავთ, და მიმდინარე კვანძის აპირებს ინიციალიზდება to root node.

573
00:45:54,050 --> 00:45:56,260
და ახლა, ჩვენ ვაპირებთ შენარჩუნება გადის ხე,

574
00:45:56,260 --> 00:45:58,140
და გვახსოვდეს, რომ ჩვენი შეჩერების პირობით -

575
00:45:58,140 --> 00:46:01,870
 როდესაც ჩვენ რეალურად მუშაობდა მეშვეობით მაგალითად ხელით -

576
00:46:01,870 --> 00:46:03,960
იმ დროს, როცა ჩვენ შეექმნა null კვანძში,

577
00:46:03,960 --> 00:46:05,480
არა მაშინ, როცა ჩვენ შევხედეთ null ბავშვი,

578
00:46:05,480 --> 00:46:09,620
არამედ, როდესაც ჩვენ რეალურად გადავიდა node in ხე

579
00:46:09,620 --> 00:46:12,640
და აღმოჩნდა, რომ ჩვენ დროს null კვანძში.

580
00:46:12,640 --> 00:46:20,720
ჩვენ ვაპირებთ iterate სანამ მიმდ. არ არის ტოლი null.

581
00:46:20,720 --> 00:46:22,920
და რა ჩვენ ვაპირებთ?

582
00:46:22,920 --> 00:46:31,610
ჩვენ ვაპირებთ შევამოწმოთ, თუ (მიმდ. -> ღირებულების == ღირებულების),

583
00:46:31,610 --> 00:46:35,160
მაშინ ჩვენ ვიცით, რომ ჩვენ რეალურად ნაპოვნია კვანძში, რომ ჩვენ ვეძებთ.

584
00:46:35,160 --> 00:46:40,450
ასე რომ, ჩვენ შეიძლება დაბრუნდეს ჭეშმარიტი.

585
00:46:40,450 --> 00:46:49,830
წინააღმდეგ შემთხვევაში, ჩვენ გვინდა თუ არა მნიშვნელობა ნაკლებია ღირებულება.

586
00:46:49,830 --> 00:46:53,850
თუ მიმდინარე კვანძის ს მნიშვნელობა ნაკლებია ღირებულების ჩვენ ვეძებთ,

587
00:46:53,850 --> 00:46:57,280
ჩვენ ვაპირებთ გადასვლის უფლება.

588
00:46:57,280 --> 00:47:10,600
ასე რომ, მიმდ. = მიმდ. -> right_child და სხვაგვარად, ჩვენ ვაპირებთ გადაინაცვლებს მარცხენა.

589
00:47:10,600 --> 00:47:17,480
მიმდ. = მიმდ. -> left_child;. Pretty მარტივი.

590
00:47:17,480 --> 00:47:22,830
>> ალბათ აღიარებს loop, რომელიც გამოიყურება ძალიან გავს ამ საწყისი

591
00:47:22,830 --> 00:47:27,580
ორობითი ძებნა ადრე ვადა, გარდა მაშინ საქმე გვქონდა დაბალი, საშუალო და მაღალი.

592
00:47:27,580 --> 00:47:30,000
აქ, ჩვენ უბრალოდ უნდა შევხედოთ მიმდინარე ღირებულება,

593
00:47:30,000 --> 00:47:31,930
ამიტომ ლამაზი და მარტივი.

594
00:47:31,930 --> 00:47:34,960
მოდით დარწმუნდით ეს კოდი მუშაობს.

595
00:47:34,960 --> 00:47:42,780
პირველი, დარწმუნდით, რომ იგი ადგენს. როგორც ჩანს, ის ჯერ.

596
00:47:42,780 --> 00:47:47,920
მოდით ვეცადოთ გაშვებული იგი.

597
00:47:47,920 --> 00:47:50,160
მართლაც, იგი ბეჭდავს out ყველაფერი, რაც ჩვენ გვგონია.

598
00:47:50,160 --> 00:47:54,320
იგი აღმოაჩენს 6 წლის ხე, არ იპოვოს 10 რადგან 10 არ in ხე,

599
00:47:54,320 --> 00:47:57,740
და არ იპოვოს 1 ან იმიტომ 1 ისიც არ ხე.

600
00:47:57,740 --> 00:48:01,420
მაგარი რამეები.

601
00:48:01,420 --> 00:48:04,470
>> კარგად. მოდით დავუბრუნდეთ ჩვენი სპეციფიკაცია და ხედავთ რა მომავალი.

602
00:48:04,470 --> 00:48:07,990
ახლა მას სურს დაამატოთ კიდევ რამდენიმე კვანძების ჩვენი ხე.

603
00:48:07,990 --> 00:48:11,690
მას სურს დაამატოთ 5, 2 და 8, და დარწმუნდით, რომ ჩვენი შეიცავს კოდი

604
00:48:11,690 --> 00:48:13,570
დღემდე მუშაობს როგორც მოსალოდნელია.

605
00:48:13,570 --> 00:48:14,900
მოდით წავიდეთ გავაკეთოთ, რომ.

606
00:48:14,900 --> 00:48:19,430
ამ ეტაპზე, ვიდრე აკეთებს, რომ შემაშფოთებელი და ჩასვით ისევ,

607
00:48:19,430 --> 00:48:23,770
მოდით დავწეროთ ფუნქცია რეალურად შექმნა კვანძში.

608
00:48:23,770 --> 00:48:27,740
თუ ჩვენ გადახვევა ქვემოთ ყველა გზა ძირითადი, ჩვენ ვხედავთ, რომ ჩვენ ამით

609
00:48:27,740 --> 00:48:31,210
ძალიან ჰგავს კოდი უსასრულოდ ყოველ ჯერზე, რომ ჩვენ გვინდა შევქმნათ კვანძში.

610
00:48:31,210 --> 00:48:39,540
>> მოდით დავწეროთ ფუნქცია, რომელიც რეალურად ააშენოს კვანძის ჩვენთვის და დაგვიბრუნოთ ის.

611
00:48:39,540 --> 00:48:41,960
მე ვაპირებ მოვუწოდო მას build_node.

612
00:48:41,960 --> 00:48:45,130
მე ვაპირებ აშენებას კვანძის განსაკუთრებული მნიშვნელობა.

613
00:48:45,130 --> 00:48:51,040
მიუახლოვდით აქ.

614
00:48:51,040 --> 00:48:56,600
პირველი, რაც მე ვაპირებ ამის გაკეთებას რეალურად შექმნას ფართი კვანძის შესახებ ბევრი.

615
00:48:56,600 --> 00:49:05,400
ასე რომ, node * N = malloc (sizeof (კვანძის)); N -> ღირებულება = value;

616
00:49:05,400 --> 00:49:14,960
და შემდეგ აქ, მე უბრალოდ აპირებს ინიციალიზაცია ყველა ველი უნდა იყოს შესაბამის მნიშვნელობებზე.

617
00:49:14,960 --> 00:49:22,500
და ბოლომდე, ჩვენ დავიბრუნოთ ჩვენი კვანძში.

618
00:49:22,500 --> 00:49:28,690
კარგად. ერთი რამ აღვნიშნო, რომ ამ ფუნქციის უფლება აქ

619
00:49:28,690 --> 00:49:34,320
დაბრუნებას აპირებს მომცეთ მეხსიერება, რომ უკვე ბევრი-გამოყოფილი.

620
00:49:34,320 --> 00:49:38,880
რა არის ლამაზი შესახებ არის ის, რომ ამ კვანძის ახლა -

621
00:49:38,880 --> 00:49:42,420
ჩვენ უნდა გამოაცხადოს ის შესახებ ბევრი, რადგან თუ ჩვენ გამოაცხადა on დასტის

622
00:49:42,420 --> 00:49:45,050
ჩვენ ვერ შეძლებს ამის გაკეთებას ამ ფუნქციის მოსწონს ეს.

623
00:49:45,050 --> 00:49:47,690
რომ მეხსიერების წავიდოდა გარეთ ფარგლებს

624
00:49:47,690 --> 00:49:51,590
და იქნება ბათილად, თუ ჩვენ შევეცადეთ ვებგვერდზე მოგვიანებით.

625
00:49:51,590 --> 00:49:53,500
მას შემდეგ, რაც ჩვენ ვაცხადებთ ბევრი-გამოყოფილი მეხსიერება,

626
00:49:53,500 --> 00:49:55,830
ჩვენ ვაპირებთ უნდა იზრუნოს გამონთავისუფლების იგი მოგვიანებით

627
00:49:55,830 --> 00:49:58,530
ჩვენი პროგრამის არ გაჟონვა ნებისმიერი მეხსიერება.

628
00:49:58,530 --> 00:50:01,270
ჩვენ ბევრი punting რომ ყველაფერს სხვაგან კოდი

629
00:50:01,270 --> 00:50:02,880
უბრალოდ სიმარტივის გულისთვის დროს,

630
00:50:02,880 --> 00:50:05,610
მაგრამ თუ ოდესმე წერენ ფუნქცია რომ ასე გამოიყურება

631
00:50:05,610 --> 00:50:10,370
სადაც თქვენ მოხვდით - ზოგიერთი ეძახით malloc ან realloc შიგნით -

632
00:50:10,370 --> 00:50:14,330
თქვენ გვინდა დავრწმუნდეთ, რომ თქვენ დააყენა გარკვეული კომენტარი აქ რომ ამბობს,

633
00:50:14,330 --> 00:50:29,970
Hey, თქვენ იცით, დააბრუნებს ბევრი-გამოყოფილი კვანძის ინიციალიზაცია ერთად გაიარა-ღირებულების.

634
00:50:29,970 --> 00:50:33,600
და მაშინ გვინდა დავრწმუნდეთ, რომ თქვენ დააყენა გარკვეული გაითვალისწინოთ, რომ ამბობს

635
00:50:33,600 --> 00:50:41,720
Caller უნდა გასათავისუფლებლად დაბრუნდა მეხსიერება.

636
00:50:41,720 --> 00:50:45,450
რომ გზა, თუ ვინმეს ოდესმე მიდის და იყენებს, რომ ფუნქცია,

637
00:50:45,450 --> 00:50:48,150
მათ იციან, რომ რაც ისინი უკან რომ ფუნქცია

638
00:50:48,150 --> 00:50:50,870
რაღაც მომენტში უნდა გათავისუფლდებიან.

639
00:50:50,870 --> 00:50:53,940
>> ვთქვათ, რომ ყველა კარგად და კარგი აქ,

640
00:50:53,940 --> 00:51:02,300
ჩვენ შეგვიძლია წავიდეთ ქვემოთ შევიდა ჩვენი კოდი და შეცვლის ყველა ამ ხაზების უფლება აქ

641
00:51:02,300 --> 00:51:05,410
ერთად მოუწოდებს ჩვენს Build კვანძის ფუნქციას.

642
00:51:05,410 --> 00:51:08,170
მოდით, რომ მართლაც სწრაფად.

643
00:51:08,170 --> 00:51:15,840
ერთი ნაწილი, რომ ჩვენ არ ვაპირებთ, შევცვალოთ ეს ნაწილი ქვევით აქ

644
00:51:15,840 --> 00:51:18,520
ბოლოში, სადაც ჩვენ რეალურად WIRE up კვანძების აღვნიშნო ერთმანეთს,

645
00:51:18,520 --> 00:51:21,030
იმიტომ, რომ ჩვენ არ შეგვიძლია გავაკეთოთ ჩვენი ფუნქცია.

646
00:51:21,030 --> 00:51:37,400
მაგრამ, მოდით root = build_node (7); კვანძის * სამი = build_node (3);

647
00:51:37,400 --> 00:51:47,980
კვანძის * ექვსი = build_node (6); კვანძის * ცხრა = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
და ახლა, ჩვენც გვინდა დაამატოთ კვანძების ამისთვის -

649
00:51:52,590 --> 00:52:03,530
კვანძის * ხუთი = build_node (5); კვანძის * რვა = build_node (8);

650
00:52:03,530 --> 00:52:09,760
და რა იყო სხვა კვანძის? ვნახოთ აქ. გვინდოდა აგრეთვე დაამატოთ 2 -

651
00:52:09,760 --> 00:52:20,280
კვანძის * ორი = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
კარგად. ამ ეტაპზე, ჩვენ ვიცით, რომ გვაქვს 7, 3, 9, და 6

653
00:52:26,850 --> 00:52:30,320
ყველა სახაზო up სათანადოდ, მაგრამ რაც შეეხება 5, 8 და 2?

654
00:52:30,320 --> 00:52:33,550
შენარჩუნება ყველაფერი შესაბამისი ბრძანებით,

655
00:52:33,550 --> 00:52:39,230
ჩვენ ვიცით, რომ სამი უფლება ბავშვი 6.

656
00:52:39,230 --> 00:52:40,890
ასე რომ, თუ ჩვენ ვაპირებთ დაამატოთ 5,

657
00:52:40,890 --> 00:52:46,670
5 ასევე ეკუთვნის in მარჯვენა მხარეს ხე რომელიც 3 არის root,

658
00:52:46,670 --> 00:52:50,440
ასე 5 ეკუთვნის როგორც მარცხენა ბავშვი 6.

659
00:52:50,440 --> 00:52:58,650
ჩვენ შეგვიძლია ამის გაკეთება იმით, ექვსი -> left_child = ხუთი;

660
00:52:58,650 --> 00:53:10,790
და შემდეგ 8 ეკუთვნის როგორც მარცხენა ბავშვი 9, ასე ცხრა -> left_child = რვა;

661
00:53:10,790 --> 00:53:22,190
და შემდეგ 2 არის მარცხენა ბავშვი 3, ასე რომ ჩვენ შეგვიძლია გავაკეთოთ, რომ აქ - შენ -> left_child = ორი;.

662
00:53:22,190 --> 00:53:27,730
თუ თქვენ არ საკმაოდ დაიცვას ერთად რომ, მე გთავაზობთ დავხატოთ ის თავს.

663
00:53:27,730 --> 00:53:35,660
>> კარგად. გადავარჩინოთ ეს. მოდით გასვლა და დარწმუნდით, რომ იგი ადგენს,

664
00:53:35,660 --> 00:53:40,760
და მაშინ ჩვენ შეგიძლიათ დაამატოთ ჩვენი არსებული მოწოდებით.

665
00:53:40,760 --> 00:53:44,120
როგორც ჩანს, ყველაფერი მაინც ადგენს.

666
00:53:44,120 --> 00:53:51,790
მოდით წავიდეთ და დაამატოთ ზოგიერთი შეიცავს მოუწოდებს.

667
00:53:51,790 --> 00:53:59,640
ისევ, მე აპირებს ცოტა ასლი და პასტა.

668
00:53:59,640 --> 00:54:15,860
ახლა მოვძებნოთ 5, 8, და 2. კარგად.

669
00:54:15,860 --> 00:54:28,330
მოდით დავრწმუნდეთ, რომ ამ ყველა გამოიყურება კარგი მაინც. მშვენიერია შენახვა და გასვლა.

670
00:54:28,330 --> 00:54:33,220
ახლა გადავდგათ, კომპილირდება და ახლა მოდით აწარმოებს.

671
00:54:33,220 --> 00:54:37,540
მდებარეობა შედეგების, როგორც ჩანს ყველაფერი მუშაობს უბრალოდ ლამაზი და კარგად.

672
00:54:37,540 --> 00:54:41,780
მშვენიერია ახლა გვაქვს ჩვენი შეიცავს ფუნქციას წერილობითი.

673
00:54:41,780 --> 00:54:46,160
მოდით გადაადგილება და დაიწყოს მუშაობა როგორ ჩადეთ კვანძების შევიდა ხე

674
00:54:46,160 --> 00:54:50,000
რადგან, როგორც ვაკეთებთ ეს ახლავე, რამ არ არის ძალიან ლამაზი.

675
00:54:50,000 --> 00:54:52,280
>> თუ ჩვენ დავუბრუნდებით სპეციფიკაცია,

676
00:54:52,280 --> 00:55:00,540
იგი გვთხოვს დაწერა ფუნქციის მოუწოდა ჩადეთ - ერთხელ, დაბრუნების bool

677
00:55:00,540 --> 00:55:04,400
ამისთვის თუ არა ჩვენ შეგვიძლია რეალურად ჩადეთ კვანძის შევიდა ხე -

678
00:55:04,400 --> 00:55:07,710
და მაშინ ღირებულება ჩასასმელად შევიდა ხე არის მითითებული, როგორც

679
00:55:07,710 --> 00:55:11,060
ერთადერთი არგუმენტი ჩვენი ჩანართით ფუნქცია.

680
00:55:11,060 --> 00:55:18,180
ჩვენ TRUE თუ ჩვენ შევძელით მართლაც ჩადეთ კვანძის შემცველი ღირებულება შევიდა ხე,

681
00:55:18,180 --> 00:55:20,930
რაც იმას ნიშნავს, რომ ჩვენ, ერთი, ჰქონდა საკმარისი მეხსიერება,

682
00:55:20,930 --> 00:55:24,840
და შემდეგ ორი, რომ კვანძის არ უკვე არსებობს ხე წლიდან -

683
00:55:24,840 --> 00:55:32,170
გახსოვდეთ, ჩვენ არ ვაპირებთ, რომ გვქონდეს დუბლიკატი ღირებულებების ხე, უბრალოდ, რათა რამ მარტივი.

684
00:55:32,170 --> 00:55:35,590
კარგად. თავში კოდი.

685
00:55:35,590 --> 00:55:44,240
გახსენით ეს. მიუახლოვდით bit, მაშინ გადახვევა down.

686
00:55:44,240 --> 00:55:47,220
მოდით დააყენა ჩასმა ფუნქციის უფლება ზემოთ შეიცავს.

687
00:55:47,220 --> 00:55:56,360
ისევ და ისევ, ეს იქნება მოუწოდა bool ჩანართით (int value).

688
00:55:56,360 --> 00:56:01,840
Give it ცოტა მეტი სივრცე და შემდეგ, როგორც ჩვეულებრივ,

689
00:56:01,840 --> 00:56:08,870
მოდით დააყენა სანაცვლოდ ყალბი დროს ბოლომდე.

690
00:56:08,870 --> 00:56:22,620
ახლა ქვემოთ ბოლოში, მოდით წავიდეთ წინ და ნაცვლად ხელით ვაშენებთ კვანძების

691
00:56:22,620 --> 00:56:27,900
მთავარ თავი და გაყვანილობა მათ მდე აღვნიშნო, რომ ერთმანეთი ისე ვაკეთებთ,

692
00:56:27,900 --> 00:56:30,600
ჩვენ დაეყრდნოს ჩვენი ჩანართით ფუნქცია გაგვაჩნია.

693
00:56:30,600 --> 00:56:35,510
ჩვენ არ დაეყრდნონ ჩვენი ჩანართით ფუნქცია აშენება მთელი ხე ნულიდან უბრალოდ არ არის,

694
00:56:35,510 --> 00:56:39,970
არამედ ჩვენ დავაღწიოთ ამ ხაზები - we'll კომენტარის აღნიშნული ხაზები -

695
00:56:39,970 --> 00:56:43,430
რომ ავაშენოთ კვანძების 5, 8, და 2.

696
00:56:43,430 --> 00:56:55,740
და ამის ნაცვლად, ჩვენ ჩადეთ მოუწოდებს ჩვენს ჩანართით ფუნქცია

697
00:56:55,740 --> 00:57:01,280
რომ დავრწმუნდეთ, რომ რეალურად მუშაობს.

698
00:57:01,280 --> 00:57:05,840
Here We Go.

699
00:57:05,840 --> 00:57:09,300
>> ახლა ჩვენ გამოეხმაურა აღნიშნული ხაზები.

700
00:57:09,300 --> 00:57:13,700
ჩვენ მხოლოდ 7, 3, 9, და 6 ჩვენს ხე ამ ეტაპზე.

701
00:57:13,700 --> 00:57:18,870
რომ დავრწმუნდეთ, რომ ეს ყველაფერი სამუშაო,

702
00:57:18,870 --> 00:57:25,050
ჩვენ შეგვიძლია დააშორებს, რათა ჩვენი ორობითი ხე,

703
00:57:25,050 --> 00:57:30,750
გაუშვით და ვხედავთ, რომ შეიცავს არის გვეუბნებოდა, რომ ჩვენ მთლიანად უფლება -

704
00:57:30,750 --> 00:57:33,110
5, 8 და 2 არ არიან ხე.

705
00:57:33,110 --> 00:57:37,960
უკან დაბრუნება შევიდა კოდი,

706
00:57:37,960 --> 00:57:41,070
და როგორ მივდივართ ჩასასმელად?

707
00:57:41,070 --> 00:57:46,290
გახსოვთ რა გავაკეთეთ, როდესაც ჩვენ რეალურად ჩასმა 5, 8, და 2 ადრე.

708
00:57:46,290 --> 00:57:50,100
ჩვენ ითამაშა რომ Plinko თამაში, სადაც ჩვენ დაიწყო root,

709
00:57:50,100 --> 00:57:52,780
ჩამოიწია ხე ერთი ერთი

710
00:57:52,780 --> 00:57:54,980
სანამ ჩვენ აღმოვაჩინეთ შესაბამისი უფსკრული,

711
00:57:54,980 --> 00:57:57,570
და მაშინ ჩვენ სახაზო წელს კვანძის შესაბამის ადგილზე.

712
00:57:57,570 --> 00:57:59,480
ჩვენ ვაპირებთ გავაკეთოთ იგივე.

713
00:57:59,480 --> 00:58:04,070
ეს არის ძირითადად, როგორიცაა წერა კოდი, რომ ჩვენ გამოყენებული შეიცავს ფუნქცია

714
00:58:04,070 --> 00:58:05,910
მოძიების ადგილზე სადაც კვანძის უნდა იყოს,

715
00:58:05,910 --> 00:58:10,560
და მაშინ ჩვენ უბრალოდ აპირებს ჩადეთ კვანძის უფლება არსებობს.

716
00:58:10,560 --> 00:58:17,000
დავიწყოთ აკეთებს, რომ.

717
00:58:17,000 --> 00:58:24,200
>> ამიტომ კვანძის * მიმდ. = root; ჩვენ უბრალოდ აპირებს დაიცვას შეიცავს კოდი

718
00:58:24,200 --> 00:58:26,850
სანამ ჩვენ, რომ არ საკმაოდ ჩვენთვის მუშაობა.

719
00:58:26,850 --> 00:58:32,390
ჩვენ ვაპირებთ გავლა ხე ხოლო მიმდინარე ელემენტს არ null,

720
00:58:32,390 --> 00:58:45,280
და თუ ჩვენ ვხედავთ, რომ მიმდ. ღირებულების ტოლია ღირებულება, რომ ჩვენ ვცდილობთ ჩასასმელად -

721
00:58:45,280 --> 00:58:49,600
ასევე, ეს არის ერთ შემთხვევებში, რომელშიც ჩვენ ვერ რეალურად ჩადეთ კვანძში

722
00:58:49,600 --> 00:58:52,730
შევიდა ხე რადგან ეს იმას ნიშნავს, რომ ჩვენ გვაქვს დუბლიკატი ღირებულება.

723
00:58:52,730 --> 00:58:59,010
აქ ჩვენ რეალურად დაბრუნებას აპირებს ყალბი.

724
00:58:59,010 --> 00:59:08,440
ახლა, სხვას თუ მიმდ. ს მნიშვნელობა ნაკლებია ღირებულება,

725
00:59:08,440 --> 00:59:10,930
ახლა ჩვენ ვიცით, რომ ჩვენ გადავა უფლება

726
00:59:10,930 --> 00:59:17,190
 რადგან ღირებულების ეკუთვნის სწორი ნახევარში მიმდ. ხე.

727
00:59:17,190 --> 00:59:30,110
წინააღმდეგ შემთხვევაში, ჩვენ ვაპირებთ გადაინაცვლებს მარცხენა.

728
00:59:30,110 --> 00:59:37,980
სწორედ ძირითადად ჩვენი შეიცავს ფუნქციონირებას უფლება არსებობს.

729
00:59:37,980 --> 00:59:41,820
>> ამ ეტაპზე, ერთხელ ჩვენ დასრულდება ამ ხოლო მარყუჟის,

730
00:59:41,820 --> 00:59:47,350
ჩვენი მიმდ. მაჩვენებელი იქნება მიუთითებს null

731
00:59:47,350 --> 00:59:51,540
თუ ფუნქცია არ უკვე დაბრუნდა.

732
00:59:51,540 --> 00:59:58,710
ჩვენ ამიტომ მქონე მიმდ. ადგილზე, სადაც ჩვენ გვინდა, რომ ჩადეთ ახალი კვანძში.

733
00:59:58,710 --> 01:00:05,210
რა არის გასაკეთებელი არის რეალურად ააშენოს ახალი კვანძის,

734
01:00:05,210 --> 01:00:08,480
რაც ჩვენ შეგვიძლია გავაკეთოთ საკმაოდ მარტივად.

735
01:00:08,480 --> 01:00:14,930
ჩვენ შეგვიძლია გამოვიყენოთ ჩვენი სუპერ მოსახერხებელი Build კვანძის ფუნქციას,

736
01:00:14,930 --> 01:00:17,210
და ის, რასაც ჩვენ არ ადრე -

737
01:00:17,210 --> 01:00:21,400
ჩვენ უბრალოდ სახის აიღო თავისთავად მაგრამ ახლა ჩვენ ყველაფერს გავაკეთებთ, რათა დავრწმუნდეთ, -

738
01:00:21,400 --> 01:00:27,130
ჩვენ ვამოწმებთ დავრწმუნდეთ, რომ ღირებულება დაბრუნდა ახალი კვანძში იყო სინამდვილეში

739
01:00:27,130 --> 01:00:33,410
არ null, რადგან ჩვენ არ გვინდა, რომ დაიწყოს წვდომის რომ მეხსიერების თუ ეს null.

740
01:00:33,410 --> 01:00:39,910
ჩვენ შეგვიძლია შევამოწმოთ რომ დავრწმუნდეთ, რომ ახალი კვანძში არ არის ტოლი null.

741
01:00:39,910 --> 01:00:42,910
ან ნაცვლად, ჩვენ შეგვიძლია მხოლოდ თუ ის რეალურად არის null,

742
01:00:42,910 --> 01:00:52,120
და თუ ეს null, მაშინ ჩვენ შეგვიძლია მხოლოდ დაბრუნების ცრუ დასაწყისში.

743
01:00:52,120 --> 01:00:59,090
>> ამ ეტაპზე, ჩვენ უნდა WIRE ახალი კვანძის მის შესაბამის ადგილზე in ხე.

744
01:00:59,090 --> 01:01:03,510
თუ ჩვენ ვიხსენებთ ძირითად და სად ვიყავით რეალურად გაყვანილობა წელს ფასეულობების წინაშე,

745
01:01:03,510 --> 01:01:08,470
ჩვენ ვხედავთ, რომ გზა ვაკეთებდით, როცა გვინდოდა დააყენა 3 in ხე

746
01:01:08,470 --> 01:01:11,750
იყო ჩვენ შემოწმდა მარცხენა ბავშვის ძირეული.

747
01:01:11,750 --> 01:01:14,920
როდესაც ჩვენ დააყენა 9 in ხე, გვქონდა წვდომისათვის უფლება ბავშვი root.

748
01:01:14,920 --> 01:01:21,030
ჩვენ უნდა აქვს მომცეთ მშობელს, რათა დააყენოს ახალი მნიშვნელობის შევიდა ხე.

749
01:01:21,030 --> 01:01:24,430
სენსორული უკან მდე ჩადეთ, რომ არ აპირებს საკმაოდ მუშაობა აქ

750
01:01:24,430 --> 01:01:27,550
იმიტომ, რომ ჩვენ არ გვაქვს მშობელი მაჩვენებელი.

751
01:01:27,550 --> 01:01:31,650
რა გვინდა გამოუვა არის, ამ ეტაპზე,

752
01:01:31,650 --> 01:01:37,080
შეამოწმეთ მშობლის ღირებულება და ვხედავ - ისე, gosh,

753
01:01:37,080 --> 01:01:41,990
თუ მშობლის მნიშვნელობა ნაკლებია მიმდინარე ღირებულება,

754
01:01:41,990 --> 01:01:54,440
მაშინ მშობლის უფლება ბავშვი უნდა იყოს ახალი კვანძში;

755
01:01:54,440 --> 01:02:07,280
წინააღმდეგ შემთხვევაში, მშობლის მარცხენა ბავშვი უნდა იყოს ახალი კვანძში.

756
01:02:07,280 --> 01:02:10,290
მაგრამ, ჩვენ არ გვაქვს ამ მშობელს მაჩვენებელი საკმაოდ ამჟამად.

757
01:02:10,290 --> 01:02:15,010
>> იმისათვის, რომ მიიღოთ ის, რომ ჩვენ რეალურად აპირებს უნდა აკონტროლოთ, როგორც ჩვენ გაიაროს ხე

758
01:02:15,010 --> 01:02:18,440
და იპოვოს შესაბამისი ლაქა ჩვენს loop ზემოთ.

759
01:02:18,440 --> 01:02:26,840
ჩვენ შეგვიძლია გავაკეთოთ, რომ სენსორული უკან მდე ზევით ჩვენი ჩანართით ფუნქცია

760
01:02:26,840 --> 01:02:32,350
და თვალთვალის სხვა კურსორი ცვლადში მშობელი.

761
01:02:32,350 --> 01:02:39,340
ჩვენ სხვებისათვის იგი ტოლია null თავდაპირველად,

762
01:02:39,340 --> 01:02:43,640
და შემდეგ ყოველ ჯერზე ჩვენ გაიაროს ხე,

763
01:02:43,640 --> 01:02:51,540
ჩვენ სხვებისათვის მშობელი მაჩვენებელი ემთხვევა მიმდინარე მაჩვენებელი.

764
01:02:51,540 --> 01:02:59,140
უცნობია მშობლის ტოლი მიმდ..

765
01:02:59,140 --> 01:03:02,260
ეს გზა, ყოველ ჯერზე ჩვენ გაიაროს,

766
01:03:02,260 --> 01:03:05,550
ჩვენ ვაპირებთ, რომ უზრუნველყოფილ იქნას როგორც მიმდინარე კურსორი იღებს incremented

767
01:03:05,550 --> 01:03:12,640
მშობელი მაჩვენებელი შემდეგნაირად ეს - მხოლოდ ერთი დონის უფრო მაღალია, ვიდრე მიმდინარე წელს მაჩვენებელი ხე.

768
01:03:12,640 --> 01:03:17,370
რომ ყველა გამოიყურება საკმაოდ კარგი.

769
01:03:17,370 --> 01:03:22,380
>> ვფიქრობ, ერთი რამ, რომ ჩვენ გვინდა შეცვალოს ეს აშენება კვანძის დაბრუნების null.

770
01:03:22,380 --> 01:03:25,380
მისაღებად აშენება კვანძის რეალურად წარმატებით დაბრუნებას null,

771
01:03:25,380 --> 01:03:31,060
ჩვენ უნდა ცვლილებები, რომ კოდი,

772
01:03:31,060 --> 01:03:37,270
რადგან აქ, ჩვენ არასოდეს ტესტირება, რათა დავრწმუნდეთ, რომ malloc დაბრუნდა სწორი მაჩვენებელი.

773
01:03:37,270 --> 01:03:53,390
ასე რომ, თუ (N! = NULL), მაშინ -

774
01:03:53,390 --> 01:03:55,250
თუ malloc დაბრუნდა სწორი მაჩვენებელი, მაშინ ჩვენ ინიციალიზაცია მას;

775
01:03:55,250 --> 01:04:02,540
წინააღმდეგ შემთხვევაში, ჩვენ უბრალოდ დაბრუნდება და რომ დასრულდება მდე დაბრუნების null ჩვენთვის.

776
01:04:02,540 --> 01:04:13,050
ახლა ყველა გამოიყურება საკმაოდ კარგი. მოდით დარწმუნდით ამ ფაქტობრივად ადგენს.

777
01:04:13,050 --> 01:04:22,240
ჩადება ორობითი ხე, და oh, გვაქვს რაღაცები ხდება აქ.

778
01:04:22,240 --> 01:04:29,230
>> გვაქვს დაფარული დეკლარაციის ფუნქციის აშენება კვანძში.

779
01:04:29,230 --> 01:04:31,950
ერთხელ, ამ compilers, ჩვენ ვაპირებთ დავიწყოთ ზედა.

780
01:04:31,950 --> 01:04:36,380
რა უნდა ნიშნავდეს ის არის, რომ მე მოუწოდებდა აშენება კვანძის ადრე მე რეალურად გამოაცხადა.

781
01:04:36,380 --> 01:04:37,730
მოდით დავუბრუნდეთ კოდი მართლაც სწრაფად.

782
01:04:37,730 --> 01:04:43,510
Scroll down, და დარწმუნებული საკმარისი, ჩემი ჩანართით ფუნქცია ცხადდება

783
01:04:43,510 --> 01:04:47,400
ზემოთ Build კვანძის ფუნქციას,

784
01:04:47,400 --> 01:04:50,070
მაგრამ ვცდილობ გამოიყენოთ აშენება კვანძის შიგნით ჩანართით.

785
01:04:50,070 --> 01:05:06,610
მე ვაპირებ წავიდეს და ასლი - და შემდეგ ჩასვით Build კვანძის ფუნქციას გზა აქ ზედა.

786
01:05:06,610 --> 01:05:11,750
ამ გზით, იმედია იმუშავებს. მოდით მივცეთ ამ მეორე წასვლა.

787
01:05:11,750 --> 01:05:18,920
ახლა კი ყველა ადგენს. ყველა კარგია.

788
01:05:18,920 --> 01:05:21,640
>> მაგრამ ამ ეტაპზე, ჩვენ არ რეალურად მოუწოდა ჩვენი ჩანართით ფუნქცია.

789
01:05:21,640 --> 01:05:26,510
ჩვენ უბრალოდ ვიცით, რომ ეს კომპილაციისას მოდით წავიდეთ და დააყენა რამდენიმე მოუწოდებს სისტემაში

790
01:05:26,510 --> 01:05:28,240
მოდით, რომ ჩვენი მთავარი ფუნქცია.

791
01:05:28,240 --> 01:05:32,390
აქ, ჩვენ კომენტარს გარეთ 5, 8, და 2,

792
01:05:32,390 --> 01:05:36,680
და მაშინ ჩვენ არ WIRE მათ ქვემოთ აქ.

793
01:05:36,680 --> 01:05:41,640
მოდით გარკვეული მოუწოდებს ჩასასმელად,

794
01:05:41,640 --> 01:05:46,440
და მოდით ასევე გამოიყენოთ იგივე პერსონალი, რომ ჩვენ გამოყენებული

795
01:05:46,440 --> 01:05:52,810
როცა ჩვენ მივიღეთ ამ printf მოუწოდებს დავრწმუნდეთ, რომ ყველაფერი ისე მიიღოს ჩასმული სწორად.

796
01:05:52,810 --> 01:06:00,550
მე ვაპირებ დააკოპირეთ და ჩასვით,

797
01:06:00,550 --> 01:06:12,450
და ნაცვლად შეიცავს ჩვენ ვაპირებთ ჩანართით.

798
01:06:12,450 --> 01:06:30,140
და ნაცვლად 6, 10 და 1, ჩვენ ვაპირებთ გამოვიყენოთ 5, 8, და 2.

799
01:06:30,140 --> 01:06:37,320
ეს უნდა იმედია ჩადეთ 5, 8, და 2 შევიდა ხე.

800
01:06:37,320 --> 01:06:44,050
კომპილირდება. ყველა კარგია. ახლა ჩვენ რეალურად აწარმოებს ჩვენი პროგრამა.

801
01:06:44,050 --> 01:06:47,330
>> ყველაფერი დაბრუნდა ყალბი.

802
01:06:47,330 --> 01:06:53,830
ასე რომ, 5, 8, და 2 არ წასვლა, და გამოიყურება შეიცავს ვერ მათ არც.

803
01:06:53,830 --> 01:06:58,890
რა ხდება? მოდით დააშორებს.

804
01:06:58,890 --> 01:07:02,160
პირველი პრობლემა ის იყო, რომ ჩანართით ჩანდა დაბრუნების ცრუ,

805
01:07:02,160 --> 01:07:08,750
და როგორც ჩანს ეს იმიტომ, რომ ჩვენ დარჩა ჩვენი დაბრუნების ცრუ ზარი,

806
01:07:08,750 --> 01:07:14,590
და ჩვენ არასოდეს რეალურად დაბრუნდა ჭეშმარიტი.

807
01:07:14,590 --> 01:07:17,880
ჩვენ შეგვიძლია მითითებული, რომ up.

808
01:07:17,880 --> 01:07:25,290
მეორე პრობლემა ისაა, ახლა კი, თუ ჩვენ გავაკეთებთ - შენახვა ამ, დატოვა ეს,

809
01:07:25,290 --> 01:07:34,530
აწარმოებს გააკეთოს ერთხელ, არ ის კომპილირება, მაშინ გაუშვით -

810
01:07:34,530 --> 01:07:37,670
ჩვენ ვხედავთ, რომ რაღაც მოხდა აქ.

811
01:07:37,670 --> 01:07:42,980
5, 8 და 2 მაინც არასოდეს ნაპოვნი ხე.

812
01:07:42,980 --> 01:07:44,350
ასე რომ, რა ხდება?

813
01:07:44,350 --> 01:07:45,700
>> მოდით შევხედოთ ამ კოდექსში.

814
01:07:45,700 --> 01:07:49,790
მოდით ვნახოთ, თუ შევძლებთ გაერკვნენ ამ გარეთ.

815
01:07:49,790 --> 01:07:57,940
ჩვენ დავიწყებთ მშობელს არ ყოფნის null.

816
01:07:57,940 --> 01:07:59,510
ჩვენ დავსახეთ მიმდინარე მაჩვენებელი ტოლია root მაჩვენებელი,

817
01:07:59,510 --> 01:08:04,280
და ჩვენ ვაპირებთ მუშაობას ჩვენი გზა ქვემოთ მეშვეობით ხე.

818
01:08:04,280 --> 01:08:08,650
თუ მიმდინარე კვანძში არ null, მაშინ ჩვენ ვიცით, რომ ჩვენ შეგვიძლია ქვევით ცოტა.

819
01:08:08,650 --> 01:08:12,330
ჩვენ დავსახეთ ჩვენი მშობელი მომცეთ თანაბარია მიმდინარე მაჩვენებელი,

820
01:08:12,330 --> 01:08:15,420
შემოწმდება ღირებულება - თუ ღირებულებები იგივე დავბრუნდით ყალბი.

821
01:08:15,420 --> 01:08:17,540
თუ ღირებულებები ნაკლებად გადავედით უფლება;

822
01:08:17,540 --> 01:08:20,399
წინააღმდეგ შემთხვევაში, ჩვენ გადავიდა მარცხენა.

823
01:08:20,399 --> 01:08:24,220
მაშინ ჩვენ ავაშენებთ კვანძში. მე დიდი ზომით ცოტა.

824
01:08:24,220 --> 01:08:31,410
და აქ, ჩვენ ვაპირებთ ცდილობენ WIRE up ღირებულებების იყოს იგივე.

825
01:08:31,410 --> 01:08:37,250
რა ხდება? ვნახოთ, თუ შესაძლოა Valgrind შეუძლია მოგვცეს მინიშნება.

826
01:08:37,250 --> 01:08:43,910
>> მომწონს გამოიყენოს Valgrind მხოლოდ იმიტომ Valgrind მართლაც სწრაფად გადის

827
01:08:43,910 --> 01:08:46,729
და გიჩვენებთ, თუ არსებობს რაიმე მეხსიერების შეცდომები.

828
01:08:46,729 --> 01:08:48,300
როდესაც ჩვენ აწარმოებს Valgrind on კოდი,

829
01:08:48,300 --> 01:08:55,859
როგორც ხედავთ უფლება here--Valgrind./binary_tree--and დააჭიროთ.

830
01:08:55,859 --> 01:09:03,640
ხედავთ, რომ ჩვენ არ გვაქვს რაიმე მეხსიერების შეცდომა, ასე გამოიყურება ყველაფერი okay ჯერჯერობით.

831
01:09:03,640 --> 01:09:07,529
ჩვენ გვაქვს გარკვეული მეხსიერების ტბები, რომელიც ჩვენ ვიცით, იმიტომ, რომ ჩვენ არ ვართ

832
01:09:07,529 --> 01:09:08,910
ხდება გასათავისუფლებლად ჩვენს ნებისმიერ კვანძების.

833
01:09:08,910 --> 01:09:13,050
მოდით ვეცადოთ გაშვებული GDB რა სინამდვილეში ხდება.

834
01:09:13,050 --> 01:09:20,010
ჩვენ ყველაფერს გავაკეთებთ GDB. / Binary_tree. ეს გაიჭედოთ up მხოლოდ ჯარიმა.

835
01:09:20,010 --> 01:09:23,670
მოდით მითითებული შესვენების წერტილი ჩანართით.

836
01:09:23,670 --> 01:09:28,600
მოდით აწარმოებს.

837
01:09:28,600 --> 01:09:31,200
როგორც ჩანს ჩვენ არასოდეს რეალურად მოუწოდა ჩანართით.

838
01:09:31,200 --> 01:09:39,410
როგორც ჩანს პრობლემა იყო, რომ როდესაც მე შეიცვალა ქვემოთ აქ მთავარი -

839
01:09:39,410 --> 01:09:44,279
ყველა ამ printf ზარები შეიცავს -

840
01:09:44,279 --> 01:09:56,430
მე არასოდეს რეალურად შეიცვალა ამ მოვუწოდო ჩანართით.

841
01:09:56,430 --> 01:10:01,660
ახლა მოდით გინება. მოდით შეადგინონ.

842
01:10:01,660 --> 01:10:09,130
ყველა გამოიყურება კარგი არსებობს. ახლა მოდით შევეცადოთ გაშვებული ის, ვნახოთ, რა მოხდება.

843
01:10:09,130 --> 01:10:13,320
კარგად! ყველაფერი გამოიყურება საკმაოდ კარგი არსებობს.

844
01:10:13,320 --> 01:10:18,130
>> საბოლოო რამ ფიქრი არის, მოქმედებს თუ არა პირას შემთხვევებში ამ ჩანართით?

845
01:10:18,130 --> 01:10:23,170
და აღმოჩნდება, რომ, ისევე, ერთ კიდეზე შემთხვევაში, რომ ყოველთვის საინტერესო ფიქრი

846
01:10:23,170 --> 01:10:26,250
არის, რა მოხდება თუ თქვენი ხე არის ცარიელი და რეკავთ ამ ჩანართით ფუნქცია?

847
01:10:26,250 --> 01:10:30,330
Will მუშაობს იგი? კარგად, მოდით გინება.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree. გ -

849
01:10:32,110 --> 01:10:35,810
გზა ჩვენ ვაპირებთ შევამოწმოთ ეს, ჩვენ ვაპირებთ ქვევით ჩვენი მთავარი ფუნქცია,

850
01:10:35,810 --> 01:10:41,690
და ვიდრე გაყვანილობა ამ კვანძების up მოსწონს,

851
01:10:41,690 --> 01:10:56,730
ჩვენ უბრალოდ აპირებს კომენტარის მთელი რამ,

852
01:10:56,730 --> 01:11:02,620
და ნაცვლად გაყვანილობა up კვანძების თავს,

853
01:11:02,620 --> 01:11:09,400
ჩვენ შეგვიძლია რეალურად მხოლოდ წავიდეთ წინ და წაშლა ყველა ამ.

854
01:11:09,400 --> 01:11:17,560
ჩვენ ვაპირებთ, რათა ყველაფერი ზარის ჩასასმელად.

855
01:11:17,560 --> 01:11:49,020
ასე რომ, მოდით - ის ნაცვლად 5, 8, და 2, ჩვენ ვაპირებთ ჩადეთ 7, 3, და 9.

856
01:11:49,020 --> 01:11:58,440
და მაშინ საბოლოოდ დავრწმუნდებით ასევე მინდა ჩადეთ 6 ისევე.

857
01:11:58,440 --> 01:12:05,190
შენახვა. Quit. ჩადება ორობითი ხე.

858
01:12:05,190 --> 01:12:08,540
ყველაფერი ადგენს.

859
01:12:08,540 --> 01:12:10,320
ჩვენ შეგვიძლია მხოლოდ აწარმოებს, როგორც არის და ვნახოთ, რა მოხდება,

860
01:12:10,320 --> 01:12:12,770
მაგრამ ასევე იქნება მართლაც მნიშვნელოვანია დავრწმუნდეთ, რომ

861
01:12:12,770 --> 01:12:14,740
ჩვენ არ გვაქვს რაიმე მეხსიერების შეცდომები,

862
01:12:14,740 --> 01:12:16,840
რადგან ეს არის ჩვენი ერთი პირას შემთხვევებში, რომ ვიცით.

863
01:12:16,840 --> 01:12:20,150
>> მოდით დარწმუნდით რომ იგი კარგად მუშაობს ქვეშ Valgrind,

864
01:12:20,150 --> 01:12:28,310
რომელსაც ჩვენ გავაკეთებთ მხოლოდ გაშვებული Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
როგორც ჩანს ჩვენ მართლაც გვაქვს ერთი შეცდომა ერთ კონტექსტში -

866
01:12:31,110 --> 01:12:33,790
ჩვენ გვაქვს ამ სეგმენტაცია ბრალია.

867
01:12:33,790 --> 01:12:36,690
რა მოხდა?

868
01:12:36,690 --> 01:12:41,650
Valgrind ფაქტობრივად გვეუბნება, სადაც იგი.

869
01:12:41,650 --> 01:12:43,050
დაპატარავება ცოტა.

870
01:12:43,050 --> 01:12:46,040
როგორც ჩანს ეს ხდება ჩვენი ჩანართით ფუნქცია,

871
01:12:46,040 --> 01:12:53,420
რომელშიც ჩვენ არასწორი წაკითხული of ზომა 4 საათზე ჩანართით, ხაზი 60.

872
01:12:53,420 --> 01:13:03,590
მოდით დავუბრუნდეთ და ვნახოთ, რა ხდება აქ.

873
01:13:03,590 --> 01:13:05,350
დაპატარავება მართლაც სწრაფი.

874
01:13:05,350 --> 01:13:14,230
მე გვინდა დავრწმუნდეთ, რომ არ წასულიყვნენ ზღვარზე ეკრანზე ასე ვხედავთ ყველაფერს.

875
01:13:14,230 --> 01:13:18,760
გაიგეთ, რომ ცოტა. კარგად.

876
01:13:18,760 --> 01:13:35,030
Scroll down, და პრობლემა ის არის, უფლება აქ.

877
01:13:35,030 --> 01:13:40,120
რა მოხდება თუ არ მივიღებთ ქვემოთ და ჩვენი დღევანდელი კვანძის უკვე null,

878
01:13:40,120 --> 01:13:44,010
ჩვენი მშობელი კვანძი არის null ასე რომ, თუ გადავხედავთ up at ძალიან დაბრუნება, სწორედ აქ -

879
01:13:44,010 --> 01:13:47,340
თუ ეს მაშინ, როცა მარყუჟის არასოდეს რეალურად ახორციელებს

880
01:13:47,340 --> 01:13:52,330
რადგან ჩვენი დღევანდელი ღირებულება null - ჩვენი root არის null ისე მიმდ. არის null -

881
01:13:52,330 --> 01:13:57,810
მაშინ ჩვენი მშობელი არასოდეს იღებს მითითებული მიმდ. ან სწორი ღირებულება,

882
01:13:57,810 --> 01:14:00,580
ამიტომ, მშობელი იქნება null.

883
01:14:00,580 --> 01:14:03,700
ჩვენ უნდა გვახსოვდეს, შევამოწმოთ, რომ

884
01:14:03,700 --> 01:14:08,750
იმ დროისთვის, მივიღებთ ქვემოთ აქ, და ჩვენ ვიწყებთ წვდომის მშობლის ღირებულება.

885
01:14:08,750 --> 01:14:13,190
ასე რომ, რა ხდება? ისე, თუ მშობელი არის null -

886
01:14:13,190 --> 01:14:17,990
თუ (მშობელი == NULL) - მაშინ ჩვენ ვიცით, რომ

887
01:14:17,990 --> 01:14:19,530
იქ არ უნდა იყოს არაფერი ხე.

888
01:14:19,530 --> 01:14:22,030
ჩვენ უნდა ცდილობს ჩადეთ იგი root.

889
01:14:22,030 --> 01:14:32,570
ჩვენ შეგვიძლია გავაკეთოთ, რომ მხოლოდ შექმნის root ტოლი ახალი კვანძში.

890
01:14:32,570 --> 01:14:40,010
მაშინ ამ ეტაპზე, ჩვენ არ ნამდვილად გინდათ გავლა ამ სხვა რამ.

891
01:14:40,010 --> 01:14:44,780
სამაგიეროდ, სწორედ აქ, ჩვენ შეგვიძლია გავაკეთოთ ან სხვაგან თუ-სხვაგან,

892
01:14:44,780 --> 01:14:47,610
ან ჩვენ შეგვიძლია დააკავშიროთ ყველაფერი up აქ სხვაგან,

893
01:14:47,610 --> 01:14:56,300
მაგრამ აქ ჩვენ მხოლოდ გამოიყენოს სხვაგან და ამის გაკეთება, რომ გზა.

894
01:14:56,300 --> 01:14:59,030
ახლა ჩვენ ვაპირებთ შევამოწმოთ რომ დავრწმუნდეთ, რომ ჩვენი მშობელი არ არის null

895
01:14:59,030 --> 01:15:02,160
ადრე მაშინ რეალურად ცდილობს წვდომას თავისი სფეროებში.

896
01:15:02,160 --> 01:15:05,330
ეს დაგვეხმარება თავიდან ავიცილოთ სეგმენტაცია ბრალია.

897
01:15:05,330 --> 01:15:14,740
ასე რომ, ჩვენ დატოვა, zoom out, კომპილაციის, აწარმოებს.

898
01:15:14,740 --> 01:15:18,130
>> არარის შეცდომები, მაგრამ ჩვენ ჯერ კიდევ არის რამოდენიმე მეხსიერების გაჟონვის

899
01:15:18,130 --> 01:15:20,650
რადგან ჩვენ ვერ გასათავისუფლებლად ჩვენს ნებისმიერ კვანძების.

900
01:15:20,650 --> 01:15:24,350
მაგრამ, თუ ჩვენ აქ და შევხედავთ ჩვენი ამონაწერი,

901
01:15:24,350 --> 01:15:30,880
ჩვენ ვხედავთ, რომ, ისევე, ჰგავს ყველა ჩვენი ჩანართები ბრუნდებოდა ჭეშმარიტი, რომელიც არის კარგი.

902
01:15:30,880 --> 01:15:33,050
ჩანართები ყველა ასეა,

903
01:15:33,050 --> 01:15:36,670
და შემდეგ შესაბამისი არსებული მოწოდებით ასევე ჭეშმარიტი.

904
01:15:36,670 --> 01:15:41,510
>> კარგ საქმეს! როგორც ჩანს ჩვენ წარმატებით წერილობითი ჩანართით.

905
01:15:41,510 --> 01:15:47,430
სულ ეს გვაქვს ამ კვირაში პრობლემა Set სპეციფიკაცია.

906
01:15:47,430 --> 01:15:51,720
ერთი fun გამოწვევა ფიქრი არის, როგორ რეალურად წავიდეს

907
01:15:51,720 --> 01:15:55,340
და თავისუფალი ყველა კვანძების ამ ხეს.

908
01:15:55,340 --> 01:15:58,830
ჩვენ შეგვიძლია ამის გაკეთება რამდენიმე განსხვავებული გზები,

909
01:15:58,830 --> 01:16:01,930
მაგრამ დავტოვებთ, რომ თქვენი ექსპერიმენტი,

910
01:16:01,930 --> 01:16:06,080
და როგორც fun გამოწვევა, სცადეთ და დარწმუნდით, რომ თქვენ შეგიძლიათ დარწმუნდეთ

911
01:16:06,080 --> 01:16:09,490
რომ ეს Valgrind ანგარიში ბრუნდება შეუცდომლობის და არ გაჟონვის.

912
01:16:09,490 --> 01:16:12,880
>> წარმატებებს გისურვებთ ამ კვირის Huffman კოდირების პრობლემა კომპლექტი,

913
01:16:12,880 --> 01:16:14,380
და ვნახავთ, თქვენ მომავალ კვირას?

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]