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, एक सबट्री की जड़ है.

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
हम जड़ में शुरू करते हैं.

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
में सबसे खराब, हे (लॉग एन) समय लग जाएगा.

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 है.