1
00:00:07,050 --> 00:00:09,630
[Powered by Google Translate] რა წარმოადგენს ყველა თქვენი ოჯახის წევრების კომპიუტერი?

2
00:00:10,790 --> 00:00:12,390
ჩვენ უბრალოდ გამოიყენოთ სია,

3
00:00:12,390 --> 00:00:14,400
მაგრამ წმინდა იერარქია აქ.

4
00:00:14,400 --> 00:00:17,110
>> ვთქვათ ჩვენ დაწყებული თქვენი დიდი ბებია, Alice.

5
00:00:17,110 --> 00:00:19,030
მას 2 ვაჟი, ბობ

6
00:00:19,030 --> 00:00:21,310
და თქვენი ბაბუა, ჩარლი.

7
00:00:21,310 --> 00:00:23,190
ჩარლი ჰყავს 3 შვილი,

8
00:00:23,190 --> 00:00:26,730
თქვენი ბიძა, Dave, თქვენი დეიდა, ევა, და თქვენი მამა, ფრედ.

9
00:00:26,730 --> 00:00:28,750
თქვენ ხართ Fred ერთადერთი შვილი.

10
00:00:28,750 --> 00:00:30,950
>> რატომ უნდა ორგანიზება თქვენი ოჯახის წევრები ამ გზით

11
00:00:30,950 --> 00:00:34,010
უკეთესი, ვიდრე უბრალო სია წარმომადგენლობა?

12
00:00:34,010 --> 00:00:36,630
ერთი მიზეზი ის არის, რომ ეს იერარქიული სტრუქტურა,

13
00:00:36,630 --> 00:00:39,660
მოუწოდა "ხე", შეიცავს მეტ ინფორმაციას, ვიდრე უბრალო სია.

14
00:00:40,540 --> 00:00:43,520
ჩვენ ვიცით ოჯახური ურთიერთობებს ყველას

15
00:00:43,520 --> 00:00:45,440
მხოლოდ შემოწმებას ხე.

16
00:00:45,440 --> 00:00:47,250
ასევე, მას შეუძლია დააჩქაროს

17
00:00:47,250 --> 00:00:50,010
ნახვა-up დროს საოცრად, თუ ხე მონაცემები დალაგებულია.

18
00:00:50,010 --> 00:00:53,850
>> ჩვენ ვერ ვისარგებლებთ, რომ აქ, მაგრამ ჩვენ დავინახავთ მაგალითია მალე.

19
00:00:53,850 --> 00:00:56,150
თითოეულმა ადამიანმა წარმოდგენილია კვანძის on ხე.

20
00:00:56,680 --> 00:00:58,370
კვანძების შეიძლება ჰქონდეს ბავშვის კვანძების

21
00:00:58,370 --> 00:01:00,350
ისევე როგორც მშობელი კვანძი.

22
00:01:00,350 --> 00:01:02,390
ეს არის ტექნიკური თვალსაზრისით,

23
00:01:02,390 --> 00:01:05,220
მაშინაც კი, როდესაც გამოყენებით ხეების რამ გარდა ოჯახებს.

24
00:01:05,220 --> 00:01:07,940
Alice-ის კვანძის აქვს 2 შვილი და არ მშობლები,

25
00:01:07,940 --> 00:01:11,500
ხოლო ჩარლი მისი კვანძის ჰყავს 3 შვილი და 1 მშობელი.

26
00:01:11,500 --> 00:01:14,330
>> ფოთოლი კვანძში, რომელიც არ აქვს არც ბავშვები

27
00:01:14,330 --> 00:01:16,410
on გარეთ კიდეზე ხე.

28
00:01:16,410 --> 00:01:18,520
ზედოთ მდებარე კვანძის ხე, ძირეული კვანძის,

29
00:01:18,520 --> 00:01:20,240
ვიზიტორების მშობელი.

30
00:01:20,240 --> 00:01:23,170
>> ორობითი ხე არის კონკრეტული ტიპის ხე,

31
00:01:23,170 --> 00:01:26,720
რომელშიც თითოეული კვანძის აქვს, უმეტეს, 2 შვილი.

32
00:01:26,720 --> 00:01:30,490
აქ არის struct of node of ორობითი ხე C.

33
00:01:31,560 --> 00:01:34,530
ყველა კვანძის აქვს გარკვეული მონაცემები ასოცირდება იგი

34
00:01:34,530 --> 00:01:36,520
და 2 მითითებას სხვა კვანძების.

35
00:01:36,520 --> 00:01:38,110
>> ჩვენი ოჯახის ხე,

36
00:01:38,110 --> 00:01:40,900
ასოცირებული მონაცემები იყო თითოეული ადამიანის სახელი.

37
00:01:40,900 --> 00:01:43,850
აქ არის int, თუმცა ეს შეიძლება იყოს არაფერს.

38
00:01:44,510 --> 00:01:46,200
როგორც ირკვევა,

39
00:01:46,200 --> 00:01:48,990
ორობითი ხე არ იქნებოდა კარგი წარმომადგენლობა საოჯახო,

40
00:01:48,990 --> 00:01:51,960
რადგან ადამიანები ხშირად უფრო მეტია, ვიდრე 2 შვილი.

41
00:01:51,960 --> 00:01:53,510
>> ორობითი ძებნა tree

42
00:01:53,510 --> 00:01:56,380
არის სპეციალური დავალებით ტიპის ორობითი ხე

43
00:01:56,380 --> 00:01:58,090
რომ საშუალებას გვაძლევს შევხედოთ ფასეულობების სწრაფად.

44
00:01:58,740 --> 00:02:00,050
თქვენ შეიძლება არ შეამჩნია

45
00:02:00,050 --> 00:02:02,010
რომ ყველა კვანძის ქვემოთ ფესვი ხე

46
00:02:02,010 --> 00:02:04,620
არის root სხვა ხე, რომელსაც ეწოდება "subtree. '

47
00:02:04,960 --> 00:02:07,090
აქ ფესვი ხე 6,

48
00:02:07,090 --> 00:02:09,860
და მისი შვილი, 2, არის ფესვი subtree.

49
00:02:09,860 --> 00:02:11,870
>> In ორობითი ძებნა tree

50
00:02:11,870 --> 00:02:15,790
ყველა ღირებულებებს კვანძის უფლება subtree

51
00:02:15,790 --> 00:02:18,690
მეტი კვანძის ღირებულების. აქ: 6.

52
00:02:18,690 --> 00:02:22,640
ისე, ღირებულებების კვანძის მარცხენა subtree

53
00:02:24,540 --> 00:02:26,890
ნაკლებია კვანძის ღირებულების.

54
00:02:26,890 --> 00:02:28,620
თუ ჩვენ გვჭირდება გაუმკლავდეს დუბლიკატი ღირებულებების,

55
00:02:28,620 --> 00:02:31,760
ჩვენ შეგვიძლია შევცვალოთ ან იმ to loose უთანასწორობა,

56
00:02:31,760 --> 00:02:34,410
რაც იმას ნიშნავს, იდენტური ღირებულებებს შეიძლება დაეცემა ან მარცხენა ან მარჯვენა,

57
00:02:34,410 --> 00:02:37,400
სანამ ჩვენ თანმიმდევრული ამის შესახებ მასშტაბით.

58
00:02:37,400 --> 00:02:39,620
ეს ხე არის ორობითი ძებნა tree

59
00:02:39,620 --> 00:02:41,540
რადგან ეს შემდეგნაირად ამ წესებს.

60
00:02:42,320 --> 00:02:46,020
>> ეს არის, თუ როგორ გამოიყურება თუ გადავედით ყველა კვანძების შევიდა C structs.

61
00:02:46,880 --> 00:02:48,410
გაითვალისწინეთ, რომ თუ ბავშვი არის დაკარგული,

62
00:02:48,410 --> 00:02:50,340
კურსორი არის null.

63
00:02:50,340 --> 00:02:53,270
როგორ შეამოწმეთ, რომ 7 არის ხე?

64
00:02:53,270 --> 00:02:55,020
ჩვენ იწყება root.

65
00:02:55,020 --> 00:02:58,690
შვიდი მეტია 6 ასე რომ, თუ ეს წელს ხე, ეს უნდა იყოს სწორი.

66
00:02:59,680 --> 00:03:03,650
მაშინ იგი ნაკლებია, ვიდრე 8, ასე რომ უნდა დაუტოვებიათ.

67
00:03:03,650 --> 00:03:06,210
აქ, ჩვენ მოვნახეთ 7.

68
00:03:06,210 --> 00:03:08,160
ახლა, ჩვენ შევამოწმოთ 5.

69
00:03:08,160 --> 00:03:11,500
ხუთი ნაკლებია, ვიდრე 6, ასე რომ უნდა იყოს მარცხნივ.

70
00:03:11,500 --> 00:03:13,460
ხუთი მეტია 2,

71
00:03:13,460 --> 00:03:15,010
ასე რომ უნდა იყოს უფლება,

72
00:03:15,010 --> 00:03:18,100
და ისიც აღემატება 4, ასე რომ უნდა იყოს უფლება კვლავ.

73
00:03:18,100 --> 00:03:20,300
თუმცა, არ არსებობს ბავშვი აქ.

74
00:03:20,300 --> 00:03:22,000
კურსორი არის null.

75
00:03:22,000 --> 00:03:24,270
ეს ნიშნავს, რომ 5 არ არის ჩვენი ხე.

76
00:03:24,270 --> 00:03:27,250
>> ჩვენ შეგვიძლია ძებნის ორობითი ხე შემდეგი კოდი:

77
00:03:28,430 --> 00:03:31,140
ყოველ კვანძში, ჩვენ შეამოწმეთ, რომ ჩვენ მოვნახეთ

78
00:03:31,140 --> 00:03:33,020
ღირებულება ვეძებთ.

79
00:03:33,020 --> 00:03:35,740
თუ ჩვენ ვერ, ჩვენ განსაზღვროს, თუ იგი უნდა იყოს

80
00:03:35,740 --> 00:03:38,990
მარცხენა ან მარჯვენა და შეამოწმოს, რომ subtree.

81
00:03:38,990 --> 00:03:41,160
ეს loop გააგრძელებს ქვემოთ ხე

82
00:03:41,160 --> 00:03:44,190
სანამ არ არსებობს ბავშვის კვანძის ორივე მარცხენა ან მარჯვენა.

83
00:03:45,190 --> 00:03:48,600
>> გახსოვდეთ, რომ 5 არ იყო ხე.

84
00:03:48,600 --> 00:03:50,460
როგორ უნდა ჩადოთ ეს?

85
00:03:50,460 --> 00:03:52,370
პროცესი გამოიყურება მსგავსი ძებნის.

86
00:03:52,370 --> 00:03:54,830
ჩვენ iterate ქვემოთ ხე დაწყებული 6,

87
00:03:54,830 --> 00:03:57,040
მარცხნიდან 2,

88
00:03:57,040 --> 00:03:59,140
უფლება 4,

89
00:03:59,140 --> 00:04:02,500
და მარჯვენა ისევ, მაგრამ 4 ვიზიტორების ბავშვი ამ მხარეს.

90
00:04:02,500 --> 00:04:06,090
ეს იქნება ახალი თანამდებობაზე 5,

91
00:04:06,090 --> 00:04:08,500
და ეს დაიწყება არ მყავს ბავშვები.

92
00:04:09,020 --> 00:04:12,220
>> როგორ სწრაფად ხართ ოპერაციების ორობითი ძებნა ხე?

93
00:04:12,220 --> 00:04:15,410
გახსოვდეთ, რომ Bigohnotation ცდილობს უზრუნველყოს ზედა შეკრული.

94
00:04:15,410 --> 00:04:17,390
ყველაზე ცუდ შემთხვევაში,

95
00:04:17,390 --> 00:04:19,480
ჩვენი ხე უბრალოდ იყოს დაკავშირებული სია

96
00:04:19,480 --> 00:04:22,220
რაც იმას ნიშნავს, რომ Insertion, წაშლის, და ძებნა

97
00:04:22,220 --> 00:04:25,380
შეეძლო დროის პროპორციული რაოდენობის კვანძების ხე.

98
00:04:25,380 --> 00:04:27,380
ეს არის O (N).

99
00:04:27,380 --> 00:04:30,690
>> მაგალითად, შემდეგ არის სწორი ორობითი ძებნა ხე.

100
00:04:31,850 --> 00:04:34,020
თუმცა, თუ ჩვენ ვცდილობთ ვიპოვოთ 9,

101
00:04:34,020 --> 00:04:36,760
ჩვენ უნდა traverse ყველა კვანძში.

102
00:04:36,760 --> 00:04:39,120
არავისთვის არ არის უკეთესი, ვიდრე უკავშირდება სიაში.

103
00:04:39,120 --> 00:04:41,410
იდეალურ შემთხვევაში, ჩვენ გვინდა ყველა კვანძის

104
00:04:41,410 --> 00:04:44,120
ჩვენი ორობითი ძებნა ხე აქვს 2 შვილი.

105
00:04:44,120 --> 00:04:46,370
ეს გზა, Insertion, წაშლა და ძებნა

106
00:04:46,370 --> 00:04:50,190
მიიღებს, ზე უარესი, O (შესვლა n) დრო.

107
00:04:50,190 --> 00:04:52,470
ხე საწყისი ადრე შეიძლება უფრო დაბალანსებული,

108
00:04:52,470 --> 00:04:54,140
მოსწონს ეს.

109
00:04:54,140 --> 00:04:57,980
ახლა, ეძებს up ნებისმიერი მნიშვნელობა იღებს, უმეტეს, 3 ნაბიჯები.

110
00:04:57,980 --> 00:04:59,460
ეს ხე არის დაბალანსებული,

111
00:04:59,460 --> 00:05:01,190
მნიშვნელობა, რომელიც აქვს მინიმალური სიღრმე

112
00:05:01,190 --> 00:05:03,680
შედარებით ხმების კვანძების.

113
00:05:03,680 --> 00:05:06,300
>> ვეძებთ ღირებულების დაბალანსებული ორობითი ძებნა tree

114
00:05:06,300 --> 00:05:09,540
მსგავსია ორობითი ძიება დახარისხებული მასივი.

115
00:05:09,540 --> 00:05:12,290
რეალურად, თუ ჩვენ არ გვჭირდება ჩასასმელად ან წაშლა ნივთები,

116
00:05:12,290 --> 00:05:15,150
ისინი იქცევიან ზუსტად ისე.

117
00:05:15,150 --> 00:05:17,600
თუმცა, ხის სტრუქტურაში უკეთესია

118
00:05:17,600 --> 00:05:19,530
გატარება insertions და წაშლებს

119
00:05:20,360 --> 00:05:22,670
>> ჩემი სახელი არის Bannus ვან დერ Kloot.

120
00:05:22,670 --> 00:05:24,030
ეს არის CS50.