Konuşma notu: Bugün bir düğüm birden fazla düğüme işaret edebiliyor. Bir işaretçinin ikiye çıkması — listeden ağaca geçişin tamamı bu. Bu tek değişiklik, bugün öbeği, öncelik kuyruğunu ve Huffman kodlamasını, hepsini bir oturumda kuruyor.
Konuşma notu: On sekiz kısa animasyon dersin tamamını taşıyor; her biri, fikri tanıttığımız yerde bir kez görünüyor, birçoğu en can alıcı uç durumuna da bir kez daha bakıyor.
Konuşma notu: Her terim ilk geçtiği yerde tam olarak tanımlanır; bu tablo yalnızca onu nerede tekrar bulacağınızı söylüyor.
Konuşma notu: İsterseniz şimdi bir terminal açın; bugünün her kod parçası tam olarak gösterildiği gibi derlenir ve çalışır.
Konuşma notu: Bir ağaç düğümü, bir işaretçi alanı daha fazla olan bağlı liste düğümüdür — yeni olan gerçekten bu kadar.
Konuşma notu: Bellek konusunda bugün yeni bir şey yok — yalnızca aynı işaretçi ve yığın/kuyruk fikirlerinden kurulu yeni biçimler var.
Konuşma notu: Bu haritadaki her kutu aşağıda kendi slaytlarını alıyor, çoğu kısa bir animasyon ve eksiksiz bir C/Java programıyla.
Konuşma notu: Bölüm 1, sonraki her bölümün üzerine kurulduğu terimleri — kök, ebeveyn, çocuk, yaprak, derinlik, yükseklik — bir düğümün istediği sayıda çocuğu olabildiği genel bir ağaçta kuruyor.
Konuşma notu: Sorun: bu biçim bir yığın mı, bir kuyruk mu, yoksa yeni bir şey mi? Dallanıyor — bugünün tüm yeniliği bu.
Konuşma notu: Cayley bilgisayarı hiç düşünmüyordu — hidrokarbon izomerlerini sayıyordu, dallanma yapıları tam olarak bir ağaç.
Konuşma notu: "Kök neden en üstte" diye sorun — bir doğa kanunu değil, ama bu alanda tamamen evrensel bir gelenek.
Konuşma notu: Bu tablodaki her terim, hemen sonraki animasyonda, sırayla, gerçek bir ağaç üzerinde işaret ediliyor.
Konuşma notu: n-1 kenar üzerinde durmaya değer: kök hariç her düğümün tam olarak bir kenarı var, kendi ebeveynine.
Konuşma notu: Derinlik kökten aşağı sayar; yükseklik bir düğümden en derin yaprağına aşağı sayar — sayma yönü kafa karıştıran şey.
Konuşma notu: Normal örnek: 11 düğümlü dallı bir ağaç. Her terimin aynı gerçek ağaç üzerinde, sırayla, nasıl yanıp söndüğünü izleyin.
Konuşma notu: Yıldız "derece"yi en zorlu şekilde sınar: derecesi 10 olan bir düğüm, her biri derecesi 0 olan on yaprak, ve yüksekliği yalnızca 1 olan bir ağaç.
Konuşma notu: Bunu Hafta 2'nin bağlı liste düğümüyle karşılaştırın: aynı fikir, ama children artık bir dizi, çünkü genel bir ağaç düğümünün birden fazla çocuğu olabilir, tek bir "next" değil.
Konuşma notu: Bir yaprağın yüksekliği taban durumu, 0; başka her düğüm 1 + en yüksek çocuğu — kuyruk gerekmez, saf özyineleme.
Konuşma notu: Derinlik önce ebeveynin cevabına ihtiyaç duyar, o yüzden bir kuyrukla yukarıdan aşağı yürür — height'ın aşağıdan yukarı özyinelemesinin ayna görüntüsü.
Konuşma notu: Biçim, bu hafta ilerledikçe, toplam iş değil de özyineleme *derinliği* söz konusu olunca çok önem kazanacak.
Konuşma notu: İkili sınırlama tam olarak bir sonraki bölümde başlıyor, ve bu bir doğa kanunu değil, hilelerinden ötürü yaptığımız bir seçim.
Konuşma notu: Sonraki slayttan önce her iki cevabı da sınıfa sordurun.
Konuşma notu: Derinlik, kökten her seviye aşağı inildiğinde tam olarak bir artar — kısayol yok, istisna yok.
Konuşma notu: Bir sınırlama — en çok iki çocuk, left ve right adıyla — öbeği, Huffman kodlamasını ve gelecek dönemin arama ağaçlarını açıyor.
Konuşma notu: Karşılığı, dizi indisleri üzerinde bölüm 4'ün tanıtacağı aritmetik hileler — sınırsız çocukla imkânsız.
Konuşma notu: Bu haftanın kalan her programı tam olarak bu struct'ın üzerine kuruluyor — bağlı liste düğümünden bir işaretçi fazla.
Konuşma notu: Bunlar beş bağımsız evet/hayır sorusu — bir ağaç tam olmadan dolu olabilir, ya da tersi.
Konuşma notu: Normal örnek: 12 düğüm, tam ama mükemmel değil. Animasyon aynı ağaç üzerinde beş evet/hayır sorusunu da soruyor.
Konuşma notu: Dejenere bir ağaç dolu, tam ve mükemmelin hepsinde birden başarısız, ve yüksekliği n-1 — düz bir bağlı liste kadar kötü.
Konuşma notu: Bu iki formül sürekli geri geliyor — bölüm 5'teki öbek ikisine de dayanıyor.
Konuşma notu: Denge, gelecek dönem ikili arama ağaçlarını rastgele değil dikkatle kurmaya değer kılan tek sebep.
Konuşma notu: Bu, bir kuyrukla seviye seviye yürür, bilerek NULL yer tutucular ekler, ki boşluktan sonra gerçek bir düğüm yakalanabilsin.
Konuşma notu: Tek bir gözcü değer, -1, "artık dengesiz" bilgisini özyineleme boyunca yukarı taşır, aynı altağacı iki kez gezmeden.
Konuşma notu: h yükseklik, ve dejenere bir ağacın O(n) yığın alanı tam olarak bu yüzden en kötü durum.
Konuşma notu: Yukarıdaki tek geçişli check_balance, tam olarak bu çok yaygın tuzağı önlemek için var.
Konuşma notu: İki slayt öncesindeki formülleri kullanın.
Konuşma notu: Her mükemmel ağacın yaprak sayısı, toplam düğümünün yaklaşık yarısı — iyi bir sağlık kontrolü.
Konuşma notu: Bir ağacın tek "doğal" bir sırası yok — düğümün iki çocuğu var, o yüzden hangisinin önce ve düğümün kendisinin ne zaman ziyaret edileceğine dair gerçek bir seçim var.
Konuşma notu: Aşağıdaki beş program aynı 10 düğümlü dengeli ağacı paylaşır: [50,30,70,20,40,60,80,10,-,-,45,55] — değişen yalnızca ziyaret sırası.
Konuşma notu: Diziyi geri okurken, okunan ilk değer her zaman bir sonraki altağacın köküdür.
Konuşma notu: Vurgulanan çağrı yolunun kökten şu an etkin olan çağrıya kadar izlediği rotayı gözlemleyin.
Konuşma notu: Yalnızca sol çocuklarla, preorder zincirin kurulduğu sırayla ziyaret eder — her zaman ziyaret, sonra tek çocuk.
Konuşma notu: Önce ziyaret, sonra sol, sonra sağ — taban durum, node == NULL, ilk sırada olmalı, yoksa boş bir altağaçta çöker.
Konuşma notu: Bu gösterim ağaçlarında, BST kurallarıyla kurulmadıkları için, inorder yine de sol-önce-kendi-sonra-sağ çalışır; sadece sıralanmış çıkmaz.
Konuşma notu: Normal ağaçta, [50,30,70,...], inorder tam olarak sıralı çıkıyor: 10 20 30 40 45 50 55 60 70 80.
Konuşma notu: Yalnızca sağ çocuklarla önce ziyaret edilecek sol altağaç yok, o yüzden inorder tam olarak zincirlenme sırasında çıkar — sola yığılmışın tersi.
Konuşma notu: preorder ile tıpatıp aynı biçim — yalnızca "visit" satırının yeri, ilk yerden ortaya, değişiyor.
Konuşma notu: Bir düğümün çocuklarını, düğümün kendisinden önce serbest bırakın, yoksa serbest bırakılmış işaretçilere tekrar ihtiyaç duyarsınız.
Konuşma notu: Bu koşunun ilk ve son yazdırılan değerlerini preorder'ınkiyle karşılaştırın — burada kök son, orada ilk.
Konuşma notu: Sol altağaç olmadan, postorder yine "kendini son ziyaret et"i saklar, o yüzden sağ zincir tam ters sırayla çıkar.
Konuşma notu: Her zamanki üç satır, yalnızca sona taşınmış — ziyaret, sol, sağ; sol, sağ, ziyaret oluyor.
Konuşma notu: Üçü arasında değişen tek şey "ziyaret, sol, sağ"ın sırası; toplam iş asla değişmiyor.
Konuşma notu: Üçü de "her düğümü ziyaret eder", o yüzden yanlış seçim yine de çalışır — hata yalnızca sıra önem kazandığında ortaya çıkar.
Konuşma notu: Hangi değerin ilk okunması gerektiğini düşünün.
Konuşma notu: Bu tam olarak preorder slaytlarının başındaki "sıfırdan kurmak" özelliği.
Konuşma notu: Tüm sol omurgayı push edin; artık sola gidemeyince pop edin, ziyaret edin, sonra sağ altağaca yürüyün ve tekrarlayın.
Konuşma notu: Sol omurga push edilirken yığının büyüdüğünü, sonra her pop'ta bir düğüm ziyaret edildikçe küçüldüğünü izleyin.
Konuşma notu: 10 düğümün hepsi tek biri pop edilmeden önce push edilir — yığın derinliği zincirin tamamına eşit.
Konuşma notu: Hafta 3'ün tam olarak aynı dizi tabanlı yığını — yalnızca eleman türü int'ten Node *'a değişti.
Konuşma notu: Tüm sol omurgayı push edin, pop edip ziyaret edin, sonra sağa adım atıp tekrarlayın — dış while'ın her iki yarısı da önemli.
Konuşma notu: Çok derin, dejenere bir ağaç özyinelemeli çağrı yığınını çökertebilir; kendi dizi tabanlı yığınımız daha nazikçe biter.
Konuşma notu: Bu döngü koşulunun her iki yarısı da önemli — ilkini atlarsanız çok erken durursunuz, ikincisini atlarsanız sonsuza kadar döner.
Konuşma notu: Yığının o an tam olarak hangi düğümleri tuttuğunu düşünün.
Konuşma notu: 0'dan h'ye kadar derinlikler, dahil — bu h+1 düğüm, hiçbir zaman daha fazla değil.
Konuşma notu: Kuyruğa eklenen ilk düğüm, kök, işlenen de ilk olmalı — bu tam olarak FIFO, bir yığın yanlış sıra verirdi.
Konuşma notu: Bir sonraki derinlik başlamadan önce her derinliğin tamamen bittiğini izleyin — 50, sonra 30 ve 70, sonra dört torun.
Konuşma notu: Burada her düğümün tek çocuğu var, o yüzden hiçbir derinlikte birden fazla düğüm hiç yok — kuyruk 1 boyutunu asla geçmiyor.
Konuşma notu: Hafta 3'ün tam olarak aynı dairesel kuyruğu — rear -1'den başlar ki ilk enqueue doğru şekilde 0. indise otursun.
Konuşma notu: Bölüm 2'nin tamlık kontrolünün tersine, bu döngü asla NULL eklemez — iki kuralı bir arada karıştırmak klasik bir hata kaynağı.
Konuşma notu: Derinlik öncelikli dolaşmalar genişliği derinlikle takas eder; level order derinliği genişlikle — hiçbiri bedava değil.
Konuşma notu: Kod her iki durumda da derlenir ve çalışır; hatayı yalnızca gerçek ziyaret sırası ortaya çıkarır.
Konuşma notu: Tek başına bir level-order dizisinin hangi düğümün kimin çocuğu olduğunu söyleyip söylemediğini düşünün.
Konuşma notu: Bir preorder-artı-inorder çifti birlikte belirli bir ağacı belirler; tek başına bir level-order dizisi belirlemez.
Konuşma notu: Tam olarak tam bir ağaç için, bir indis üzerinde aritmetik her işaretçinin yerini alır — hiç malloc yok, hiç left/right alanı yok.
Konuşma notu: Var — ve bu tam olarak bölüm 5'teki ikili öbeğin kurulu olduğu gösterim.
Konuşma notu: Üç formül gösterimin tamamı; her şey tek bir düz dizi üzerinde saf aritmetik.
Konuşma notu: Normal örnek: 12 düğüm, tam, hiç boşluk yok — her formül resmin söylediği yere tam olarak iniyor.
Konuşma notu: İndis 9 ve 10 boş ama indis 11 dolu — boşluktan sonra tek bir gerçek düğüm, tamlığı tamamen bozmaya yeter.
Konuşma notu: Üç tek satırlık formül, sonra bir döngü: son gerçek düğümden önceki herhangi bir boş slot, tamlığın hayır olması demek.
Konuşma notu: O(1) çocuk/ebeveyn erişimi, dizi gösteriminin tüm amacı — ve öbeğin bir sonraki bölümde tam olarak ihtiyaç duyduğu şey.
Konuşma notu: Formüller her durumda *bir* indis hesaplar; tam olmayan bir ağaçta o indis anlamsız olabilir.
Konuşma notu: Birkaç slayt öncesindeki üç formülü uygulayın.
Konuşma notu: Aynı üç formül, her zaman, ağaç ne kadar büyük olursa olsun.
Konuşma notu: İkili öbek, bölüm 4'ten tam bir ağaç, tek bir ek kuralla: her ebeveyn her iki çocuğunu da yeniyor.
Konuşma notu: Her gelişte sıralamak, geliş başına O(n log n) maliyetli — bu kadar sık bir şey için çok yavaş.
Konuşma notu: Her iki makale de aynı yıl çıktı — öbek ve öbek sıralaması hiçbir zaman gerçekten ayrı fikirler değildi.
Konuşma notu: Öbekler hakkında en yaygın yanlış anlama bu: bir öbek sıralı bir dizi değil, yalnızca kısmen sıralı.
Konuşma notu: Dört işlem, ve sonraki dört alt bölüm tam olarak bu dördünü, bu sırayla kuruyor.
Konuşma notu: Özellik sağlandığı ya da değer köke ulaştığı an durun — hangisi önce gelirse.
Konuşma notu: Normal örnek: bir min-öbek, sırayla eklenen 10 değer: 15, 7, 22, 3, 18, 9, 30, 1, 25, 12.
Konuşma notu: Bir min-öbeğe artan 12 değer: her ekleme öbek özelliğini zaten sağlıyor, o yüzden tek bir yer değiştirme bile olmuyor.
Konuşma notu: better(), min-öbek ile max-öbeği bir fonksiyon arkasına gizler, o yüzden sift-up döngüsünün kendisi hiç değişmez.
Konuşma notu: Boyut değil yükseklik, insert'in maliyetini belirler — bölüm 2'nin "denge neden önemli" fikri işbaşında.
Konuşma notu: Önce boyutu bir azaltın, sonra sift edin — taşınan eleman genellikle kökte hiç durmaz.
Konuşma notu: Normal örnek: bir min-öbek, 12 değer, 3 çıkarma — son elemanın köke paraşütle inip sonra geri battığını izleyin.
Konuşma notu: 10 değerin hepsini birer birer çıkarmak, tamamen sıralı bir sonuç veriyor — bu bir tesadüf değil, öbek sıralamasının tam kendisi.
Konuşma notu: Yalnızca sol çocukla değil, her ikisiyle de karşılaştırın — tek tarafla karşılaştırmak diğer tarafta özelliği bozuk bırakabilir.
Konuşma notu: insert en çok log n seviye tırmanır; extract en çok log n seviye batar — yükseklikler, yine, her şeyi belirler.
Konuşma notu: Boş bir öbekte extract, heap[-1] bitişiği belleği sessizce okur — güvenli bir çökme değil, tehlikeli bir hata.
Konuşma notu: Bu gerçekten şaşırtıcı bir sonuç — kurma, n ekleme kadar maliyetli görünür ama değil.
Konuşma notu: Normal örnek: bir max-öbek, rastgele sırada 10 değer — n/2 yapraktan kaçının hiç hareket ettiğini izleyin.
Konuşma notu: Her sift-down çağrısı target == i'yi hemen bulur ve hiçbir şey yapmaz — build_heap, girdinin gerektirdiği kadar iş yapar, ne fazla.
Konuşma notu: sift_down burada extract'in sift-down döngüsünün ta kendisi; yeni olan tek şey hangi düğümlerin, hangi sırayla çağrıldığı.
Konuşma notu: Bu, tüm haftanın gerçekten şaşırtıcı tek karmaşıklık sonucu — bir süre üzerinde durmaya değer.
Konuşma notu: Döngü sondan köke, geriye doğru çalışmalı, ki her düğüm sift edildiğinde altağaçları zaten geçerli olsun.
Konuşma notu: Her sift-down çağrısının ağaçta nereden başladığını düşünün.
Konuşma notu: Aynı fonksiyon, sift_down, iki çok farklı örüntüde çağrılıyor, iki çok farklı toplam maliyetle.
Konuşma notu: build_heap ve extract ikisi de var olduğunda, sıralamak neredeyse bedava — bu bölüm ikisini birbirine bağlıyor.
Konuşma notu: Normal örnek: bir max-öbekle artan sıralama, 10 değer — sıralı bölgenin dizinin sonundan geriye büyümesini izleyin.
Konuşma notu: build-heap'in tersine, öbek sıralaması adaptif değil — zaten sıralı bir girdi yine de tam O(n log n) maliyetli, yer değiştirme yer değiştirmesine.
Konuşma notu: Az önceki aynı build_heap döngüsü, sonra n-1 tur yer değiştirme-ve-sift, her biri küçülen bir bölgede.
Konuşma notu: Birleştirme sıralaması ya da hızlı sıralamanın ortalama durumuyla aynı asimptotik sınıf, ama ekstra bellek gerekmeden.
Konuşma notu: Kararlı bir sıralama gerekiyorsa, öbek sıralaması iyi karmaşıklığına rağmen yanlış araç.
Konuşma notu: Bir kuyruk ilk gelene hizmet eder; bir öncelik kuyruğu, geliş sırası ne olursa olsun, en önemliye hizmet eder.
Konuşma notu: Burada gerçekten yeni bir şey yok — bölüm 5'teki öbek, bir öncelik kuyruğunu gerçekleştirmenin en yaygın yolu.
Konuşma notu: update_key gerçekten yeni tek işlem, ve her öğenin kalıcı bir id'ye ihtiyaç duymasının tek sebebi.
Konuşma notu: Her öğe kalıcı bir id ister, dizide nereye taşınırsa taşınsın değişmeyen — yoksa update_key onu bir daha bulamaz.
Konuşma notu: Normal örnek: min-öncelik, 10 insert, bir peek, 2 extract, bir update-key — bölüm 5'in heap-insert'iyle aynı 15,7,22,3,18,... değerleri.
Konuşma notu: Öbek işlemlerinin kendisi değil, çağıran taraf size > 0 kontrol eder — bu senaryo, o kontrolün taşmayı güvenle yakaladığını gösteriyor.
Konuşma notu: Artık her öğe key'inin yanında kalıcı bir id taşıyor — öğenin dizideki slotu değişse de id hiç değişmiyor.
Konuşma notu: find_by_id burada doğrusal bir tarama — gerçek bir sistem id'den indise bir hash tablosu ekler, bunu da O(log n) yapmak için.
Konuşma notu: Bu ekstra muhasebe, klasik bir alan-zaman takası — binlerce öğe devrede olduğunda buna değer.
Konuşma notu: Decrease-key yukarı sift ister; increase-key aşağı sift ister — yanlışını kullanmak öbeği sessizce bozar.
Konuşma notu: Min-öncelik kuyruğunda "daha acil"in key'in sayısal değeri için ne anlama geldiğini düşünün.
Konuşma notu: Min-öncelik kuyruğunda küçük her zaman daha iyidir — bölüm 5'in min-öbeğiyle aynı kural.
Konuşma notu: Aşağıdaki her varyasyon, düz ikili öbeğin bir özelliğini gevşetiyor ya da değiştiriyor, farklı bir kazanç karşılığında.
Konuşma notu: Büyük bir D, insert'i ucuzlatır (daha az seviye, seviyede bir karşılaştırma) ama extract'i pahalılaştırır (seviyede D'ye kadar karşılaştırma).
Konuşma notu: Normal örnek: D=3, bir min-öbek, 12 değerden 3 çıkarma — her sift-down'ın aynı anda 3 çocukla karşılaştığını izleyin.
Konuşma notu: 10 değerin hepsi birer birer çıkarılıyor — yine tamamen sıralı çıkıyor, düz ikili öbeğin sonuna kadar durumu gibi.
Konuşma notu: base = D*i+1, ikili öbeğin 2*i+1'inin yerini alıyor — extract'in her diğer satırı tıpatıp aynı biçimde kalıyor.
Konuşma notu: Ekleme ağırlıklı iş yüklerinde, ağ olayı zamanlayıcıları gibi, popüler — extract nispeten seyrek olduğunda.
Konuşma notu: 2*i+1 ve 2*i+2, D*i+1+c'nin yalnızca D=2 özel durumu — yanlış D koyarsanız yanlış dizi hücresine dokunulur.
Konuşma notu: 13 = 0b1101, dereceleri 0, 2 ve 3'e ayrışır — 1, 4 ve 8 büyüklüğünde ağaçlar, toplamda 13.
Konuşma notu: Bu "üç ağaç aynı anda" durumu, animasyondaki zor senaryonun tam olarak sınadığı şey.
Konuşma notu: Normal örnek: min, A'nın 7 elemanı var (dereceler 0,1,2), B'nin 5 (dereceler 0,2) — eldelerin yukarı dalgalanmasını izleyin.
Konuşma notu: A (derece 3) union B (derece 3): tek bir elde her derecede dalgalanıyor — ikilik tabanda 1000 + 1000 toplamak gibi.
Konuşma notu: link(), daha kötü olan kökü daha iyi olanın yeni en soldaki çocuğu yapar — O(1), yalnızca birkaç işaretçi güncellemesi.
Konuşma notu: Düz bir ikili öbeğin insert'i de O(log n), ama tamamen farklı bir sebeple: sift-up, linkleme değil.
Konuşma notu: insert, ezberlenecek ayrı bir algoritma değil — tam olarak tek elemanlı bir ikinci öbekle union_heaps.
Konuşma notu: insert, yeni bir düğümle merge; extract, kökün kendisi silindikten sonra iki çocuğunun merge'ü.
Konuşma notu: Ağacın kendisi çok dengesiz olabilir — yalnızca sağ omurganın kısa olması garanti, ve merge yalnızca o omurgada yürür.
Konuşma notu: Normal örnek: min, A'nın 5 elemanı, B'nin 6 — merge'ün her iki sağ omurgayı nasıl birleştirip sonra npl'leri düzelttiğini izleyin.
Konuşma notu: A boş, 11 elemanlı B ile birleşiyor — merge'ün iki taban durumu (t1 == NULL, t2 == NULL) bunu hemen çözer.
Konuşma notu: Daha iyi kök her zaman kazanır ve diğer ağacı kendi sağ tarafına yutar, sonra yer değiştirme solcu özelliği onarır.
Konuşma notu: Yalnızca sağ omurganın uzunluğu önemli, ve solcu özellik onun her zaman kısa olmasını garanti eder.
Konuşma notu: O yer değiştirmeyi atlarsanız, tüm O(log n) kısa-sağ-omurga garantisi sessizce geçerliliğini kaybeder.
Konuşma notu: Hangi yapının iki bütün öbeği birleştirmek için hiç hızlı bir yolu olmadığını düşünün.
Konuşma notu: Düz bir dizi öbeğin tek birleştirme yolu, bir öbeğin her elemanını tek tek diğerine eklemek.
Konuşma notu: Bu haftanın kurduğu her şeyin ödülü: yalnızca ağaçlardan bir öbek, optimal bir sıkıştırılmış kod üretiyor.
Konuşma notu: Sorun: karışık uzunluklu kodlar bir bit akışında belirsiz olabilir, çok özel bir özellik olmadan.
Konuşma notu: Hocası sınıfa bir seçim sundu: final sınavı, ya da kanıtlanabilir optimal bir önek kodu bulmak — Huffman birini buldu.
Konuşma notu: Nadir semboller erken birleşir, altta kalır; sık semboller geç birleşir, üstte kalır — kısa kodları veren tam olarak bu.
Konuşma notu: Normal örnek: İngilizce harf benzeri sıklıklarla 10 sembol — en küçük iki kökün tekrar tekrar birleşmesini izleyin.
Konuşma notu: Yalnızca 2 sembol: bir birleşme, bir kök, bitti — "bir ağaç kur"un bile bir anlam taşıdığı en küçük girdi.
Konuşma notu: heap_pop/heap_push, tam olarak bölüm 5'in min-öbek extract/insert'i — sayı yerine Node işaretçilerini sıralıyor.
Konuşma notu: Her sembol tam olarak bir yaprak, ve bir yaprağın çocuğu yok — o yüzden hiçbir kod başka birinin öneki olamaz.
Konuşma notu: Normal örnek: "ABRACADABRA", 11 karakter — 88 düz-ASCII bit 23'e düşüyor, çünkü A tek başına 11 karakterin 5'i.
Konuşma notu: Yalnızca 2 sembol kaldı, o yüzden karakter başına 1 bit mümkün olan en iyisi — 80 yerine 10 bit, sıklıklar ne kadar çarpık olursa olsun.
Konuşma notu: Yalnızca yapraklar bir kod kaydeder; her iç düğüm yolu yalnızca bir 0 (sol) ya da 1 (sağ) ile uzatır.
Konuşma notu: Bit başına bir ağaç adımı; bir yaprağa ulaşılan an, karakterini üretin ve yürüyüşü kökten yeniden başlatın.
Konuşma notu: L metnin karakter uzunluğu; B kodlanmış mesajın bit uzunluğu.
Konuşma notu: Kod açıcı her zaman ya ağacın kendisine ya da sıklık tablosuna, kodlanmış bitlerin yanında, ihtiyaç duyar.
Konuşma notu: Bir yaprağın ağaçtaki konumunun neye izin verip neye izin vermediğini düşünün.
Konuşma notu: Bu "önek-serbest" özellik, tam olarak tek geçişli, belirsizliksiz kod açmayı mümkün kılan şey.
Konuşma notu: Aynı ağacı ziyaret etmenin beş yolu, ve tam olan birini tek bir işaretçi olmadan saklamanın bir yolu.
Konuşma notu: Bu beş satırın her biri, aynı iki hareketten kurulu: sift-up ve sift-down.
Konuşma notu: Bir öğrenci bugünden tek bir cümle hatırlayacaksa, hatırlamaya değer olan bu.
Konuşma notu: Bunlar yazılı notların sonundaki kendini sınamayı yansıtıyor, burada daha kısa bir setle, slayt başına bir soru.
Konuşma notu: Sorun, bekleyin, sonra ilerleyin.
Konuşma notu: Bölüm 2'deki aynı formül, yalnızca h = 4 ile.
Konuşma notu: Bölüm 4'teki formülü uygulayın.
Konuşma notu: Aynı formül, her zaman, ağacın boyutu ne olursa olsun.
Konuşma notu: Bölüm 5.5'teki yükseklik-ağırlıklı toplamı hatırlayın.
Konuşma notu: Üstteki az sayıda maliyetli sift, alttaki çok sayıda ucuz olanın altında eziliyor.
Konuşma notu: Neredeyse her işlemde neyin değiştiğini hatırlayın.
Konuşma notu: update_key, "bu belirli öğe"yi, o an nerede oturduğuna bağlı olmadan bulacak bir yola ihtiyaç duyar.
Konuşma notu: update_key tam olarak bunun için kuruldu: "en yakın öğeyi tekrar tekrar çıkar, sonra belki başka bir öğenin önceliğini düşür."
Konuşma notu: Bunlar, haftanın yazılı notlarının sonundaki aynı kaynaklar.
Konuşma notu: Tarihsel kaynaklar — Huffman, Williams, Floyd, Vuillemin, Cayley — bugünün "kısa tarihçe" slaytlarının dayandığı yer.