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
سی میں ایک بائنری درخت کی نوڈ کے struct ہے

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
ہے کسی اور درخت کی جڑ، قرار دیا '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
>> ایک بائنری تلاش درخت میں

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
ہم ڑیلی عدم مساوات یا تو ان میں سے تبدیل کر سکتے ہیں،

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 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
ہم جڑ میں شروع ہو جاتے ہیں.

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
یہ لوپ نیچے درخت جاری رہے گا

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 سے شروع ہونے والے درخت iterate،

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 (ن) کے ہے.

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 ہے.