[موسیقی] داگ لوید: بنابراین ما شده میدل ایست ژورنال را نزدیک تر و نزدیک تر که جام مقدس از داده سازه، یکی است که ما می توانید وارد به، حذف از، و نگاه کردن در زمان ثابت. درست. این نوع از هدف است. ما می خواهیم به قادر به انجام چیزهای بسیار، بسیار به سرعت. 

آیا ما آن را در اینجا پیدا شده است که ما در حال صحبت کردن در مورد تلاش می کند؟ خوب، اجازه دهید نگاهی به. بنابراین ما چند دیده ام ساختمان داده های مختلف که مسئولیت رسیدگی به نقشه برداری از به اصطلاح جفت کلید ارزش، نقشه برداری برخی از قطعه داده به برخی از قطعه دیگری از داده ها بنابراین ما می دانیم که برای پیدا کردن اطلاعات در ساختار. 

بنابراین برای آرایه، به عنوان مثال، کلید شاخص عنصر آرایه است یا محل 0 یا آرایه 1 و غیره. و ارزش داده است که در آن محل وجود دارد. بنابراین آنچه که در آرایه 0 ذخیره می شود؟ آنچه که در آرایه 1 در مقابل فقط ذخیره شده 0 و 1، خواهد بود که کلید. 

با یک جدول هش آن مرتب کردن بر اساس همان ایده. با یک جدول هش، ما باید این هش تابع است که کدهای هش. بنابراین کلید کد هش از داده است. و ارزش، به ویژه ما در مورد صحبت زنجیری در این ویدئو در جداول هش، که لیست پیوندی داده است که هش که hashcode. درست. چه روش دیگری این روش، هر چند؟ آنچه در مورد یک روش که در آن کلید تضمین شده است به منحصر به فرد، بر خلاف یک جدول هش، که در آن ما می تواند در نهایت با دو قطعه اطلاعات داشتن hashcode است. و سپس ما باید برای مقابله با که هم پروب یا بیشتر ترجیحا زنجیری برای رفع این مشکل است. 

بنابراین در حال حاضر ما می توانیم تضمین که کلید منحصر به فرد خواهد بود. و اگر ارزش ما بود فقط چیزی به عنوان آسان به عنوان درست و نادرست است که ما می گوید که آیا یا نه که قطعه ای از اطلاعات در ساختار وجود دارد؟ یک بولی می تواند به عنوان ساده به عنوان یک بیت. در واقع آن را احتمالا یک بایت احتمال بیشتری نسبت به کمی. اما این بسیار کوچکتر از ذخیره سازی شاید یک رشته 50-شخصیت، برای مثال. 

بنابراین تلاش می کند، مشابه به هش جداول، که ترکیب آرایه ها و لیست پیوندی، تلاش می کند ترکیب آرایه ها، سازه، و اشاره گر با هم به ذخیره داده ها در یک راه جالب که بسیار متفاوت از هر چیزی که ما تا کنون دیده ام. در حال حاضر ما با استفاده از داده ها به عنوان یک نقشه راه به حرکت این ساختار داده. و اگر ما می توانید به دنبال نقشه راه، اگر ما می توانیم داده ها از دنبال ابتدا تا انتها، ما می دانم که آیا که داده در این درخت وجود دارد. 

و اگر ما می توانید نقشه را دنبال نمی کند از معنی برای پایان دادن به در همه، داده نمی تواند وجود داشته باشد. باز هم، کلید در اینجا تضمین می شود منحصر به فرد. و بنابراین بر خلاف یک جدول هش، ما هرگز باید برای مقابله با برخورد در اینجا. و هیچ دو قطعه از داده ها دقیقا همان نقشه راه مگر آن که داده ها یکسان است. 

اگر ما وارد جان، پس از آن ما برای جان را جستجو کنید. که دو قطعه یکسان از داده ها، درست است، ما به دنبال از طریق. اما در غیر این صورت، هر دو قطعه از داده ها هستند تضمین شده است به نقشه راه های منحصر به فرد از طریق این ساختار داده ها. و ما در حال رفتن به یک نگاه تصویری از این در یک لحظه. 

ما این کار را با تلاش برای انجام ایجاد یک ساختار داده های جدید، نقشه برداری از زیر جفت کلید. در این مورد، ما قصد داریم به استفاده از چیزی به عنوان ساده به عنوان یک بولی. ما در واقع را به رشته ذخیره کنید. و این رشته در حال رفتن به بود به نام یک دانشگاه. 

و کلید است برای رفتن به سال وقتی که دانشگاه تاسیس شد. همه سال برای دانشگاه در حال رفتن به چهار رقم. و بنابراین ما آن چهار رقم به استفاده از حرکت از طریق این ساختار داده. و ما دوباره خواهید دید،، چگونه ما این کار را در یک ثانیه. 

در پایان مسیر، ما نام را ببینید از دانشگاه که مربوط به این کلید را آن چهار رقم. ایده اصلی در پشت یک درخت پیشوندی این است که ما باید یک مسیر مرکزی. بنابراین در مورد آن را مانند یک درخت فکر می کنم. و این در املای مشابه است و در مفهوم به یک درخت. به طور کلی هنگامی که ما در مورد فکر می کنم درختان در دنیای واقعی، آنها یک ریشه که در زمین و به سمت بالا آنها رشد می کنند و آنها را به شاخه و آنها را به برگ. و اساسا ایده یک درخت پیشوندی است دقیقا همان است، با این تفاوت که ریشه لنگر است جایی در آسمان. و برگ در پایین قرار دارند. 

پس از آن نوع مانند گرفتن یک درخت و فقط آن را کوه در می رم وارونه. اما هنوز هم شاخه وجود دارد. و کسانی می شود مسیر ما، آن خواهد بود ارتباطات ما از ریشه به برگ. در این مورد، آن مسیرها، آن شاخه با عددی که به ما بگویید برچسب که راه را برای از جایی که ما بروید. 

اگر ما یک 0، ما این شاخه بروید، اگر ما یک 1، ما این شاخه بروید، و به همین ترتیب و غیره. خب، این به چه معناست؟ خوب، که بدان معنی است که در هر نقطه اتصال و هر گره در وسط و هر شاخه، 10 وجود دارد مکان های که ما می توانید بروید. بنابراین 10 اشاره گر وجود دارد از هر محل. 

و این جایی است که تلاش می کند می تواند یک گرفتن کمی تهدید آمیز برای کسی که مقدار زیادی از ندارد تجربه در علوم کامپیوتر قبل از. اما سعی می کند واقعا بسیار عالی است. و اگر شما از شانس کار کردن با آنها و شما مایل به حفاری در حال و آزمایش با آنها، آنها واقعا بسیار جالب ساختمان داده برای کار با. اگر ما می خواهیم به قرار دادن یک عنصر به این درخت، همه ما نیاز به انجام ساخت مسیر صحیح از ریشه به برگ. اینجا چیزی است که هر قدم در طول راه ممکن است مانند نگاه. ما قصد داریم به تعریف یک داده جدید ساختار برای یک گره جدید به نام یک درخت پیشوندی. 

و در داخل آن داده ها ساختار دو قطعه وجود دارد. ما قصد داریم برای ذخیره نام یک دانشگاه. و ما قصد داریم برای ذخیره یک آرایه از اشاره گر به گره های دیگر از همان نوع. پس، دوباره، این است که مرتب سازی بر است از همه جا مفهوم ما، ما در 10 ممکن مکان ما می توانید بروید. اگر ما یک 0، ما پایین این شاخه. اگر ما یک 1، این شاخه، و غیره و غیره و غیره. اگر ما می گویند 9، ما پایین این شاخه. بنابراین در هر نقطه اتصال، ما می توانیم 10 مکان ممکن است. بنابراین هر گره حاوی 10 اشاره گر به گره های دیگر، به 10 گره های دیگر. 

و داده های ما در حال ذخیره سازی است فقط نام دانشگاه. بنابراین اجازه دهید یک درخت پیشوندی ساخت. اجازه دهید وارد کردن یک زن و شوهر از آیتم ها به درخت است. بنابراین در بالا بسیار، این گره ریشه ما است. این است که احتمالا به چیزی می شود شما در حال رفتن به سطح جهانی اعلام کند. و شما در حال رفتن به سطح جهانی حفظ یک اشاره گر به این گره همیشه. 

شما در حال رفتن به گفتن نیست، ریشه برابر، و شما به خودتان از malloc گره درخت. و شما هرگز دوباره ریشه را لمس کند. هر بار که شما می خواهید شروع به مرور از طریق، به شما در تنظیم یکی دیگر از اشاره گر به ریشه های برابر، مانند TRAV، که به عنوان مثال من است استفاده در بسیاری از از فیلم های من در اینجا بر روی پشته و صف و لیست های پیوندی و غیره. 

به شما در تنظیم یکی دیگر از اشاره گر نام TRAV برای پیمایش. و شما با استفاده TRAV به حرکت از طریق ساختار داده ها. بنابراین اجازه دهید که چگونه این ممکن است نگاه کنید. بنابراین در حال حاضر، چه یک گره نگاه می کنید؟ خوب، فقط به عنوان داده های ما اعلامیه ساختار نشان داد، ما یک رشته، که در این مورد خالی است. هیچ چیز در اینجا وجود دارد. 

و مجموعه ای از 10 اشاره گر. و در حال حاضر، تنها ما 1 گره در این درخت. هیچ چیز دیگری در آن وجود دارد. به طوری که همه از آن 10 نقطه اشاره گر تهی. این چیزی است که قرمز نشان می دهد. 

اجازه دهید وارد کردن رشته دانشگاه هاروارد است. اجازه دهید وارد دانشگاه دانشگاه هاروارد به این درخت که در سال 1636 تاسیس شد. ما می خواهیم به استفاده از کلید، 1636، به ما بگویید که در آن ما رفتن به ذخیره هاروارد در این درخت. در حال حاضر، چگونه ممکن است ما انجام این کار؟ 

ممکن است چیزی شبیه به این. ما در ریشه شروع می شود. و ما باید این 10 مکان ما می توانید بروید. ریشه مثل هر است گره دیگر از این درخت به. 10 مکان ما می توانید از اینجا وجود دارد. 

که در آن ما احتمالا می خواهید برای رفتن اگر کلید 1636 است؟ واقعا دو گزینه وجود دارد. درست. ما می توانید کلید از ساخت راست به چپ و شروع با 6. یا می توانیم کلید را از ساخت چپ به راست و شروع با 1. 

این احتمالا بیشتر بصری به عنوان یک انسان به درک ما فقط چپ به راست. و بنابراین اگر من می خواهم برای قرار دادن دانشگاه هاروارد به این درخت، من احتمالا می خواهید برای شروع با شروع در ریشه، با 10 گزینه های من در مقابل من، و گفت: من می خواهم به پایین 1 مسیر. باشه. 

در حال حاضر، در حال حاضر 1 مسیر تهی است. بنابراین اگر من می خواهم برای ادامه این مسیر برای وارد کردن این عنصر به درخت، من به malloc یک گره جدید 1 نقطه وجود دارد، و پس از آن خوب به آن بروید هستم. 

بنابراین من اساسا در یک هستم نقطه ای که من ایستاده ام در ریشه درخت یا درخت و 10 شاخه وجود دارد. اما هر شاخه است دروازه در مقابل آن. درست. زیرا هیچ چیز دیگری وجود دارد. بدون عبور امن. این بدان معناست که هیچ چیز وجود دارد پایین هر یک از این شاخه. اگر من می خواهم برای شروع ساختمان چیزی، من می خواهم به حذف دروازه. من می خواهم به حذف دروازه در مقابل شماره 1. و من می خواهم به پیاده روی پایین است. و من می خواهم به ساخت مکان دیگری برای من برای رفتن. 

و این چیزی است که من در اینجا انجام داده ام. بنابراین 1 دیگر امتیاز به تهی. من گفته ام آن را بی خطر به پایین در اینجا در حال حاضر. من گره دیگر ساخته شده است. و وقتی که به آن گره، من تصمیم دیگری را به. که در آن من رفتن به از اینجا بروم؟ 

خوب، من در حال حاضر به پایین 1 رفته است. بنابراین در حال حاضر من احتمالا می خواهید به پایین 6. درست. باز هم، من 10 مکان من می توانید انتخاب داشته باشد. بنابراین اجازه دهید حال حاضر پایین رفتن شماره 6. بنابراین من روشن دروازه در مقابل شماره 6. و من راه رفتن وجود دارد. و من گره دیگر ساخت. و من نقطه اتصال دیگر رسیدهاید. 

باز هم، من 10 انتخاب برای من که در آن می توانید بروید. من 1-6 نقل مکان کرد. بنابراین در حال حاضر من احتمالا خواهید برای رفتن به 3. 3، هیچ جا من می توانم رفتن وجود دارد. بنابراین من به راه روشن و یک فضای جدید ساخت خودم. و سپس از 3، که در آن من می خواهم برای رفتن؟ من می خواهم به پایین 6. 

و، دوباره، من تا به حال راه برای انجام آن روشن است. بنابراین در حال حاضر من کلید من استفاده می شود به قرار دادن ایجاد گره ها و شروع به ساخت این درخت. من در ریشه آغاز شده ام. من پایین 1636 رفته است. و در حال حاضر من در پایین هستم وجود دارد که گره. و شما ممکن است قادر به آن را بر روی صفحه نمایش خود را ببینید. 

آن را به رنگ زرد برجسته. این جایی است که من در حال حاضر. کلید من انجام شده است. من هر موقعیت در کلید من خسته ام. بنابراین من نمی توانم به هر بیشتر. بنابراین در این مرحله، همه من واقعا نیاز به انجام است می گویند، OK. این نوع از دوست به دنبال پایین در زمین، اگر شما در حال تجسم خود را به عنوان این نوع از مسیر با قابلیت اتصال به متفاوت است. مرتب کردن بر اساس نگاه کردن و مرتب کردن بر اساس رنگ اسپری دانشگاه هاروارد بر روی زمین. که نام این. بدانید که چه چیزی در این مکان. اگر ما در ریشه شروع و ما به پایین 1 و سپس 6 و سپس 3 و سپس 6، ما کجا هستیم؟ خوب اگر ما نگاه کردن و ما می بینیم هاروارد، پس از آن ما می دانیم که هاروارد بود در سال 1636 تاسیس بر اساس راه ما در حال اجرای این ساختار داده. به طوری که امیدوارم ساده بود. ما قصد داریم به انجام دو درج شده است. و امیدوارم آن را برای کمک به این دو بار دیگر انجام می شود. 

در حال حاضر، اجازه دهید وارد کردن یکی دیگر از دانشگاه. اجازه دهید وارد دانشگاه ییل به این درخت. دانشگاه ییل در سال 1701 تاسیس شد. بنابراین ما در شروع ریشه، به عنوان ما همیشه انجام دهید. و ما یک اشاره گر پیمایش تنظیم شده است. ما قصد داریم به استفاده از آن به طریق حرکت می کند. اولین چیزی که ما می خواهیم است به پایین 1 مسیر. که رقم اول اصلی ما است. خوشبختانه، هر چند، ما نمی به انجام هر کار در این زمان. 1 مسیر در حال حاضر پاک شده است. من آن را پاک قبلا وقتی که من شد قرار دادن دانشگاه هاروارد در 1636. بنابراین من با خیال راحت می تواند حرکت کند پایین 1 و فقط وجود دارد. اگر می توانید حرکت به پایین 1. 

در حال حاضر، هر چند، من می خواهم برای رفتن به 7. من راه در 6 پاک شده است. من می دانم که من با خیال راحت می توانید ادامه راه را 6. اما من نیاز به ادامه در مسیر 7. بنابراین چه چیزی باید انجام دهم؟ خب، درست مانند قبل، من فقط نیاز برای روشن شدن دروازه، از راه، و ساخت یک گره جدید از راه 7. درست مثل این. 

بنابراین در حال حاضر من نقل مکان کرد و پس از آن 1 7. و در حال حاضر متوجه میشوید که من هستم مرتب سازی بر از این subbranch جدید است. درست. هر چیز دیگری از 16 در، من در مورد مراقبت. من انجام 16 هر چیزی نیست. من انجام 17 مسائل. 

بنابراین در حال حاضر از 17 به بعد، من به مرتب کردن بر اساس شعله مسیرهای جدید در اینجا. رقم بعدی کلید من 0 است. من به وضوح می تواند هر جای دریافت کنید. من فقط ساخته شده است این گره. بنابراین من می دانم که هیچ وجود دارد مسیر رو به جلو را از اینجا. بنابراین من به یکی خودم. 

بنابراین من از malloc یک گره جدید و 0 نقطه وجود دارد. و سپس یک بار دیگر، من از malloc گره جدید و یک نقطه وجود دارد. باز هم، من کلید من، 1701 خسته ام. بنابراین من نگاه کردن و من اسپری رنگ ییل. که نام این گره است. 

و بنابراین در حال حاضر اگر من همیشه نیاز به دیدن اگر ییل در این درخت به، من در ریشه شروع، من پایین 1701 رفت، و نگاه کردن. و اگر من اسپری ییل را ببینید نقاشی بر روی زمین، پس از آن من می دانم که ییل در این درخت وجود دارد. اجازه دهید یکی بیشتر انجام دهد. اجازه دهید وارد کردن دارتموث به این پیشوندی، که در سال 1769 تاسیس شد. 

شروع در ریشه است. رقم اول من از کلید من 1 است. من با خیال راحت می توانید پایین حرکت می کند که مسیر. که در حال حاضر وجود دارد. رقم بعدی از کلید من 7 است. من با خیال راحت می توانید پایین حرکت می کند که مسیر. آن را به عنوان وجود دارد. 

بعدی من 6 است. از اینجا، از جایی که من در حال حاضر در زرد وجود دارد در آن گره متوسط، 6 در حال حاضر قفل شده است. اگر من می خواهم به این مسیر، من باید برای ساخت آن خودم. بنابراین من یک گره جدید از malloc و 6 نقطه وجود دارد. و پس از آن، دوباره، من فروزان مسیرهای جدید در اینجا. 

بنابراین من از malloc یک گره جدید به طوری که از که تعداد مسیر node-- 9-- و سپس در حال حاضر اگر من سفر 1769، و من نگاه کردن. هیچ چیز وجود دارد در حال حاضر اسپری رنگ وجود دارد. من می توانم دارتموث ارسال. و من قرار داده ام دارتموث به این درخت. 

به طوری که قرار دادن همه چیز را به این درخت. حالا ما می خواهیم به جستجو برای چیزهایی. چگونه ما برای چیزهایی در این درخت را جستجو کنم؟ خوب، آن را بسیار همان ایده. در حال حاضر ما فقط با استفاده از ارقام کلید برای دیدن اگر ما می توانیم از ریشه حرکت به جایی که ما می خواهیم در این درخت. 

اگر ما به بن بست در هر نقطه ضربه، سپس ما می دانیم که آن عنصر می تواند وجود داشته باشد و یا دیگری که مسیر را در حال حاضر پاک شده است. اگر ما آن را تمام راه را به پایان، همه ما باید انجام دهیم است نگاه کردن و ببینید که اگر که عنصر ما دنبال آن هستید. اگر آن را، موفقیت است. اگر این طور نیست، شکست است. 

بنابراین اجازه دهید برای جستجو دانشگاه هاروارد در این درخت. ما در ریشه شروع می شود. و، دوباره، ما قصد داریم به ایجاد یک اشاره گر پیمایش به انجام حرکات ما را برای ما. از ریشه ما می دانیم که در وهله اول ما نیاز به رفتن 1، می توانید را انجام داد؟ بله ما میتوانیم. اگر با خیال راحت وجود دارد. ما می توانیم وجود دارد. 

در حال حاضر، محل بعدی ما نیاز به رفتن 6 است. آیا مسیر 6 از اینجا وجود دارد؟ آره، آن را ندارد. ما می توانید به پایین مسیر 6. و ما تا پایان در اینجا. 

آیا ما می توانیم مسیر پایین 3 از اینجا بروم؟ همچنین، به عنوان آن می رسد، بله، وجود دارد که بیش از حد. و می تواند ما در مسیر 6 را از اینجا دریافت؟ بله ما میتوانیم. 

ما کاملا پاسخ داده نشده سوال است. هنوز هم یکی بیشتر وجود دارد گام به گام، که در حال حاضر ما نیاز به نگاه کردن و ببینید اگر که actually-- اگر ما به دنبال برای دانشگاه هاروارد، این است که چیزی که ما پیدا بعد از ما کلید اگزوز؟ در مثال ما با استفاده از در اینجا، سال همیشه چهار رقم. اما شما ممکن است که در آن با استفاده از مثال شما در حال ذخیره کردن یک فرهنگ لغت از کلمات. 

و به این ترتیب به جای داشتن اشاره گر 10 موقعیت مکانی من، شما ممکن است 26 داشته باشد. یکی برای هر حرف از حروف الفبا. و برخی از کلمات مانند خفاش وجود دارد، که زیر مجموعه ای از دسته ای، به عنوان مثال. و بنابراین حتی اگر شما به دریافت پایان کلید و شما نگاه کردن، شما ممکن است آنچه را ببینید شما دنبال آن هستید. 

بنابراین شما همیشه باید به گذشتن کل مسیر و پس از آن اگر شما با موفقیت قادر بودند برای گذشتن از کل مسیر، نگاه کردن و انجام یک تایید نهایی. این است که آنچه من به دنبال؟ خوب، من نگاه کردن بعد از شروع در بالا و رفتن 1636. من نگاه کردن. من در دانشگاه هاروارد را ببینید. بنابراین، بله، من موفق شد. اگر چه من به دنبال است در این درخت نیست، هر چند. چه می شود اگر من به دنبال پرینستون، که در سال 1746 تاسیس شد. و به این ترتیب 1746 کلید من می شود به این درخت به حرکت. خوب، من در ریشه شروع می شود. و در وهله اول من می خواهم به پایین 1 مسیر می رود. میتونم من انجامش بدم؟ بله می توانم. 

آیا من می توانم پایین مسیر 7 از وجود دارد؟ آره، من می توانم. که وجود دارد بیش از حد. اما می توانم پایین مسیر 4 از اینجا بروم؟ مثل این است که پرسیدن سوال، می توانید من اقدام به پایین است که مربع کوچک که من به رنگ زرد برجسته ام؟ هیچ چیز وجود دارد وجود دارد. درست. 

هیچ راهی رو به جلو را در مسیر 4 وجود دارد. اگر پرینستون در این درخت بود، که 4 را برای ما پاک شده است در حال حاضر. و بنابراین در این مرحله ما به بن بست رسیده ام. ما نمی توانیم به هر بیشتر. و به این ترتیب می توان گفت، قطعی، نه. پرینستون می کند در این درخت وجود ندارد. 

پس چه چیزی این همه چیست؟ درست. در بسیاری در اینجا وجود دارد. این اشاره گر در همه جا وجود دارد. و، به عنوان شما می توانید ببینید فقط از نمودار، در بسیاری از گره وجود دارد که نوع از پرواز در اطراف. اما توجه کنید هر زمان که ما را به خواست بررسی کنید که آیا چیزی در این درخت بود، ما تنها تا به حال به 4 حرکت می کند. 

هر بار که ما می خواستیم قرار دادن چیزی در این درخت، ما را به 4 حرکت می کند، احتمالا mallocing برخی از مسائل در طول راه. اما همانطور که ما را دیدم زمانی که ما وارد می دارتموث به این درخت، گاهی اوقات برخی از مسیر ممکن است در حال حاضر برای ما پاک شود. و بنابراین به عنوان درخت ما می شود بزرگتر و بزرگتر، ما باید کار کمتری انجام هر زمان برای وارد کردن چیزهای جدید چون ما در حال حاضر ساخته شده است بسیاری از متوسط شاخه در طول راه. اگر ما تنها به نگاه 4 چیز، 4 فقط یک ثابت است. ما واقعا در حال نزدیک شدن به نوع درج زمان ثابت و زمان مراجعه ثابت است. معاوضه، البته، این است که این درخت، همانطور که شما احتمالا می توانید بگویید، بزرگ است. هر یک از این گره ها طول می کشد تا مقدار زیادی از فضای. 

اما این معاوضه است. اگر ما می خواهیم واقعا سریع الحاق، حذف واقعا سریع، مراجعه سریع و واقعا، ما به یک مقدار زیادی از داده های پرواز در اطراف. ما را به کناری بگذاریم مقدار زیادی از فضای و حافظه برای آن ساختار داده خارج شدن. 

و به طوری که معاوضه. اما آن را مانند به نظر می رسد ما ممکن است آن را در بر داشت. ما ممکن است پیدا شده است که جام مقدس از ساختمان داده با درج سریع، حذف، و مراجعه. و شاید این خواهد بود که ساختار داده ها مناسب برای استفاده از هر اطلاعاتی که ما در حال تلاش به فروشگاه. من داگ لوید هستم، این CS50 است.