در این مطلب، ویدئو درختان جستجوی باینری در پایتون: مقدمه – درج و جستجو با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,060 –> 00:00:01,650
در این ویدیو ما ساختار
2
00:00:01,650 –> 00:00:03,659
داده درخت جستجوی باینری را بررسی خواهیم کرد
3
00:00:03,659 –> 00:00:05,609
و توصیه میکنم اگر
4
00:00:05,609 –> 00:00:08,010
این مجموعه را
5
00:00:08,010 –> 00:00:10,530
در این کانال روی درختهای باینری ندیدهاید، حداقل اولین
6
00:00:10,530 –> 00:00:12,120
ویدیوی آن سری را به شما توصیه میکنم.
7
00:00:12,120 –> 00:00:14,370
ابتدا اولین ویدیو را تماشا کنید،
8
00:00:14,370 –> 00:00:15,780
زیرا در آن ویدئو، من
9
00:00:15,780 –> 00:00:16,859
قصد دارم بسیاری از اصطلاحات کلی را
10
00:00:16,859 –> 00:00:19,500
که وقتی
11
00:00:19,500 –> 00:00:21,420
به ساختارهای داده درختی نگاه میکند، مانند
12
00:00:21,420 –> 00:00:24,150
ریشه چیست،
13
00:00:24,150 –> 00:00:25,740
مرور میکنم. با
14
00:00:25,740 –> 00:00:27,240
آن نوع اصطلاحات آشنا هستید، سپس می
15
00:00:27,240 –> 00:00:28,619
توانید از تماشای آن ویدیو صرف نظر کنید و اگر این مفاهیم برای شما جدید است، می
16
00:00:28,619 –> 00:00:30,269
توانید به ادامه این ویدیوی درخت جستجوی دودویی ادامه دهید
17
00:00:30,269 –> 00:00:32,250
18
00:00:32,250 –> 00:00:33,239
، توصیه می کنم
19
00:00:33,239 –> 00:00:35,730
قبل از تماشای این ویدیوی درخت جستجوی باینری، ابتدا آن ویدیو را تماشا کنید.
20
00:00:35,730 –> 00:00:38,160
با این گفته، اجازه
21
00:00:38,160 –> 00:00:40,050
دهید ادامه دهم و تعریف کنم که
22
00:00:40,050 –> 00:00:41,879
درخت جستجوی باینری چیست، بنابراین دوباره با فرض اینکه
23
00:00:41,879 –> 00:00:43,739
ویدیوی درخت باینری را دیدهاید یا
24
00:00:43,739 –> 00:00:45,570
میدانید درخت باینری چیست،
25
00:00:45,570 –> 00:00:47,250
درخت جستجوی باینری واقعاً فقط یک ساختار داده درختی
26
00:00:47,250 –> 00:00:49,410
است که ea گره ch حداکثر دو
27
00:00:49,410 –> 00:00:51,120
فرزند دارد، بنابراین اصطلاح
28
00:00:51,120 –> 00:00:52,949
دودویی از آن برای دو فرزند برای هر
29
00:00:52,949 –> 00:00:55,289
گره می آید و سپس ما به طور معمول به
30
00:00:55,289 –> 00:00:57,360
فرزندان هر گره به عنوان فرزند چپ و
31
00:00:57,360 –> 00:00:59,879
راست آن گره اشاره می کنیم، بنابراین این یکی فرزند چپ این گره است.
32
00:00:59,879 –> 00:01:01,859
گره متشکل
33
00:01:01,859 –> 00:01:04,379
از هشت و این گره با عنصر داده
34
00:01:04,379 –> 00:01:06,900
10 فرزند سمت راست این گره در اینجا است
35
00:01:06,900 –> 00:01:08,850
که در این مورد ریشه است، بنابراین
36
00:01:08,850 –> 00:01:10,260
تفاوت درخت جستجوی
37
00:01:10,260 –> 00:01:12,030
دودویی با درختان باینری این است که
38
00:01:12,030 –> 00:01:14,580
نوعی نظم بر روی گره ها اعمال می شود.
39
00:01:14,580 –> 00:01:16,290
عناصر موجود در هر یک از گره های
40
00:01:16,290 –> 00:01:18,750
درخت، بنابراین در این مورد داریم که هر یک
41
00:01:18,750 –> 00:01:21,060
از عناصر این درخت مرتب شده اند
42
00:01:21,060 –> 00:01:23,340
بنابراین به طور خاص ریشه در اینجا
43
00:01:23,340 –> 00:01:26,189
عنصر 8 دارد و سپس فرزند سمت چپ هر
44
00:01:26,189 –> 00:01:28,650
گره در این درخت کوچکتر از هر چیزی خواهد بود.
45
00:01:28,650 –> 00:01:30,450
مقداری که در این گره داریم و
46
00:01:30,450 –> 00:01:32,729
سپس فرزند سمت راست هر مقداری
47
00:01:32,729 –> 00:01:34,229
که در اینجا در این گره داریم
48
00:01:34,229 –> 00:01:36,720
بزرگتر خواهد بود، برای مثال این مقدار 8
49
00:01:36,720 –> 00:01:39,030
به سمت چپ است، ما 3 داریم که کمتر از 8 است
50
00:01:39,030 –> 00:01:41,070
و سپس 10 در سمت راست داریم
51
00:01:41,070 –> 00:01:42,780
که بزرگتر از 8 بنابراین این نوع
52
00:01:42,780 –> 00:01:45,149
الگو در سراسر درخت باقی می ماند،
53
00:01:45,149 –> 00:01:46,740
برای مثال اگر به این گره
54
00:01:46,740 –> 00:01:48,899
در اینجا نگاه کنیم که حاوی عنصر داده 3 است
55
00:01:48,899 –> 00:01:50,939
، گره های سمت چپ 3
56
00:01:50,939 –> 00:01:53,640
فرزند سمت چپ 3 است 1 که کمتر از 3 است و
57
00:01:53,640 –> 00:01:55,740
سپس فرزند نیز به همین ترتیب است. در سمت راست
58
00:01:55,740 –> 00:01:58,649
3 عنصر 6 است و آن بزرگتر از
59
00:01:58,649 –> 00:02:01,320
3 است، بنابراین این الگو دوباره
60
00:02:01,320 –> 00:02:02,610
در سراسر آن درخت باقی می ماند و این همان چیزی است که
61
00:02:02,610 –> 00:02:04,320
این درخت خاص را به یک درخت جستجوی دودویی تبدیل
62
00:02:04,320 –> 00:02:07,320
می کند، بنابراین بیایید نگاهی به
63
00:02:07,320 –> 00:02:09,119
درج در یک درخت جستجوی دودویی
64
00:02:09,119 –> 00:02:09,989
بیندازیم. دوباره به یک مثال
65
00:02:09,989 –> 00:02:11,879
نگاه میکنیم، فرض میکنیم
66
00:02:11,879 –> 00:02:13,510
که این آرایه از
67
00:02:13,510 –> 00:02:15,580
آرایهای از اعداد را داریم که در این مورد
68
00:02:15,580 –> 00:02:17,290
به ما داده شده است و کاری که میخواهیم انجام دهیم این است که
69
00:02:17,290 –> 00:02:18,819
میخواهیم هر یک از این عناصر را بگیریم و
70
00:02:18,819 –> 00:02:21,040
از
71
00:02:21,040 –> 00:02:22,989
عناصری که به ما داده شده است، یک درخت جستجوی دودویی تشکیل دهیم، بنابراین کاری که میتوانیم
72
00:02:22,989 –> 00:02:24,430
انجام دهیم این است که میتوانیم شروع کنیم، فرض کنید این
73
00:02:24,430 –> 00:02:26,170
ابتدای آرایه است و
74
00:02:26,170 –> 00:02:27,610
از ابتدا شروع میکنیم و تمام راه را
75
00:02:27,610 –> 00:02:29,590
تا انتها پردازش میکنیم، بنابراین نگاه میکنیم. در اولین
76
00:02:29,590 –> 00:02:32,110
عنصر که 8 است و درخت ما سمت راست است
77
00:02:32,110 –> 00:02:33,879
اکنون خالی است، هیچ عنصری در درخت ما وجود ندارد،
78
00:02:33,879 –> 00:02:36,879
بنابراین این 8 به طور پیشفرض
79
00:02:36,879 –> 00:02:38,980
ریشه درخت ما خواهد بود، بنابراین من فقط میخواهم
80
00:02:38,980 –> 00:02:40,810
آن را در اینجا با این دایره
81
00:02:40,810 –> 00:02:44,200
که گره ریشه این درخت است نشان دهم، بنابراین
82
00:02:44,200 –> 00:02:45,790
تمام چیزی که نیاز داریم به آن نیاز داریم. برای انجام این کار در این مورد، بنابراین اجازه دهید
83
00:02:45,790 –> 00:02:47,440
به عنصر بعدی در آرایه ای
84
00:02:47,440 –> 00:02:48,940
که می خواهیم پردازش کنیم که 3 است
85
00:02:48,940 –> 00:02:51,310
و روشی که در درخت جستجوی دودویی وارد می کنیم
86
00:02:51,310 –> 00:02:52,930
تا مطمئن شویم
87
00:02:52,930 –> 00:02:55,959
ترتیب حفظ شده است، این است که از root
88
00:02:55,959 –> 00:02:58,359
و ما بررسی می کنیم عنصری که
89
00:02:58,359 –> 00:03:00,549
می خواهیم درج کنیم آیا بزرگتر از این
90
00:03:00,549 –> 00:03:02,409
عنصر در اینجا است یا کمتر از آن است و سپس
91
00:03:02,409 –> 00:03:03,489
ما فقط به پرسیدن این سؤالات
92
00:03:03,489 –> 00:03:05,319
ادامه می دهیم تا جایی که مکان مناسب برای
93
00:03:05,319 –> 00:03:08,290
قرار دادن عنصر داده پیدا کنیم، بنابراین در این مورد ما
94
00:03:08,290 –> 00:03:11,319
داریم 3 به این ریشه 8 نگاه می کنیم پس 8
95
00:03:11,319 –> 00:03:13,450
بزرگتر از 3 است بنابراین می دانیم که هر
96
00:03:13,450 –> 00:03:16,180
عنصری که قرار است کمتر از 3 باشد
97
00:03:16,180 –> 00:03:18,190
متأسفانه کمتر از 8 در این مورد که
98
00:03:18,190 –> 00:03:20,139
3 است باید به سمت چپ این
99
00:03:20,139 –> 00:03:22,239
گره با 8 برود. کاری که ما انجام میدهیم این است که 3 را بیرون میآوریم
100
00:03:22,239 –> 00:03:24,970
و به سمت چپ این گره
101
00:03:24,970 –> 00:03:27,220
در اینجا میرود، بنابراین این اکنون le است ft فرزند
102
00:03:27,220 –> 00:03:30,790
این گره ریشه 8، بنابراین ما یک الگوی مشابه را
103
00:03:30,790 –> 00:03:32,470
با عناصر باقی مانده دنبال می کنیم،
104
00:03:32,470 –> 00:03:34,540
بنابراین عنصر بعدی که داریم این
105
00:03:34,540 –> 00:03:36,730
عنصر 10 است، ریشه را از اینجا شروع می کنیم و می
106
00:03:36,730 –> 00:03:40,060
خواهیم 10 کمتر یا بزرگتر از این
107
00:03:40,060 –> 00:03:43,120
عنصر در اینجا باشد، بنابراین 10 است. بزرگتر از 8 بنابراین
108
00:03:43,120 –> 00:03:45,040
می دانیم که باید سمت راست را بررسی کنیم
109
00:03:45,040 –> 00:03:46,930
، هیچ گره ای در سمت راست وجود ندارد، بنابراین
110
00:03:46,930 –> 00:03:48,400
کاری که انجام می دهیم این است که ادامه می دهیم و یک گره ایجاد می کنیم و اینجاست
111
00:03:48,400 –> 00:03:50,709
که این گره 10 را قرار می دهیم،
112
00:03:50,709 –> 00:03:54,220
بنابراین 10 اکنون به عنوان فرزند مناسب زندگی می کند.
113
00:03:54,220 –> 00:03:56,980
این گره ریشه را دنبال می کنیم
114
00:03:56,980 –> 00:03:59,019
، ما یکی را در اینجا داریم، بنابراین از اینجا شروع می کنیم در
115
00:03:59,019 –> 00:04:01,000
ریشه که می پرسیم یک کوچکتر یا بزرگتر
116
00:04:01,000 –> 00:04:03,760
از 8 است، بنابراین 1 کوچکتر از 8 است، بنابراین
117
00:04:03,760 –> 00:04:05,650
به سمت چپ حرکت می کنیم و می بینیم که یک
118
00:04:05,650 –> 00:04:07,329
گره در اینجا وجود دارد، بنابراین پرسیدیم همان سوالی
119
00:04:07,329 –> 00:04:09,879
که پرسیدیم یک بزرگتر یا کمتر
120
00:04:09,879 –> 00:04:11,409
از این عنصر است که در این گره در اینجا 3 ذخیره شده است،
121
00:04:11,409 –> 00:04:14,139
بنابراین کمتر است، بنابراین به سمت چپ می
122
00:04:14,139 –> 00:04:16,988
رویم و می بینیم که هیچ گره ای در اینجا وجود ندارد، بنابراین
123
00:04:16,988 –> 00:04:18,940
پیش می رویم و یک گره ایجاد می کنیم که همان
124
00:04:18,940 –> 00:04:21,310
گره ای است که این کار را انجام می دهد. ذخیره 1 بنابراین جایی است که 1
125
00:04:21,310 –> 00:04:23,080
می رود و سپس ما همین کار را
126
00:04:23,080 –> 00:04:25,570
برای 6 شکل ou انجام می دهیم t جایی که 6 می رود ما از 8 شروع می کنیم.
127
00:04:25,570 –> 00:04:27,460
6 کمتر از 8 است، بنابراین
128
00:04:27,460 –> 00:04:29,800
به سمت چپ حرکت می کنیم شش بزرگتر از
129
00:04:29,800 –> 00:04:31,630
سه است، بنابراین به سمت راست حرکت می کنیم، متوجه می شویم
130
00:04:31,630 –> 00:04:34,150
که چیزی در آنجا وجود ندارد، بنابراین شش به سمت راست می رود
131
00:04:34,150 –> 00:04:37,060
، بنابراین ما اینجا فقط درخت جستجوی باینری خود را داریم.
132
00:04:37,060 –> 00:04:39,430
اجازه دهید
133
00:04:39,430 –> 00:04:44,130
مثال دیگری از درج را مرور کنم که در آن
134
00:04:44,130 –> 00:04:46,389
عناصر موجود در آرایه ای که
135
00:04:46,389 –> 00:04:49,150
داده شده به ترتیب مرتب شده معکوس به ما داده می شود،
136
00:04:49,150 –> 00:04:51,190
بنابراین ما همان عناصری را داریم که قبلا داشتیم،
137
00:04:51,190 –> 00:04:53,259
فقط این بار آنها را به
138
00:04:53,259 –> 00:04:54,789
ترتیب مرتب شده معکوس داریم، بنابراین ده هشت شش
139
00:04:54,789 –> 00:04:57,009
سه و یکی پس بیایید ببینیم این
140
00:04:57,009 –> 00:04:59,319
درخت چگونه به نظر می رسد اگر بخواهیم
141
00:04:59,319 –> 00:05:01,229
از این آرایه به این شکل یک درخت تشکیل
142
00:05:01,229 –> 00:05:03,520
دهیم، بنابراین کاری که انجام می دهیم این است که دوباره در
143
00:05:03,520 –> 00:05:05,349
ابتدای لیست شروع کنیم و ده
144
00:05:05,349 –> 00:05:07,449
عنصر را برداریم، این تنها عنصر در درخت ما است. به طوری
145
00:05:07,449 –> 00:05:09,580
که فقط تبدیل به گره ریشه
146
00:05:09,580 –> 00:05:12,070
درخت ما می شود، بنابراین در اینجا ده است، اکنون هشت را بررسی می کنیم،
147
00:05:12,070 –> 00:05:14,590
بنابراین هشت، به کجا
148
00:05:14,590 –> 00:05:15,970
باید در این درخت برود، بنابراین از
149
00:05:15,970 –> 00:05:18,220
ساعت ده هشت شروع می کنیم، کمتر از ده است، بنابراین
150
00:05:18,220 –> 00:05:19,720
بررسی می کنیم که آیا چیزی برای این درخت وجود دارد یا خیر. چپ
151
00:05:19,720 –> 00:05:21,909
چیزی وجود ندارد بنابراین ما به جلو می رویم و
152
00:05:21,909 –> 00:05:24,909
هشت را در سمت چپ ده قرار می دهیم، بنابراین
153
00:05:24,909 –> 00:05:26,800
همان کار را برای شش انجام می دهیم و شش را نیز
154
00:05:26,800 –> 00:05:29,650
بیرون می آوریم، می پرسیم خوب خوب 6 کمتر از 10 است
155
00:05:29,650 –> 00:05:32,349
6 کمتر از 8 است، هیچ چیزی در
156
00:05:32,349 –> 00:05:33,909
سمت چپ 8 نیست، بنابراین این همان جایی است که می رود و
157
00:05:33,909 –> 00:05:35,560
شما میتوانید ببینید که این به کجا میرود،
158
00:05:35,560 –> 00:05:37,750
اساساً فهرستی
159
00:05:37,750 –> 00:05:40,270
مانند ساختار داده دریافت خواهید کرد، بنابراین کل هدف
160
00:05:40,270 –> 00:05:41,979
از کل مزیت درخت جستجوی دودویی
161
00:05:41,979 –> 00:05:44,590
، ساختار آن درخت و
162
00:05:44,590 –> 00:05:46,479
163
00:05:46,479 –> 00:05:48,280
بهطور خاص آن ساختار درخت است. به شما اجازه دهید آنچه را که می بینیم
164
00:05:48,280 –> 00:05:50,259
کمی جستجو کنید، به
165
00:05:50,259 –> 00:05:52,080
شما این امکان را می دهد که اساساً
166
00:05:52,080 –> 00:05:54,699
بخش های مختلف فضای جستجو را حذف
167
00:05:54,699 –> 00:05:56,680
کنید تا عنصری را در درخت پیدا کنید و اگر
168
00:05:56,680 –> 00:05:58,509
درخت شما به این شکل است، چیز زیادی وجود ندارد،
169
00:05:58,509 –> 00:05:59,800
می توانید اساساً شما را حذف کنید.
170
00:05:59,800 –> 00:06:01,180
مزایایی
171
00:06:01,180 –> 00:06:03,310
که در یک لیست خواهید داشت، بنابراین اگر می خواهید
172
00:06:03,310 –> 00:06:06,370
عنصری را در این درخت در اینجا جستجو کنید،
173
00:06:06,370 –> 00:06:09,370
174
00:06:09,370 –> 00:06:11,530
در بدترین حالت باید تمام گره های این درخت را طی کنید،
175
00:06:11,530 –> 00:06:13,000
برای مثال اگر می خواهید
176
00:06:13,000 –> 00:06:14,919
پیدا کنید یکی که باید از آن شروع کنید در پایان
177
00:06:14,919 –> 00:06:16,630
اینجا چیزی به سمت راست وجود ندارد، بنابراین
178
00:06:16,630 –> 00:06:18,159
باید به سمت چپ بروید، یکی کمتر
179
00:06:18,159 –> 00:06:20,110
از 8 است 1 کمتر از 6 است 1 کمتر از 3 است
180
00:06:20,110 –> 00:06:22,060
و سپس در نهایت به اینجا می رسید،
181
00:06:22,060 –> 00:06:23,710
اما اگر ساختاری شبیه به این
182
00:06:23,710 –> 00:06:26,169
داشتید، پس چه چیزی می توانید با
183
00:06:26,169 –> 00:06:27,880
استفاده از ساختار درخت جستجوی دودویی این کار را انجام دهید این
184
00:06:27,880 –> 00:06:29,710
است که اساساً می توانید
185
00:06:29,710 –> 00:06:31,210
تعداد عملیاتی
186
00:06:31,210 –> 00:06:32,830
را که برای یافتن آن عنصر 1 باید انجام دهید
187
00:06:32,830 –> 00:06:34,360
به نصف کاهش دهید و ما به
188
00:06:34,360 –> 00:06:36,729
طور خاص خواهیم دید که وقتی جستجو را پوشش می دهیم چگونه به نظر می رسد.
189
00:06:36,729 –> 00:06:38,949
بنابراین این
190
00:06:38,949 –> 00:06:40,360
نوعی ساختار است که ما می خواهیم از
191
00:06:40,360 –> 00:06:41,439
192
00:06:41,439 –> 00:06:43,239
آن اجتناب کنیم و خارج از محدوده این ویدیو است، اما
193
00:06:43,239 –> 00:06:45,069
اگر می خواهید اگر کنجکاو هستید که چگونه
194
00:06:45,069 –> 00:06:46,959
می توانید از گرفتن
195
00:06:46,959 –> 00:06:49,059
ساختار از خواندن داده ها و تشکیل
196
00:06:49,059 –> 00:06:50,979
درخت جستجوی باینری جلوگیری کنید. از این پس
197
00:06:50,979 –> 00:06:52,089
میتوانید به چیزی به نام درخت AVL نگاه کنید،
198
00:06:52,089 –> 00:06:55,089
بنابراین
199
00:06:55,089 –> 00:06:56,830
گرهها را بهگونهای متعادل میکند که
200
00:06:56,830 –> 00:06:58,769
همچنان ساختاری را دریافت میکنید که برای ساختار داده
201
00:06:58,769 –> 00:07:00,999
درخت جستجوی باینری مفید
202
00:07:00,999 –> 00:07:03,459
است و
203
00:07:03,459 –> 00:07:05,169
دوباره خواهد بود. فراتر دامنه این ویدیو،
204
00:07:05,169 –> 00:07:07,659
بنابراین شما می توانید مقاله ویکی پدیا
205
00:07:07,659 –> 00:07:09,729
را در مورد آن جستجو کنید که ممکن است در
206
00:07:09,729 –> 00:07:11,800
یک ویدیوی آینده به آن موضوع بپردازیم، بنابراین بیایید نگاهی بیندازیم
207
00:07:11,800 –> 00:07:13,569
که چگونه می توانیم یک عنصر را در
208
00:07:13,569 –> 00:07:15,550
درخت جستجوی باینری جستجو کنیم، بنابراین بیایید فرض کنیم که
209
00:07:15,550 –> 00:07:17,559
این موضوع ماست. درخت در اینجا، بنابراین
210
00:07:17,559 –> 00:07:19,779
چند عنصر دیگر در این درخت وجود دارد و در واقع
211
00:07:19,779 –> 00:07:22,059
من جلوتر رفتهام و گرهها را پر کردهام،
212
00:07:22,059 –> 00:07:24,610
بنابراین هر گره در این درخت دارای
213
00:07:24,610 –> 00:07:26,619
دو فرزند است به استثنای
214
00:07:26,619 –> 00:07:28,179
برگها، بنابراین این چیزی است که به عنوان
215
00:07:28,179 –> 00:07:30,459
جستجوی دودویی کامل شناخته میشود. درخت، بنابراین ما
216
00:07:30,459 –> 00:07:32,349
217
00:07:32,349 –> 00:07:34,659
در ویدیوی درخت دودویی انواع مختلف درخت را در درختان پوشاندیم و یکی
218
00:07:34,659 –> 00:07:35,919
از انواع درختانی که پوشش دادیم
219
00:07:35,919 –> 00:07:37,569
یک درخت کامل بود، بنابراین اگر
220
00:07:37,569 –> 00:07:39,579
میخواهید دوباره در مورد آن تجدید نظر کنید، فقط
221
00:07:39,579 –> 00:07:41,529
با آن ویدیو مشورت کنید، بنابراین بیایید بگوییم که
222
00:07:41,529 –> 00:07:43,029
ما با توجه به این درخت، ما میخواهیم
223
00:07:43,029 –> 00:07:45,339
عنصری را در این درخت جستجوی دودویی جستجو
224
00:07:45,339 –> 00:07:47,259
کنیم، بنابراین میخواهیم یکی را در
225
00:07:47,259 –> 00:07:49,360
این مورد جستجو کنیم، بنابراین کاری که انجام میدهیم این است که بدانیم
226
00:07:49,360 –> 00:07:50,829
درخت جستجوی دودویی نظم خاصی
227
00:07:50,829 –> 00:07:53,139
بر آن تحمیل شده است، بنابراین آنچه میتوانیم انجام دهید این است
228
00:07:53,139 –> 00:07:55,439
که از ریشه شروع کنیم و سپس
229
00:07:55,439 –> 00:07:57,429
سؤالات بعدی را می پرسیم
230
00:07:57,429 –> 00:07:58,959
عنصری است که به دنبال آن
231
00:07:58,959 –> 00:08:00,550
بزرگتر یا کمتر از مقداری هستیم که در
232
00:08:00,550 –> 00:08:02,919
حال حاضر روی آن قرار داریم، بنابراین می دانیم که 1 کمتر
233
00:08:02,919 –> 00:08:05,439
از 8 است بنابراین می دانیم که 1 اگر
234
00:08:05,439 –> 00:08:06,909
در درخت وجود دارد. اصلاً قرار است
235
00:08:06,909 –> 00:08:09,550
در این قسمت از درخت باشد، بنابراین ما به جلو می رویم
236
00:08:09,550 –> 00:08:11,759
و به سمت فرزند سمت چپ
237
00:08:11,759 –> 00:08:14,860
درخت می رویم و متوجه خواهید شد که همه
238
00:08:14,860 –> 00:08:17,529
این گره های قرمز اساساً
239
00:08:17,529 –> 00:08:18,729
فضای جستجویی را نشان می دهند که ما در حال حذف
240
00:08:18,729 –> 00:08:22,419
آن هستیم تا بدانیم. که گره 1، گره ای که
241
00:08:22,419 –> 00:08:24,519
حاوی عنصر داده 1 است، نمی تواند در
242
00:08:24,519 –> 00:08:26,529
هیچ یک از این گره ها باشد، بنابراین ما به نوعی
243
00:08:26,529 –> 00:08:28,209
همه
244
00:08:28,209 –> 00:08:29,949
عناصر این درخت را حذف کردیم و اگر درخت به
245
00:08:29,949 –> 00:08:31,839
خصوص بزرگ باشد، شما
246
00:08:31,839 –> 00:08:34,568
یک تکه بزرگ از آن را حذف می کنید. درخت، بنابراین
247
00:08:34,568 –> 00:08:35,799
ما به این ترتیب ادامه می دهیم، ما
248
00:08:35,799 –> 00:08:37,448
در 3 هستیم، ما هنوز در جستجوی یکی هستیم و
249
00:08:37,448 –> 00:08:39,818
بنابراین می پرسیم 1 کوچکتر یا بزرگتر از
250
00:08:39,818 –> 00:08:42,849
3 چاه 1 کمتر از 3 است، بنابراین دوباره
251
00:08:42,849 –> 00:08:44,649
پایه جستجوی خود را قطع می کنیم. و ما به سمت چپ می
252
00:08:44,649 –> 00:08:46,750
رویم زیرا می دانیم که 1 خواهد بود اگر
253
00:08:46,750 –> 00:08:49,389
اصلاً در سمت چپ 3 وجود داشته باشد پس h e
254
00:08:49,389 –> 00:08:50,649
به سمت چپ حرکت می کند و در این مورد ما
255
00:08:50,649 –> 00:08:53,050
یکی را پیدا می کنیم و این
256
00:08:53,050 –> 00:08:55,270
پایان جستجو است، پس اگر می
257
00:08:55,270 –> 00:08:56,860
خواستیم عنصر یک را جستجو
258
00:08:56,860 –> 00:08:58,900
کنیم، اگر درختی به این شکل داشتیم، در واقع بیشتر شبیه یک لیست
259
00:08:58,900 –> 00:09:00,850
است. در
260
00:09:00,850 –> 00:09:03,070
این نوع درخت کاری که در نهایت
261
00:09:03,070 –> 00:09:04,690
انجام می دهیم این است که از ریشه شروع می کنیم و
262
00:09:04,690 –> 00:09:06,700
سپس می گوییم خوب یکی کمتر از
263
00:09:06,700 –> 00:09:08,410
ده است پس ادامه دهید و به سمت چپ بروید
264
00:09:08,410 –> 00:09:10,930
یکی کمتر از هشت است به چپ بروید به
265
00:09:10,930 –> 00:09:12,760
سمت چپ و سپس در نهایت به یکی می رسیم
266
00:09:12,760 –> 00:09:15,520
اما این عملیات
267
00:09:15,520 –> 00:09:18,400
زمان خطی را می گیرد که در آن
268
00:09:18,400 –> 00:09:20,320
عملیات خطی با توجه به
269
00:09:20,320 –> 00:09:21,640
اندازه درخت یا تعداد گره های
270
00:09:21,640 –> 00:09:23,380
درخت است و این
271
00:09:23,380 –> 00:09:25,360
چیزی بهتر از پیمایش به ما نمی دهد. یک لیست
272
00:09:25,360 –> 00:09:27,520
بنابراین فقط به نوعی خلاصه است اینجا
273
00:09:27,520 –> 00:09:30,250
پیچیدگی زمانی عملیات مختلفی است
274
00:09:30,250 –> 00:09:31,810
که می توانید روی
275
00:09:31,810 –> 00:09:34,540
درخت جستجوی باینری انجام دهید، بنابراین اجازه دهید
276
00:09:34,540 –> 00:09:37,000
هر یک از اینها را یکی یکی مرور کنیم تا اگر
277
00:09:37,000 –> 00:09:39,070
می خواهید n چیز را ذخیره کنید، فرض کنید n را ذخیره کنید.
278
00:09:39,070 –> 00:09:40,810
تعداد گره هایی که می خواهید در
279
00:09:40,810 –> 00:09:42,910
این جستجوی باینری ذخیره کنید البته
280
00:09:42,910 –> 00:09:44,770
بدترین حالت در حالت متوسط این است که شما مجبور خواهید بود n گ
281
00:09:44,770 –> 00:09:46,870
ه را
282
00:09:46,870 –> 00:09:48,520
خصیص دهید، اگ
283
00:09:48,520 –> 00:09:50,620
می خواهید n چیز را ذخیره کنید، واقعاً نمی توانید با اختصاص کمتر از n گره کنار بیایید، بن
284
00:09:50,620 –> 00:09:52,090
براین میانگین و بدترین حالت ممکن است به شم
285
00:09:52,090 –> 00:09:54,730
بدهد. ما دیدیم
286
00:09:54,730 –> 00:09:56,770
که بهترین حالت این است که شما یک
287
00:09:56,770 –> 00:09:58,690
ساختار درختی داشته باشید که شبیه این
288
00:09:58,690 –> 00:10:00,430
نوع درخت جستجوی دودویی کامل است و
289
00:10:00,430 –> 00:10:01,630
در صورتی که بخواهید
290
00:10:01,630 –> 00:10:02,560
عنصری را در آن درخت پیدا
291
00:10:02,560 –> 00:10:04,660
کنید، متعاقباً حذف نیمی از
292
00:10:04,660 –> 00:10:06,820
فضای جستجوی خود در هر حرکت
293
00:10:06,820 –> 00:10:08,770
به گره بعدی، به طوری که به نوعی
294
00:10:08,770 –> 00:10:11,050
نمایی معکوس است، یکی از راه های
295
00:10:11,050 –> 00:10:12,490
فکر کردن به آن است و به
296
00:10:12,490 –> 00:10:14,620
شما زمان جستجوی لگاریتمی می دهد تا
297
00:10:14,620 –> 00:10:17,110
زمانی که یک گره را پیدا کنید. درختی از
298
00:10:17,110 –> 00:10:19,390
این شکل log از n خواهد بود که
299
00:10:19,390 –> 00:10:21,010
دوباره n تعداد گره های
300
00:10:21,010 –> 00:10:22,840
درخت شما است البته شما می توانید یک درخت باینری داشته باشید
301
00:10:22,840 –> 00:10:24,880
که شبیه یک لیست است و در آن
302
00:10:24,880 –> 00:10:26,920
صورت بدترین سناریو
303
00:10:26,920 –> 00:10:29,860
یک Big خواهد بود. O از n بنابراین شامل
304
00:10:29,860 –> 00:10:31,840
عبور از هر عنصر می شود در
305
00:10:31,840 –> 00:10:33,550
لیست قبل از اینکه واقعاً در درخت
306
00:10:33,550 –> 00:10:35,050
هستید قبل از اینکه به عنصری که
307
00:10:35,050 –> 00:10:37,150
دنبالش هستید برسید، بنابراین یک
308
00:10:37,150 –> 00:10:39,130
نوع داستان مشابه در اینجا با درج وجود دارد، بنابراین اگر
309
00:10:39,130 –> 00:10:42,070
میخواهید در این درخت وارد کنید، بگویید پس
310
00:10:42,070 –> 00:10:44,070
تمام کاری که باید انجام دهید این است موقعیتی را پیدا کنید
311
00:10:44,070 –> 00:10:46,540
که گره خود را در آن درج کنید، بنابراین
312
00:10:46,540 –> 00:10:47,830
اگر می خواهید
313
00:10:47,830 –> 00:10:50,680
گره 0 را وارد کنید، می توانید از اینجا در ساعت 8 شروع کنید و
314
00:10:50,680 –> 00:10:53,140
این یک نوع ایده مشابه برای اینکه چرا
315
00:10:53,140 –> 00:10:55,720
زمان لگاریتمی برای جستجو است، همانطور
316
00:10:55,720 –> 00:10:58,030
که برای درج است. از
317
00:10:58,030 –> 00:11:00,610
اینجا شروع کنید 0 کمتر از 8 کمتر از 3 کوچکتر
318
00:11:00,610 –> 00:11:01,840
از 1 است و سپس در
319
00:11:01,840 –> 00:11:03,310
موقعیتی که می خواهید
320
00:11:03,310 –> 00:11:06,520
گره را با عنصر 0 قرار دهید پیدا کردید، در حالی که اگر
321
00:11:06,520 –> 00:11:08,200
ساختار درختی داشته باشید که شبیه به این است،
322
00:11:08,200 –> 00:11:08,740
جایی که می گوید
323
00:11:08,740 –> 00:11:10,450
در واقع بهتر از یک لیست و سپس
324
00:11:10,450 –> 00:11:11,680
مقدار زمانی که برای
325
00:11:11,680 –> 00:11:14,410
پیدا کردن مکان برای وارد کردن گره با صفر طول می کشد، شما
326
00:11:14,410 –> 00:11:16,480
را شامل می شود تا از هر یک
327
00:11:16,480 –> 00:11:17,950
از این گره ها عبور کنید و سپس در
328
00:11:17,950 –> 00:11:19,540
نهایت به اینجا می رسید که می دانید صفر
329
00:11:19,540 –> 00:11:21,190
به سمت چپ این گره می رود. عنصر
330
00:11:21,190 –> 00:11:23,680
با یک به طوری که در آن بزرگترین و
331
00:11:23,680 –> 00:11:25,390
با بدترین حالت از آن ناشی میشود و
332
00:11:25,390 –> 00:11:27,250
در نهایت حذفی
333
00:11:27,250 –> 00:11:28,690
که در این ویدیو به آن نپرداختهایم، اما
334
00:11:28,690 –> 00:11:30,970
در ویدیوی بعدی به آن خواهیم پرداخت.
335
00:11:30,970 –> 00:11:33,310
336
00:11:33,310 –> 00:11:36,880
N
337
00:11:36,880 –> 00:11:39,190
و n بسیار شبیه به چیزی است که برای
338
00:11:39,190 –> 00:11:41,470
جستجو و درج دیدیم، بنابراین اکنون
339
00:11:41,470 –> 00:11:42,730
که نوعی ایده از نحوه
340
00:11:42,730 –> 00:11:44,620
تشکیل درخت جستجوی دودویی چگونه ساختار آن
341
00:11:44,620 –> 00:11:46,779
چگونه عملیات جستجو و درج
342
00:11:46,779 –> 00:11:48,430
را انجام می دهد، به دست می آوریم.
343
00:11:48,430 –> 00:11:49,959
و به نحوه پیادهسازی این
344
00:11:49,959 –> 00:11:52,600
ساختار داده در پایتون نگاهی بیندازید، بنابراین اکنون که
345
00:11:52,600 –> 00:11:54,130
در ویرایشگر متن خود هستیم، میخواهیم
346
00:11:54,130 –> 00:11:56,440
347
00:11:56,440 –> 00:11:58,450
پیادهسازی درخت جستجوی باینری را در پایتون
348
00:11:58,450 –> 00:12:00,279
کدنویسی کنیم و همچنین کدنویسی میکنیم. توابع جستجو
349
00:12:00,279 –> 00:12:03,220
یا پیدا کردن و درج را نیز
350
00:12:03,220 –> 00:12:05,080
که در اسلایدها مرور کردیم و
351
00:12:05,080 –> 00:12:07,779
درست مانند اجرای پایتون درخت باینری
352
00:12:07,779 –> 00:12:09,760
اگر آن ویدیو را دیدید، ما
353
00:12:09,760 –> 00:12:12,130
دو کلاس داشتیم، یکی کلاسی برای
354
00:12:12,130 –> 00:12:13,870
اشیاء گره بود که در درخت ذخیره می شوند.
355
00:12:13,870 –> 00:12:16,270
و دیگری f است یا خود درخت، بنابراین
356
00:12:16,270 –> 00:12:18,160
ما در اینجا نیز از الگوی مشابهی برای
357
00:12:18,160 –> 00:12:20,560
این پیاده سازی پیروی می کنیم، بنابراین
358
00:12:20,560 –> 00:12:22,510
بیایید با ایجاد کلاس گره
359
00:12:22,510 –> 00:12:25,149
برای درخت جستجوی باینری شروع کنیم که
360
00:12:25,149 –> 00:12:27,370
این کلاس را node می نامیم و در
361
00:12:27,370 –> 00:12:29,709
سازنده این کلاس، خود به خود می گیرد. از آنجایی که
362
00:12:29,709 –> 00:12:32,260
این البته تابعی برای این کلاس
363
00:12:32,260 –> 00:12:34,480
و سپس عنصر داده ای است که
364
00:12:34,480 –> 00:12:36,730
برای این گره خاص ذخیره می شود، بنابراین به
365
00:12:36,730 –> 00:12:38,350
طور پیش فرض ابتدا آن را روی none تنظیم می
366
00:12:38,350 –> 00:12:41,079
کنیم، اما در برخی از ع