[MÜZİK OYUN] Doug LLOYD: Yani biz yakın inching oldum ve daha yakın bu verilerin Holy Grail biz ekleyebilirsiniz yapıları, tek içine, silmek ve bakmak sürekli zaman içinde. Sağ. Bu hedefe tür. Biz yapabilmek istiyorum işler çok, çok hızlı. 

Biz burada ne zaman buldunuz Biz deneme bahsediyoruz? Peki, bir göz atalım. Bu yüzden birkaç gördüm Farklı veri yapıları Bu haritalama kolu anahtar-değer çiftleri olarak adlandırılan, bazı verileri parça haritalama verilerin başka bir parçasına bu yüzden nerede bulacağınızı biliyorsunuz yapıda bilgiler. 

Bu nedenle bir dizi için, örneğin, anahtar unsur indeksi veya dizi Konumu 0 ya da dizi 1 vb. Ve değer veri o konumda bulunmaktadır. Yani dizideki 0 ne saklanır? Ne sadece karşı dizide 1 depolanır 0, 1, anahtarlar olurdu. 

Karma tablo ile bu kadar Aynı fikir tür. Karma tablo ile, bu karma var hash kodları üretir işlevi. Yani anahtar verilerinin karma kodudur. Ve değer, özellikle de biz zincirleme hakkında konuştuk karma tablolar video, Verilerin bu bağlantılı liste o hashCode için sağlamalarının. Sağ. Başka bir yaklaşım hakkında neler Bu yöntem olsa? Bir yöntem hakkında ne nerede anahtar, benzersiz olması sağlanır karma tablo, biz olabilir aksine Verilerin iki parça ile sona Aynı hashcode sahip. Ve sonra biz uğraşmak zorunda bu da sondalama veya daha fazla tercihen bu sorunu çözmek için zincirleme. 

Yani şimdi garanti edemez Bu bizim anahtar benzersiz olacaktır. Ve değer ne varsa kolay bir şey ister bize o kadar doğru ve yanlış bilgi ya da bu parça yapısında bulunan? Bir Boole biraz kadar basit olabilir. Gerçekçi muhtemelen var bir biraz daha muhtemeldir bayt. Ama çok daha küçük olduğunu 50-karakter dizesi belki depolamak, Örneğin. 

Denemeden Yani, tablo karma benzer, hangi birleştirmek diziler ve bağlantılı liste, çalışır diziler birleştirmek, yapıları ve işaretçileri Birlikte veri depolamak için var ilginç bir yol oldukça farklı Şimdiye kadar gördüğüm şey. Şimdi bir yol haritası olarak verileri kullanmak Bu veri yapısını gezinmek için. Ve biz takip edebilirsiniz eğer yol haritası, eğer biz veri izleyin Başından sonuna, yaparız Bu veriler olup olmadığını bilmek tray bulunmaktadır. 

Ve biz haritayı takip edemez eğer Tüm sona anlam dışında, veri var olamaz. Yine, anahtarlar burada benzersiz olmasını garanti. Yani karma tablo aksine, biz asla anlayamayacağım Burada çarpışmalar ile uğraşmak zorunda. Ve veri yok iki parça aynı yol haritası var sürece veri aynıdır. 

Biz John, daha sonra takarsanız Biz John arayın. Bu iki özdeş parçaları var Veri, sağ, biz aracılığıyla arıyoruz. Ama aksi takdirde, herhangi bir veri iki adettir benzersiz yol haritaları için garanti Bu veri yapısı ile. Ve biz bakmak için gidiyoruz Sadece bir an, bu bir görsel. 

Biz çalışarak bu yapacağım Yeni bir veri yapısı oluşturmak, Aşağıdaki anahtar değer çiftleri haritalama. Bu durumda, biz kullanmak için gidiyoruz değil Bir Boolean gibi basit bir şey. Biz aslında dize depolar. Ve bu dize gidiyor Bir üniversitenin adı olabilir. 

Ve anahtar yılı olacak Bu üniversitenin kurulduğu zaman. Üniversiteler için tüm yıl Dört basamaklı olacak. Ve böylece biz bu dört basamak kullanacağız Bu veri yapısının gezinin. Ve biz yine göreceğiz, nasıl biz sadece bir saniye içinde bunu. 

Yolun sonunda, Biz ismini görürsünüz karşılık gelen üniversite Bu anahtara, bu dört basamak. Bir tray arkasındaki temel fikir Biz merkezi rota olması. Yani bir ağaç gibi düşün. Ve bu yazım benzer ve bir ağaca kavramı. Genellikle biz düşünmek zaman Gerçek dünyada ağaçlar, Onlar öyle bir kök var zemin ve yukarı doğru büyür ve onlar şubeleri var ve onlar yaprakları vardır. Ve temelde fikri bir tray, tam olarak aynı kök demirlemiş hariç gökyüzünde bir yerde. Ve yaprakları alt kısmında bulunmaktadır. 

Yani bir ağaç alma gibi naziksiniz ve sadece baş aşağı çevirerek. Ama yine de şubesi bulunmaktadır. Ve bu bizim yollar olacaktır Bu bizim bağlantıları olacak yapraklara kökünden. Bu durumda, bu yolları, bu dalları bize hane ile etiketlenmiş hangi yolu Nerede gitmek için. 

Biz 0 görürseniz, bu şube aşağı gitmek, Biz 1 görürseniz, bu şube aşağı gitmek, ve benzeri ve benzerleri. Peki, bu ne anlama geliyor? Eh, bu demektir Her kavşak noktasında ve her düğüm orta ve her dal, olası 10 vardır biz gidebiliriz yerler. Yani 10 göstericiler vardır Her yerden. 

Çalışır, bir nereden bulabilirim ve bu biri için korkutucu biraz kim bir sürü yok önce bilgisayar bilimlerinde deneyim. Ama çalışır gerçekten çok harika. Ve varsa onlarla çalışmak için bir şans ve kazmak-in tutardır ve onlarla birlikte deney, onlar gerçekten oldukça ilginç konum veri yapıları ile çalışmak. Biz bir öğe eklemek istiyorsanız traya içine bütün yapmamız gereken Doğru yol inşa edildi yaprak kökünden. İşte nasıl her adımda birlikte var yol gibi görünebilir. Biz yeni bir veri tanımlamak için gidiyoruz yeni bir düğüm için yapı tray çağırdı. 

Ve bu verilerin içinde yapı iki parça vardır. Biz saklamak için gidiyoruz Bir üniversitenin adı. Ve biz saklamak için gidiyoruz işaretçiler bir dizi Aynı türdeki diğer düğümlere. Yani, yine, bu o tür Her yerde kavramının biz 10 mümkünse vardır biz gidebiliriz yerler. Biz 0 görürseniz, bu şube aşağı gitmek. Biz 1 görürseniz, bu şube, ve benzerleri ve benzeri ve benzerleri. Biz 9 derseniz, biz bu şube aşağı gitmek. Her kavşak noktasında Yani Biz 10 olası yerlere gidebilir. Yani her düğüm 10 işaretçiler içermelidir 10 diğer düğümlere diğer düğümlere için. 

Ve biz saklıyoruz veri üniversitenin sadece isim. Yani bir tray yapalım. En bir çift eklemek edelim Bizim tray içine öğeleri. Çok üstünde Yani Bu bizim kök düğümdür. Bu muhtemelen bir şey olacak Eğer declare global olarak gidiyoruz. Ve bakımını global olarak gidiyoruz her zaman bu düğüme bir işaretçi. 

Sen demek için gidiyoruz Kök eşittir, ve sen Kendinize tray düğümü malloc olacak. Ve asla gidiyoruz Yine kök dokunun. Istediğiniz her zaman gezinme başlayın, Başka işaretçi ayarlamak Böyle trav olarak, kök eşit, bu örnek, bir videoları benim birçok kullanmak Burada yığınlar ve kuyruklar üzerinde ve bağlantı listeleri vb. 

Başka bir işaretçi ayarlamak kastetmek için trav denir. Ve gezinmek için trav kullanın Veri yapısı ile. Yani bu nasıl görünebileceğini görelim. Yani şimdi, ne Bir düğüm benziyor? Peki, sadece bizim veri olarak yapı beyanı, belirtilen Biz bir dize sahip olan Bu durumda boştur. Burada bir şey yok. 

Ve 10 işaretçiler bir dizi. Ve şimdi, biz sadece Bu tray 1 düğümü vardır. İçinde başka bir şey yok. Yani bunların hepsi 10 nokta işaretçileri null. O kırmızı işaret buydu. 

En dize Harvard eklemek edelim. En University eklemek edelim Bu tray içine Harvard, burada Yıl 1636 yılında kuruldu. Biz anahtarı kullanmak istiyorum, 1636, biz olduğun yerde bize tray de Harvard'a saklamak için gidiyoruz. Şimdi, bunu nasıl yapabilirim? 

Böyle bir şey olabilir. Biz kökünde başlar. Ve biz gidebiliriz bu 10 yerler var. Kök herhangi gibi tray diğer düğüm. Buradan gidebilirsiniz 10 yer vardır. 

Nerede muhtemelen istiyoruz Anahtar 1636 ise gitmek için? Gerçekten iki seçenek var. Sağ. Biz anahtarı oluşturabilirsiniz sağdan sola ve 6 ile başlamak. Ya anahtarı inşa edebileceğini soldan sağa ve 1 ile başlar. 

Muhtemelen daha var bir insan olarak sezgisel bir sorunumuz olacak anlamak için Sadece sağa sola gidin. Ve bu yüzden eklemek istiyorsanız Bu tray içine Harvard Herhalde başlamak istiyorum kökünden başlayarak, Benim 10 seçenekleri bakarak Önümde, söyleyerek Ben 1 yolda gitmek istiyorum. TAMAM. 

Şimdi, 1 yol şu anda boş olduğunu. Yani bu yolda devam etmek istiyorsanız traya içine bu öğe eklemek için, Ben 1 var, yeni bir düğüm malloc zorunda Orada gelin ve sonra gitmek iyi değilim. 

Yani temelde bir de ben nokta nerede duruyorum ağaç veya kökündeki tray ve 10 şubesi vardır. Ama her dal olan Bunun önündeki kapısı. Sağ. Bir şey yok, çünkü başka var. Hayır güvenli geçiş. O hiçbir şey demektir Bu dalların herhangi aşağı. Binayı başlatmak istiyorsanız bir şey, ben kapıyı kaldırmak istiyor. Ben kapıyı kaldırmak istiyorum 1 numaralı ön. Ve ben aşağı yürümek istiyorum. Ve ben kurmak istiyorum Benim için başka bir yere gitmek için. 

Ve ben burada yaptığım buydu. Yani 1 artık null işaret ediyor. Ben şimdi burada aşağı gitmek güvenli söyledim. Ben başka bir düğüm inşa. Ve ben bu düğüme olsun, ben yapmak için başka bir karar var. Nereye buradan gitmek için gidiyorum? 

Eh, zaten 1 aşağı gittin. Yani şimdi ben muhtemelen 6 aşağı gitmek istiyorum. Sağ. Yine, ben seçebilirsiniz 10 yerler var. Öyleyse şimdi numarayı 6 aşağı gidelim. Yani kapıyı açık 6 numaralı önüne. Ve ben oraya yürüyorum. Ve ben başka bir düğüm oluşturmak. Ve ben başka birleşim noktası ulaştınız. 

Yine, ben 10 seçeneğiniz var Ben nereye için. I, 1 ile 6 arasında hareket ettik. Yani şimdi ben muhtemelen 3 gitmek istiyorum. 3, hiçbir yerde gidebilirsiniz var. Yani yolu temizlemek zorunda ve kendime yeni bir alan oluşturmak. Ve sonra ben gitmek istersiniz 3, gelen? Ben aşağı 6 gitmek istiyorum. 

Ve yine, ben vardı Bunu yapmanın yolu temizleyin. Yani şimdi ben oluşturmak eklemek için benim anahtar kullandım düğümler bu trie inşa etmeye başlar ve. Ben kökünde başladım. Ben 1636 aşağı gittim. Ve şimdi dibinde değilim Orada bu düğüm üzerindeki. Ve mümkün olabilir Ekranda görmek. 

Sarý oluyor. Şu anda nerede budur. Benim anahtar yapılır. Benim anahtarında her pozisyonda tükettim. Yani daha hiç gidemem. Bu noktada, tüm I So gerçekten Tamam, demek yapmanız gerekiyor. Bu tür bakıyor gibi oluyor yere aşağı, Eğer öngören eğer Kendinizi yolun bu tür olarak Farklı bağlantıları ile. Sıralama aşağı ve çeşit arıyor Yerde Harvard'a boyama sprey. Yani, bu adı. Bu konumda ne olduğunu biliyorum. Biz kök başlar ve aşağı giderseniz 1 ve 6 ve daha sonra 3 ve 6, neredeyiz? Peki biz aşağı bakmak durumunda ve biz o zaman, Harvard bkz Biz Harvard olduğunu biliyoruz Yolda dayalı 1636 yılında kurulan Bu veri yapısı uygulamak ediyoruz. Yani umarım açıktı. Biz iki eklemeleri yapmak için gidiyoruz. Ve umarım yardımcı olacak bkz bu kez daha yapmış. 

Şimdi, başka bir üniversite eklemek edelim. Şimdi bu tray içine Yale eklemek edelim. Yale 1701 yılında kurulmuştur. Yani biz başlayacağız Kök, biz her zaman yaptığımız gibi. Ve biz kastetmek işaretçi ayarlayın. Biz gezinmek için kullanan gidiyoruz. Biz istediğiniz ilk şey do 1 yolda gidin. Bu bizim anahtarın ilk basamak var. Neyse ki, olsa da, biz değil Herhangi bir esere bu sefer yapmak zorunda. 1 yol zaten temizlenmiş oldu. Daha önce ben onu temizlenir 1636 de Harvard'a takmadan oldu. Yani güvenle taşıyabilirsiniz 1 aşağı ve sadece oraya gitmek. 1 aşağı hareket edebilirsiniz. 

Şimdi olsa, ben 7 gitmek istiyorum. Ben 6'da yolu temizledi. Ben güvenle yapabilirsiniz biliyorum 6 yolda devam edin. Ama 7 yolda devam etmek gerekir. Peki ne yapmam gerekiyor? Peki, daha önce olduğu gibi, sadece ihtiyaç Kapıyı temizlemek için, yoldan çekil, ve 7 yolundan yeni bir düğüm oluşturmak. Aynen böyle. 

Yani şimdi ben 1 ve sonra 7 taşındım. Ve şimdi fark ben sayılırım bu yeni subbranch üzerinde. Sağ. 16 ila Her şey , ben umurumda değil. Ben 16 şey yapmıyorum. Ben 17 şeyler yapıyorum. 

Şimdi 17'den, ben var çeşit burada yeni yollar yangını. Bir sonraki basamak benim anahtar 0'dır. Ben açıkça her yerde alamıyorum. Ben sadece bu düğüm inşa etti. Yani orada hiçbir biliyorum İleri buradan yolları. Bu yüzden bir kendimi yapmak zorunda. 

Yani yeni bir düğüm malloc ve orada 0 nokta var. Ve sonra bir kez daha, ben malloc bir Yeni düğüm ve orada bir nokta var. Yine, benim anahtar, 1701 tükettik. Yani aşağı bakmak ve ben Yale boya sprey. İşte bu düğümün adı. 

Ve şimdi ben hiç Yale görmek için gerekirse Bu tray de, ben kökünde başlayacak olan, Ben 1701 inmek ve aşağı bakmak. Ve ben Yale sprey görürsem Daha sonra, zemin üzerine boyalı Ben Yale Bu tray var biliyorum. Bir kere daha yapalım. Şimdi bu içine Dartmouth eklemek edelim 1769 yılında kurulan tray. 

Yine kökünden başlayın. Benim anahtar Benim ilk basamak 1'dir. Ben güvenle bu yolda hareket edebilirsiniz. Bu zaten var. Benim anahtar sonraki basamak 7'dir. Ben güvenle bu yolda hareket edebilirsiniz. O da var. 

Benim sonraki 6. Buradan, Şu anda benim yerden O orta düğüm orada sarı, 6 Şu anda kapalı kilitli. Ben o yolda gitmek isterseniz, Kendim oluşturmamız gerekiyor. Yani yeni bir düğüm malloc edeceğiz ve orada 6 nokta var. Ve sonra, yine, ben burada yeni yollar yanan. 

Yani yeni bir düğüm malloc böylece Şimdi o node-- yol numarası 9-- ve Ben 1769 seyahat ve ben aşağı bakarsanız. Hiçbir şey şu anda yok Orada boyalı sprey. Ben Dartmouth yazabilirsiniz. Ve ben ekledikten Traya içine Dartmouth. 

Yani takmadan var traya içine işler. Şimdi şeylere aramak istiyorum. Nasıl tray şeyler arayabilirim? Peki, bu hemen hemen aynı fikir. Şimdi biz sadece anahtar rakamlarını kullanın Biz kök gezinebilirsiniz görmek için Biz tray gitmek istediğiniz yere. 

Biz o zaman, herhangi bir noktada çıkmaz vurursanız biz bu eleman var olamayacağını biliyorum ya da başka bu yolu olur Zaten temizlendi. Biz tüm yol yaparsanız sonunda, tüm yapmamız gereken aşağı bakmak ve bu olmadığını görmek olduğunu Aradığımız elemanı. Bu başarı ise. O değilse, başarısız. 

Yani aramak için izin Bu tray Harvard. Biz kökünde başlar. Ve yine, biz gidiyoruz Bir kastetmek işaretçi oluşturmak bizim için hamle yapmak. Root itibaren biz biliyoruz gitmemiz gereken ilk yer, 1 biz yapabiliriz? Evet yapabiliriz. Eğer güvenli var. Biz oraya gidebiliriz. 

Şimdi, biz gitmek gerekir bir sonraki yer 6'dır. 6 yolu buradan var mıdır? Evet, öyle. Biz 6 yolda gidebilirsiniz. Ve biz burada bitirmek. 

Buradan 3 yolda gidebilir miyim? Peki, bu çıkıyor gibi, evet, o da var. Ve biz burada 6 yolda alabilirim? Evet yapabiliriz. 

Biz oldukça cevap değil Henüz bir soru. Bir tane daha var hala şimdi adım, Biz aşağı bakmak gerekir ve Bu actually-- olmadığını görmek Harvard arıyorsanız, yani biz anahtar egzoz sonra ne buldun? Örneğin biz burada kullanıyorsanız, yıllar hep dört basamak vardır. Ama örnek nerede kullanıyor olabilirsiniz Eğer kelimelerin sözlük depoluyor. 

Ve böylece yerine 10 işaretçiler sahip Benim konum, sen 26 olabilir. Alfabenin her harfi için bir. Ve yarasa gibi bazı kelimeler vardır, bu, örneğin toplu bir alt kümesidir. Ve sen olsun bile anahtarın ucunu ve aşağı bakmak, ne görüyorsun olmayabilir Aradığınız. 

Yani her zaman hareket ettirmek zorunda Tüm yol ve daha sonra başarıyla mümkün olsaydı tüm yolu travers, aşağı bakmak ve bir final onay yapmak. Ben arıyorum şey mi? Eh, ben başladıktan sonra aşağı bakmak üstünde ve 1636 gidiş. Ben aşağı bakmak. Ben Harvard görüyorum. Yani, evet, ben başardı. Ne olursa ne arıyorum olsa da, tray değildir. Ben Princeton arıyorum ne olur, hangi 1746 yılında kurulmuştur. Ve böylece 1746 benim anahtar olur traya gezinmek için. Eh, ben kökünde başlar. Ve ben istiyorum ilk yer 1 yolda gider. Bunu yapabilir miyim? Evet yapabilirim. 

Orada 7 yolda gidebilir miyim? Evet yapabilirim. O da var. Ama burada 4 yolda gidebilir? Bu can, soruyu soran gibi Ben küçük kare aşağı devam ben sarı renkte vurgulanır ettik? Orada hiçbir şey yok. Sağ. 

Hiçbir şekilde ileri 4 yolda var. Princeton, bu tray olduğu 4 bu takdirde zaten bizim için temizlenmiş olurdu. Ve böylece bu noktada Biz ölü sonuna ulaştınız. Biz daha gidemem. Ve böylece biz, kesin söyleyebiliriz. Princeton Bu tray mevcut değil. 

Peki bu ne anlama geliyor? Sağ. Burada devam eden bir sürü var. Her yerde işaretçiler var. Ve, gibi görebilirsiniz Sadece, diyagramından düğümler bir sürü olduğunu tür etrafında uçuyor. Ama biz istedik her zaman fark bir şey tray içinde olup olmadığını kontrol edin biz sadece 4 hamle yapmak zorunda kaldı. 

Biz istedik her zaman tray şey eklemek biz muhtemelen, 4 hamle yapmak zorunda Yol boyunca bazı şeyler mallocing. Biz takıldığında Ama biz gördüğümüz gibi Traya içine Dartmouth, Bazen yolun bazı zaten bizim için temizlenmiş olabilir. Ve böylece bizim trie alır gibi büyük ve Daha büyük, daha az çalışmalarının her zaman yapmak zorunda yeni şeyler eklemek için biz zaten ettik çünkü ara bir sürü inşa Yol boyunca dalları. Biz sadece şimdiye bakmak varsa 4 şey 4 sadece bir sabittir. Biz gerçekten bir tür yaklaşıyor zaman sabiti ekleme ve sabit zaman arama. Tradeoff, tabii ki, varlık Bu tray olarak muhtemelen söyleyebilirim çok büyük. Bu düğümlerin her biri çok yer kaplıyor. 

Ama bu değiş tokuş. Biz gerçekten çabuk istiyorsanız ekleme, gerçekten hızlı silme, ve gerçekten hızlı arama, biz var Verilerin bir sürü etrafında uçan var. Biz çok yer ayırmak zorunda ve veri yapısı için bellek var olmak. 

Ve böylece değiş tokuş. Ama biz benziyor Onu bulmuş olabilir. Biz bulduk olabilir veri yapılarının Holy Grail Hızlı ekleme ile, silme ve arama. Ve belki bu bir olacak Uygun bir veri yapısı ne olursa olsun bilgi için kullanmak Biz mağazaya çalışıyoruz. Ben Doug Lloyd değilim, bu CS50 olduğunu.