در این مطلب، ویدئو برنامه پایتون برای پیاده سازی درخت جستجوی باینری | برنامه 3 | عملیات جستجو با زیرنویس فارسی را برای دانلود قرار داده ام. شما میتوانید با پرداخت 15 هزار تومان ، این ویدیو به علاوه تمامی فیلم های سایت را دانلود کنید.اکثر فیلم های سایت به زبان انگلیسی می باشند. این ویدئو دارای زیرنویس فارسی ترجمه شده توسط هوش مصنوعی می باشد که میتوانید نمونه ای از آن را در قسمت پایانی این مطلب مشاهده کنید.
مدت زمان فیلم: 00:13:26
تصاویر این ویدئو:
قسمتی از زیرنویس این فیلم:
00:00:00,240 –> 00:00:02,240
سلام بچه ها و به کانال یوتیوب آکادمی amulya خوش آمدید
2
00:00:02,240 –> 00:00:03,840
3
00:00:03,840 –> 00:00:05,920
ما امروز در مورد
4
00:00:05,920 –> 00:00:07,759
پیاده سازی درخت جستجوی باینری در
5
00:00:07,759 –> 00:00:09,120
زبان برنامه نویسی پایتون بحث می
6
00:00:09,120 –> 00:00:11,599
کردیم در این آموزش خواهیم دید که آیا
7
00:00:11,599 –> 00:00:14,160
گره داده شده در درخت وجود دارد یا
8
00:00:14,160 –> 00:00:14,639
نه
9
00:00:14,639 –> 00:00:16,800
به عبارت دیگر در حال نوشتن متد
10
00:00:16,800 –> 00:00:18,800
برای جستجو هستیم. عملیات
11
00:00:18,800 –> 00:00:22,160
بنابراین در اینجا بعد از متد درج،
12
00:00:22,160 –> 00:00:24,800
من def را میگیرم و در اینجا
13
00:00:24,800 –> 00:00:25,760
نام متد را بهعنوان
14
00:00:25,760 –> 00:00:27,680
جستجو میگیرم، زیرا این
15
00:00:27,680 –> 00:00:29,359
متد را برای عملیات جستجو
16
00:00:29,359 –> 00:00:32,320
مینویسیم، نام متد را جستجو میکنم
17
00:00:32,320 –> 00:00:34,480
و در اینجا اولین پارامتر self خواهد بود
18
00:00:34,480 –> 00:00:36,000
که خود شی
19
00:00:36,000 –> 00:00:39,520
به دنبال آن داده است که
20
00:00:39,520 –> 00:00:41,920
اگر من بخواهم گره داده شده را جستجو کنم
21
00:00:41,920 –> 00:00:44,320
در درخت وجود دارد یا نه برای این
22
00:00:44,320 –> 00:00:47,360
ابتدا به داده های گره داده شده
23
00:00:47,360 –> 00:00:49,280
نیاز داریم، به همین دلیل است که در اینجا باید
24
00:00:49,280 –> 00:00:52,239
داده های گره را که می خواهم منتقل کنید. جستجو کنید
25
00:00:52,239 –> 00:00:54,719
و در داخل آن باید بدنه متد جستجو را تعریف کنیم،
26
00:00:54,719 –> 00:00:56,800
27
00:00:56,800 –> 00:00:59,600
بنابراین هنگام انجام عملیات جستجو
28
00:00:59,600 –> 00:01:01,199
ابتدا باید
29
00:01:01,199 –> 00:01:04,080
داده های گره داده شده را با داده
30
00:01:04,080 –> 00:01:04,799
های
31
00:01:04,799 –> 00:01:08,400
گره ریشه مقایسه کنیم، بنابراین ابتدا باید ببینید
32
00:01:08,400 –> 00:01:11,360
کلید گره ریشه قوسی که آیا برابر با
33
00:01:11,360 –> 00:01:12,720
داده های داده شده است،
34
00:01:12,720 –> 00:01:15,280
بنابراین در اینجا داده ها چیزی نیست جز داده های
35
00:01:15,280 –> 00:01:16,080
36
00:01:16,080 –> 00:01:18,479
گره که می خواهم جستجو کنم که
37
00:01:18,479 –> 00:01:19,600
آیا در
38
00:01:19,600 –> 00:01:22,960
درخت وجود دارد یا نه، بنابراین ابتدا باید
39
00:01:22,960 –> 00:01:26,479
کلید ریشه را با داده مقایسه کنم. درست است
40
00:01:26,479 –> 00:01:28,799
بنابراین به این معنی است که گره داده شده
41
00:01:28,799 –> 00:01:29,520
در درخت وجود دارد،
42
00:01:29,520 –> 00:01:32,479
بنابراین می توانید پیامی را چاپ کنید که اگر کلید ریشه برابر با داده داده شده باشد داده گره ها باشد، بنابراین می توانید پیامی را چاپ کنید که
43
00:01:32,479 –> 00:01:34,079
گره تشکیل شده است.
44
00:01:34,079 –> 00:01:37,040
45
00:01:37,040 –> 00:01:37,840
46
00:01:37,840 –> 00:01:40,400
47
00:01:40,400 –> 00:01:42,000
48
00:01:42,000 –> 00:01:45,280
میتوانم پیامی را چاپ کنم اگر نه،
49
00:01:45,280 –> 00:01:47,600
بعد باید بررسی کنم که دادهها
50
00:01:47,600 –> 00:01:49,680
از کلید ریشه کوچکتر است یا نه،
51
00:01:49,680 –> 00:01:51,759
اگر دادهها از کلید ریشه کوچکتر هستند،
52
00:01:51,759 –> 00:01:53,680
باید آن گره را در
53
00:01:53,680 –> 00:01:56,320
درخت فرعی سمت چپ جستجو کنم، و اگر دادهها
54
00:01:56,320 –> 00:01:57,920
از ریشه بزرگتر هستند. کلید، سپس باید
55
00:01:57,920 –> 00:01:59,759
در زیردرخت سمت راست جستجو کنم،
56
00:01:59,759 –> 00:02:03,600
بنابراین فقط بررسی کنید که دادهها کمتر از
57
00:02:03,600 –> 00:02:07,040
کلید ریشه هستند، اگر دادهها کمتر از کلید اصلی هستند،
58
00:02:07,040 –> 00:02:08,000
اگر درست است،
59
00:02:08,000 –> 00:02:10,800
در درخت فرعی سمت چپ جستجو کنید،
60
00:02:10,800 –> 00:02:13,120
این قانون درخت جستجوی باینری است که سمت
61
00:02:13,120 –> 00:02:15,200
راست گرهها با کلید کوچکتر
62
00:02:15,200 –> 00:02:17,040
در درخت فرعی سمت چپ o وجود خواهد داشت اگر گرههای
63
00:02:17,040 –> 00:02:17,760
کلید
64
00:02:17,760 –> 00:02:20,000
65
00:02:20,000 –> 00:02:21,440
ریشه با کلید بزرگتر از کلید اصلی در
66
00:02:21,440 –> 00:02:22,239
زیردرخت سمت راست
67
00:02:22,239 –> 00:02:24,000
وجود دارند، به همین دلیل است که
68
00:02:24,000 –> 00:02:25,520
اگر
69
00:02:25,520 –> 00:02:28,480
دادهها کمتر از کلید ریشه باشد، دادهها را با کلید نقطه ریشه مقایسه میکنیم،
70
00:02:28,480 –> 00:02:30,319
سپس در زیردرخت سمت چپ جستجو میکنیم. درخت
71
00:02:30,319 –> 00:02:33,840
else در زیردرخت سمت راست جستجو کنید اگر
72
00:02:33,840 –> 00:02:35,599
دادهها کمتر از کلید ریشه نباشد،
73
00:02:35,599 –> 00:02:37,840
این بدان معناست که دادهها از کلید ریشه بزرگتر هستند،
74
00:02:37,840 –> 00:02:39,519
بنابراین باید در درخت فرعی سمت راست جستجو کنیم،
75
00:02:39,519 –> 00:02:40,879
76
00:02:40,879 –> 00:02:42,879
بنابراین این مراحلی است که باید
77
00:02:42,879 –> 00:02:44,879
در حین انجام عملیات جستجو دنبال کنیم.
78
00:02:44,879 –> 00:02:47,760
ابتدا باید داده های گره های
79
00:02:47,760 –> 00:02:49,280
داده شده را با کلید ریشه مقایسه
80
00:02:49,280 –> 00:02:52,400
کنیم اگر مساوی باشد اگر مساوی باشد یعنی
81
00:02:52,400 –> 00:02:55,040
گره پیدا می شود اگر مساوی نباشد سپس
82
00:02:55,040 –> 00:02:57,760
باید کلید ریشه را با
83
00:02:57,760 –> 00:03:00,319
داده هایی با داده های کوچکتر از کلید اصلی مقایسه کنم.
84
00:03:00,319 –> 00:03:01,920
اگر درست باشد، باید در
85
00:03:01,920 –> 00:03:02,400
86
00:03:02,400 –> 00:03:05,280
درخت فرعی سمت چپ جستجو کنیم اگر نادرست است، یعنی
87
00:03:05,280 –> 00:03:07,440
دادههای گرههای داده شده بزرگتر از
88
00:03:07,440 –> 00:03:08,080
کلید ریشه است،
89
00:03:08,080 –> 00:03:09,840
بنابراین باید در درخت فرعی سمت راست جستجو کنیم،
90
00:03:09,840 –> 00:03:11,599
بنابراین بیایید
91
00:03:11,599 –> 00:03:14,080
این مرحله را بنویسیم.
92
00:03:14,080 –> 00:03:14,800
93
00:03:14,800 –> 00:03:17,920
کلید چک ریشه برابر با داده است بنابراین
94
00:03:17,920 –> 00:03:19,840
من از شرط اگر برای آن استفاده میکنم
95
00:03:19,840 –> 00:03:23,200
اگر کلید root dot
96
00:03:23,200 –> 00:03:26,000
بنابراین اینجا نمیتوانم root را درست در اینجا بنویسم
97
00:03:26,000 –> 00:03:28,080
self نمایانگر شی است، بنابراین
98
00:03:28,080 –> 00:03:29,599
باید کلید self
99
00:03:29,599 –> 00:03:32,879
dot برابر با داده
100
00:03:32,879 –> 00:03:35,280
باشد اگر درست باشد، پس باید
101
00:03:35,280 –> 00:03:36,000
102
00:03:36,000 –> 00:03:39,599
اگر گره پیدا شد، پیامی را چاپ کنید که گره یافت می شود،
103
00:03:39,599 –> 00:03:41,920
پس نیازی به انجام کار دیگری نیست، بنابراین من
104
00:03:41,920 –> 00:03:43,599
عبارت بازگشت را می نویسم،
105
00:03:43,599 –> 00:03:45,840
بنابراین اگر این شرط درست باشد
106
00:03:45,840 –> 00:03:47,200
، این پیام را چاپ
107
00:03:47,200 –> 00:03:49,680
می کند و اگر شما از این روش خارج
108
00:03:49,680 –> 00:03:51,680
می شود. نمیخواهید از return در اینجا استفاده کنید، میتوانید در اینجا
109
00:03:51,680 –> 00:03:52,239
از
110
00:03:52,239 –> 00:03:56,400
موارد دیگر استفاده کنید، در غیر این صورت در هر
111
00:03:56,400 –> 00:03:58,400
روش، اولین پارامتر
112
00:03:58,400 –> 00:03:59,680
خود شی را
113
00:03:59,680 –> 00:04:02,239
در اینجا نشان میدهد، زیرا ما این روش را
114
00:04:02,239 –> 00:04:02,720
با استفاده از
115
00:04:02,720 –> 00:04:05,920
شی root در اینجا میخوانیم،
116
00:04:05,920 –> 00:04:08,720
بنابراین در اینجا self چیزی جز شی ریشه نیست.
117
00:04:08,720 –> 00:04:10,799
بنابراین کلید self dot برابر با
118
00:04:10,799 –> 00:04:12,720
داده است یعنی کلید نقطه ریشه
119
00:04:12,720 –> 00:04:13,760
برابر با داده است
120
00:04:13,760 –> 00:04:16,079
ما در حال بررسی اولین کلید گره ها
121
00:04:16,079 –> 00:04:16,959
با داده ها هستیم
122
00:04:16,959 –> 00:04:19,199
اگر مساوی باشد سپس گره پیدا می شود
123
00:04:19,199 –> 00:04:20,160
در غیر این صورت
124
00:04:20,160 –> 00:04:22,800
اگر برابر نیست پس بررسی می کنم که
125
00:04:22,800 –> 00:04:23,280
آیا
126
00:04:23,280 –> 00:04:27,120
داده ها کمتر از کلید ریشه است بنابراین داده
127
00:04:27,120 –> 00:04:30,080
ها کمتر از اگر میخواهم
128
00:04:30,080 –> 00:04:30,639
129
00:04:30,639 –> 00:04:33,040
کلید roots را بررسی کنم، باید کلید self
130
00:04:33,040 –> 00:04:34,000
dot
131
00:04:34,000 –> 00:04:36,639
را انتخاب کنم، بنابراین اگر درست است اگر دادهها کمتر از
132
00:04:36,639 –> 00:04:37,759
کلید خود نقطه
133
00:04:37,759 –> 00:04:39,199
باشد، به این معنی است که باید
134
00:04:39,199 –> 00:04:40,880
گره داده شده را در درخت فرعی سمت چپ در سمت
135
00:04:40,880 –> 00:04:43,759
راست جستجو کنم. درخت فرعی سمت چپ ممکن است
136
00:04:43,759 –> 00:04:45,520
با دو موقعیت روبرو شویم،
137
00:04:45,520 –> 00:04:48,320
موقعیت اول، زیردرخت چپ میتواند
138
00:04:48,320 –> 00:04:48,639
139
00:04:48,639 –> 00:04:51,680
خالی باشد و وضعیت دوم
140
00:04:51,680 –> 00:04:54,960
میتواند حاوی زیردرخت چپ باشد، میتواند شامل
141
00:04:54,960 –> 00:04:58,160
یک یا بیش از یک گره باشد، باید
142
00:04:58,160 –> 00:04:58,880
143
00:04:58,880 –> 00:05:01,120
برای این دو حالت شرط جداگانه بنویسیم.
144
00:05:01,120 –> 00:05:02,160
145
00:05:02,160 –> 00:05:05,039
گره ریشه است، این یک درخت است و
146
00:05:05,039 –> 00:05:06,720
147
00:05:06,720 –> 00:05:08,880
حاوی مقداری زیردرخت سمت راست است، اما
148
00:05:08,880 –> 00:05:10,160
149
00:05:10,160 –> 00:05:13,440
اگر بخواهم 5 را در این درخت جستجو
150
00:05:13,440 –> 00:05:16,639
کنم، ابتدا 10 را با 5 راست مقایسه می کنم،
151
00:05:16,639 –> 00:05:18,720
10 برابر با 5 نیست، سپس من بررسی میکنم
152
00:05:18,720 –> 00:05:20,720
که آیا دادههای گره
153
00:05:20,720 –> 00:05:22,960
5 کمتر از 10 درست است، بنابراین باید
154
00:05:22,960 –> 00:05:24,720
در زیردرخت سمت چپ جستجو کنم،
155
00:05:24,720 –> 00:05:26,479
اما در اینجا میتوانیم ببینیم که حاوی
156
00:05:26,479 –> 00:05:28,960
هیچ زیردرخت سمت چپی نیست، به این معنی که
157
00:05:28,960 –> 00:05:31,440
زیر t سمت چپ در آن زمان که نیاز داریم خالی است.
158
00:05:31,440 –> 00:05:32,479
برای نوشتن گره پیام
159
00:05:32,479 –> 00:05:35,039
در درخت وجود ندارد اگر
160
00:05:35,039 –> 00:05:36,080
گره p نباشد
161
00:05:36,080 –> 00:05:39,039
در سمت چپ این گره 10 ریشه ای ارسال مجدد شود،
162
00:05:39,039 –> 00:05:40,080
یعنی
163
00:05:40,080 –> 00:05:42,960
گره در درخت وجود ندارد سمت راست
164
00:05:42,960 –> 00:05:44,800
این درخت فقط شامل گره ریشه
165
00:05:44,800 –> 00:05:48,479
و زیردرخت سمت راست است و 5 کمتر از 10 است
166
00:05:48,479 –> 00:05:51,039
اگر فی در 3 وجود داشته
167
00:05:51,039 –> 00:05:53,520
باشد، باید در سمت چپ وجود داشته باشد. از 10
168
00:05:53,520 –> 00:05:55,759
زیرا در اینجا این گره فاقد
169
00:05:55,759 –> 00:05:58,160
درخت فرعی سمت چپ است که به این معنی است که گره
170
00:05:58,160 –> 00:05:58,639
یافت نمی شود،
171
00:05:58,639 –> 00:06:01,440
بنابراین وقتی زیردرخت سمت چپ خالی است، به این معنی است که
172
00:06:01,440 –> 00:06:03,600
گره در درخت وجود ندارد
173
00:06:03,600 –> 00:06:06,080
و اگر زیردرخت چپ شامل یک یا چند
174
00:06:06,080 –> 00:06:07,120
گره باشد
175
00:06:07,120 –> 00:06:09,840
، باید به آن نیاز دارم. آیا باید دوباره عملیات
176
00:06:09,840 –> 00:06:10,319
جستجو
177
00:06:10,319 –> 00:06:14,720
را در درخت فرعی سمت چپ انجام دهم،
178
00:06:14,720 –> 00:06:16,960
باید دوباره عملیات جستجو را
179
00:06:16,960 –> 00:06:18,880
در درخت فرعی سمت چپ انجام دهم،
180
00:06:18,880 –> 00:06:21,680
باید دوباره این روش جستجو را فراخوانی کنم،
181
00:06:21,680 –> 00:06:24,240
ما در اینجا از روش بازگشتی استفاده می کنیم،
182
00:06:24,240 –> 00:06:28,160
ابتدا بررسی می کنم که آیا خود
183
00:06:28,160 –> 00:06:32,000
نقطه l فرزند بنابراین ما درست با این شرط آشنا هستیم،
184
00:06:32,000 –> 00:06:33,039
185
00:06:33,039 –> 00:06:35,199
در حالی که در مورد روش درج
186
00:06:35,199 –> 00:06:37,039
توضیح دادم، در این مورد توضیح دادم
187
00:06:37,039 –> 00:06:40,639
اگر خود نقطه l فرزند وجود داشته
188
00:06:40,639 –> 00:06:42,800
باشد، به این معنی است که درخت فرع