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
>> A عقدة طرفية واحد هو أن ليس لديها أي الأطفال

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
هنا وهو الباحث، على الرغم من أنه يمكن أن يكون أي شيء.

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 (سجل ن) مرة.

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 فان دير Kloot.

120
00:05:22,670 --> 00:05:24,030
هذا هو CS50.