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
>> بیایید می گویند که ما در حال شروع با مادر بزرگ خود، آلیس.

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
عموی خود، دیو، عمه، خاله، حوا، و پدر خود، فرد است.

9
00:00:26,730 --> 00:00:28,750
شما تنها فرزند فرد.

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
زمان نگاه کردن فوق العاده، اگر داده ها درخت طبقه بندی شده اند.

18
00:00:50,010 --> 00:00:53,850
>> ما می توانیم که در اینجا استفاده نمی کنند، اما ما به عنوان مثال از این به زودی را ببینید.

19
00:00:53,850 --> 00:00:56,150
هر فرد با یک گره در درخت نشان داده شده است.

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
گره آلیس دارای 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
بر روی لبه در خارج از درخت است.

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
در اینجا این است که ساختار یک گره از یک درخت دودویی در 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
>> درخت جستجوی دودویی

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
ریشه درخت دیگری به نام "زیر درخت.

47
00:02:04,960 --> 00:02:07,090
در اینجا، ریشه درخت 6 است،

48
00:02:07,090 --> 00:02:09,860
و کودک آن، 2، ریشه درخت است.

49
00:02:09,860 --> 00:02:11,870
>> در درخت جستجوی دودویی

50
00:02:11,870 --> 00:02:15,790
تمام ارزش یک گره راست زیر درخت

51
00:02:15,790 --> 00:02:18,690
بیشتر از مقدار گره است. در اینجا: 6.

52
00:02:18,690 --> 00:02:22,640
خوب، ارزش ها در زیر درخت چپ گره

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
ما می توانید تغییر دهید یا از آن به نابرابری شل،

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
این درخت یک درخت جستجوی دودویی

59
00:02:39,620 --> 00:02:41,540
چرا که آن را به پیروی از این قوانین است.

60
00:02:42,320 --> 00:02:46,020
>> این است که چگونه آن را نگاه اگر ما تمام گره به ساختمانها C تبدیل.

61
00:02:46,880 --> 00:02:48,410
توجه داشته باشید که اگر کودک از دست رفته است،

62
00:02:48,410 --> 00:02:50,340
اشاره گر تهی است.

63
00:02:50,340 --> 00:02:53,270
چگونه می توانم چک کنید و ببینید اگر 7 در درخت است؟

64
00:02:53,270 --> 00:02:55,020
ما در ریشه شروع می شود.

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
اشاره گر تهی است.

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
در سمت چپ و یا راست را بررسی کنید که زیر درخت است.

81
00:03:38,990 --> 00:03:41,160
این حلقه ادامه خواهد داد درخت

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
ما تکرار پایین درخت شروع از 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
به این معنی که درج، حذف و جستجو

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
ما باید به گذشتن از هر گره است.

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
به این ترتیب، درج، حذف و جستجو

106
00:04:46,370 --> 00:04:50,190
می کنند، در بدترین حالت O (log 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
در حال حاضر، به دنبال هر مقدار طول می کشد، در اکثر، 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
>> در حال جستجو برای یک مقدار در یک درخت دودویی جستجو متوازن

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
برای درج حمل و نقل و حذف

119
00:05:20,360 --> 00:05:22,670
>> نام من Bannus ون der Kloot است.

120
00:05:22,670 --> 00:05:24,030
این CS50 است.