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
>> এটি কিভাবে এটা যদি আমরা সি structs মধ্যে সমস্ত নোড পরিণত দেখাবে.

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
আমরা 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
নাল পয়েন্টার হয়.

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 থেকে শুরু পুনরুক্তি ডাউন,

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 (n log-) সময়, নাহয়, নিতে হবে.

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
জন্য হ্যান্ডলিং insertions এবং মুছে দেওয়া

119
00:05:20,360 --> 00:05:22,670
>> আমার নাম Bannus Van Der Kloot.

120
00:05:22,670 --> 00:05:24,030
এটি CS50.