MIT Açık Ders malzemeleri

http://ocw.mit.edu

6.046J Algoritmalara Giriş, Güz 2005

Bu materyallerden alıntı yapmak veya kullanım şartları hakkında bilgi almak için:

Erik Demaine ve Charles Leiserson, 6.046J IntroductiontoAlgorithms, Fall 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (Giriş Tarihi: 08, 01, 2010). Lisans: Creative CommonsAttribution-Noncommercial-ShareAlike.

Not: Lütfen atıf taparken bilgilere eriştiğiniz gerçek tarihi kullanınız.

Atıflar ve Kullanım Koşulları konusunda daha fazla bilgi için:

http://ocw.mit.edu/terms ve http://www.acikders.org.tr sitesini ziyaret ediniz.

Ders 11

Günaydın. Bugün veri yapılarının genişletilmesi konusunda konuşacağız. Bu bağlamda yeni veri yapılarını sıfırdan tasarlamak yerine mevcut veri yapılarını alıp bunların içine kendi işlevselliğinizi işlersiniz. Ve bu sürece biz veri yapılarının geliştirmesi diyoruz. Ve bugün biz bu sınıfta artık tasarım bazına adım atacağız. Bugüne kadar hep çözümleme konusunda çok zaman geçirdik. Bundan sonrada yeni analitik teknikleri öğrenmeye devam edeceğiz.

Bugün daha verimli veri yapılarının nasıl tasarlanacağına, çeşitli problemler için verimli algoritmaların nasıl kuramlanacağına odaklanacağız. Yani bu aslında tasarım adımının iyi bir örneği olacak. Bu evrede eğer bugüne kadar yapmadıysanız, kitabın sona eklenen bölümü yani Appendix B’yi tekrarlamanız iyi bir fikir olur. Bu konuyu ek okuma olarak değerlendirip aşina olmanız lazım, çünkü bundan sonraki birkaç haftada Appendix B’ye hemen her konuya değineceğiz.

Bu sona eklenen bölümde bizim burada konuştuğumuz konuların hemen hepsi işleniyor. Eğer gelecekte bir taraftan yeni bilgileri öğrenirken aynı zamanda da kitapları karıştırmaya çalışırsanız, bu iş bu bilgileri bugün öğrenmenizden daha ağır olacaktır. Dinamik sıra istatistikleri konusunda bir problemim gösterimi ile işe başlayacağız. Aslında “ortalama bulma” yı yada “k’nıncı düzey istatistiği” gibi şeyleri bulmayı biliyoruz. Şimdi buna benzer şeyler yapacağız ama bu sefer dinamik bir set kullanarak yapacağız. Bütün verileri işin başında vermekten ziyade elimizde bir set olacak ve ondan sonraki bir evrede birileri tipik bir araya yerleştirme ya da silme işlemi yapacak ve sonrada yine birileri diyecek ki benim için “bu dinamik setin içinden i’ninci en büyük ya da i’ninci en küçük öğeyi seç”.

Ya da “x’ in OS rankını istiyorum” denilecek; Yani x’ in sıralanmış setin içinde rankını yani sırasını istiyor. Örneğin, n elemanı olan bir setin içerisinde ben n/2’yi verirsem, bu durumda ortancayı istiyorum demektir. Ortalamayı da soruyor olabilirim. Dörtte biride soruyor olabilirim. Buradan bir eleman alıp tamam şimdi bu eleman setin içindeki diğer elemanların arasında nereye düşüyor diye de sorabilirim. Ve ek olarak bunlar dinamik setler olduğundan, bunlara araya yerleştirme ya da silme işlemini uygulamak, yani bunlara eleman ekleme yada eleman çıkarma uygulaması da yapmak isteyebilirim. Bu sorunun çözümüne giderken kullanacağımız yol aslında alt ağaçların boyutlarını bir “kırmızı siyah” ağacın düğümleri içinde muhafaza etmektir. Örnek olarak bir resim çizeyim. Bu ağaçta ağacın içindeki boş düğümleri çizmedim. Onlar zaten “siyah”. İki değeri muhafaza edeceğim. Anahtarları muhafaza edeceğim. Ve anahtar olarak ta alfabemizdeki harfleri kullanmak istiyorum.

Ve bu bir “kırmızı siyah” ağaçtır. Pratikte bunun “kırmızı siyah” bir ağaç olduğunu göstermek için bunu nasıl etiketlendirebilirim? Sıfırları göstermedim. Sıfırların hepsinin siyah olduğunu unutmayın. Bunu nasıl etiketlendirebilirim; kırmızı ve siyah? Önerinizi yaparken bunun kırmızı siyah bir ağaç olduğundan emin olun her ağaç kırmızı siyah ağaç olarak etiketlendirilemez mi? Bu aslında iyi bir pratik çünkü bu tip şeyler testlerde karşınıza çıkacak. F’yi kırmızı yapın, güzel ve onun dışındaki her şey siyah olsun. Bu uygun bir çözüm olabilir. Çünkü bu temelde bu öğenin seviyesini şuraya çıkarır.

Aslında bundan daha karmaşık bir tane vardı ve bana daha eğlenceli gibi gelmişti. Önce bunu siyah yaptım. Sonra şu iki elemanı kırmızı yaptım; siyah, kırmızı, siyah, kırmızı, siyah ve siyah yaptım. Ama sizin çözümünüz de gerçekten iyidir. Yani aynı hat üzerinde iki kırmızının arka arkaya gelmemesi lazımdır. Ve siyah yükseklik konusunda da herhangi bir noktadan aşağıya doğru inerken aynı sayıda siyahla karşılaşmamız lazım; hangi yoldan gidersek gidelim. İyi. Buradaki fikir,alt ağaç boyutlarını “kırmız siyah” ağacında tutacağız. Bunlar aslında dinamik setimizin içinde depoladığımız anahtarlarımızdır ve biz alt ağaç boyutlarını ağacın içinde hiç değiştirmeyeceğiz. Örneğin, bunun boyutu 1’dir. Bunların boyutu da 1’dir çünkü bunların hepsi yaprak.

Sonra yukarıya doğru çalışmaya başlayabiliriz. Bunun boyutu 3, şunun boyutu 5, bunun boyutu 3,ve buda 5+3+1 yani 9 ediyor. Genelde x’in boyutu eşittir, x’in sol ardılın boyutu artı x’in sağ ardılının boyutu artı 1 olur. Bunu özyinelemeli olarak hesaplamanın yolu budur. Boyutun hesaplanmasında oldukça basit bir formüldür. Bu uygulamayı yapmak için yazacağımız kodda, boş düğümün yani NIL’in boyutu konusunda da konuşmamız uygun olacaktır.

NIL’in boyutu nedir? Sıfır. Boşun boyutu içinde hiçbir eleman yoktur. Ama birçok programlama dilinde ben boşun boyutunu alırsam ne olacaktır? Bir hata oluşur. Bu çok uygun bir şey değildir. Bu durumda kodumu yazarken boşun boyutuyla ilgilenmem gerekiyorsa veya herhangi bir şeyin boyutunu almam gerekiyorsa derim ki eğer bu NİL ise o zaman sıfır döndür değilse, o zaman boyut alanının kendisini döndür vs. Bunu basitleştirmek için kullanacağımız bir uygulama hilesi var. Buna sentinel yani gözcü denir.

Bir gözcü, kurmaca bir kayıttan başka bir şey değildir. Sıfırı kullanmak yerine uygulamada NIL yani NİL gözcüsü kullanacağız. NİL için bir kurmaca kayıt kullanacağız ve bunun da boyutu sıfıra eşit olacak. Bu durumda ağacın içinde NIL’i kullanabileceğim herhangi bir yerde adına NIL diyeceğim özel bir kayıt olacak. Ama bu tam bir kayıt olacak. Ve böylece bunu boyut alanını sıfıra ayarlayacağım ve bunu herhangi bir özel durum gibi değerlendirip kontrol etmeme gerek kalmayacak. Bu programcılıkta çok sık görülen bir hiledir ve gözcüler kodun basitleştirilmesi için kullanılır. Böylece sınır durumlarında veya istediğim sadece bir şeyin boyutunu indekslemekse ekstra bir fonksiyon yazmaya gerek kalmaz. Bu konuda herkes benimle beraber mi?

Şimdi bu tanımlamanın ardından büyük OS-Select(x, i) yani OS-seçme kodunu yazalım. Bu bize kökü x olan alt ağacın en küçük i’inci elemanını verecektir. Aslında bundan biraz daha genel olacaktır. Eğer büyük OS-seçme i’sini yukarıda uyarlamak istersem, o zaman ona kök (n, i)’yi veririm. Ama biz bu işlemi özyinelemeli olarak yapacağız, bu nedenle bulmak istediğimiz alt ağacın içindeki düğümle ilgilenmek daha uygun olacaktır. Kodu şöyle olur.

Bu kodudur. Önce bunun nasıl işlediğine bakalım sonrada neden işlediğini tartışalım. Örnek olarak OS-Select (root,5) kök ve 5 için yapalım. Biz setin içindeki en büyük 5’inci elemanı bulacağız. Elimizde kökün OS-Select var ve 5 var. Bu uygun değil. Yukarıdan başlarız ama şimdilik şu tahtaları değiştireyim. Evet işte böyle yukarıdan başlarız ve i bizim kökümüzdür. Af edersiniz yanlış söyledim. i, 5’e eşit evet i=5. Biz burada 5’inci büyük elemanı bulmak istiyoruz.

Önce bu k değerini hesaplarız. k, x’in solunda kalanların boyutu artı 1’dir. Bu değer nedir? Yani k nedir? Bu nedir? Evet bu durumda 6’dır, güzel. Ama k’nın anlamı nedir? Düzeydir, ranktır; güzel şu andaki düğümün rankıdır. Bu şu andaki düğümün rankıdır. k her zaman soldaki alt ağacın boyutu artı 1’dir. Buda mevcut düğümün rankıdır. Buraya bakarız ve deriz ki bizim rankımız k. Şimdi eğer bu bizim istediğimize eşitse, deriz ki aradığımız elemanı bulduk.

Eğer başka bir sonuç çıkarda i daha küçük olursa, o zaman bunun soldaki alt ağaçta olduğunu biliriz. Bu durumda yapacağımız şey soldaki alt ağaçta özyineleme yapmaktır. Ve biz burada özyineleme yapacağız. Biz en büyük beşinci elemanı istiyoruz. Ve şimdi k neye eşit olacak? İki.Şimdi burada deriz ki,“tamam bu daha büyük öyleyse istediğimiz eleman sağdaki alt ağaçta olacaktır”. Ama sağdaki alt ağaçtaki en büyük i’ninci elemanı istemiyoruz. Çünkü biz şurada zaten iki elemanın olduğunu öğrendik. Bu durumda bu alt ağaçtaki üçüncü en büyük elemanı istiyoruz. Bu alt ağaçta özyineleme yaparken i’miz 3’ e eşit olacak. Ve şimdi k’yı burada hesaplayacağız. Bu artı 1, 2 eder.

Ve bu bize tam burada özyineleme yaptığımızı söyler. Ve i = 1, k = 1 olur ve biz kodumuzun içinde bir işaretleyiciyi bu düğüme yönlendiririz. Böylece bu H’yi içeren düğüme bir işaretleyici döndürür. Burada bir şey söylemek gerekirse biz k’nın x’in rakına eşit olduğunu keşfettik. Bu kodda neler olup bittiği hakkında herhangi bir soru var mı? Tamam. O kendi yolunu aşağıya doğru buluyor. Alt ağaçların boyutları bu kararı vermesinde ona yardımcı olup i’ninci büyük elemanı bulmak için hangi yolu takip etmesi gerektiğini gösteriyor. Burada hızlı bir çözümleme yapabiliriz. Bizim kırmızı siyah ağacımızda OS-SELECT işlemesi ne kadar sürer? Evet, evet O(log n) düzeyinde; tabii eğer ağaçta n eleman varsa.

Çünkü “kırmızı siyah” ağaç dengeli bir ağaçtır; yüksekliği (log n) düzeyindedir. Aslında bu kod yüksekliği (log n) düzeyinde olan herhangi bir ağaçta çalışır. Yani eğer “kırmızı siyah” ağaçlarda olduğu gibi garantili bir yüksekliğiniz varsa, iyi durumdasınız demektir. OS-rankını burada işlemeyeceğiz ama kitapta var;onun da rankı O(log n) düzeyindedir. Burada sormak istediğim bir soru var. Biz düğümlerde alt ağaç boyutları yerine neden rankları saklamıyoruz?

Evet? Çünkü o düğümün zaten kendisidir. Öyle olmasa zaten bunun solunu ele alamazsınız. Yani bunu kesin anlatımlı bir dilde söylüyorsak o zaman hiçbir kafa karışıklığı olmaz. Ama biz sözde kod yazıyoruz, sözde kod kısa olduğu için iyidir ve algoritmaya odaklanmamıza izin verir. Öte yandan siz ölçekleme, güvenlik veya emniyet gibi kavramlarla ilgili bir program yazıyorsanız sözde kodda bu konuda bir çok şeyi yazamazsınız.

Buyurun. Evet, bunu değiştirmeye kalktığınızda bakımını yapmak veya özelliklerini korumak zordur. Örneğin eğer bu rankları düğümlerin içinde tutsaydık belirtilen bir ranktaki elemanı bulmak kolay olurdu. Bu durumda tek yapacağım şey diğer elemanlardan daha küçük olan en küçük elemanı araya yerleştirir ve ne olduğuna o durumda bakardım. Bütün ranklar değiştirilmek zorunda kalırdı. Eğer benim muhafaza etmem gereken n sayıda değer varsa n düzeyinde değişiklik gerekirdi.Ama bunu alt ağaç boyutlarını saklayarak yapmak daha kolaydır. Çünkü kırmızı siyah ağaç değiştirildiğinde değerlerin korunması zor olur.

Ve buda diğer bir hileli uygulamadır. Bir veri yapısını genişletmek istediğimizde, işlemlerinizin hızlı gitmesi için içine bir şeyler koymak istersiniz ama öteki taraftan da veri yapısının içerisinde de bazı alt işlemlerin korunmasının gerektiğini de unutmamalısınız. Şu kapıyı kapayabilir miyiz lütfen? Teşekkür ederim. Bu değişim işlemlerinin ne olduğuna ve bunları nasıl korunacağına bakmamız gerekiyor. “Kırmızı siyah” ağaçlar için değişim operasyonları araya yerleştirme ve silmedir. Bir ikili yığını genişletmek isteseydim hangi işlemlerle ilgilenmem gerekirdi?

Bir yığını ya da kümeyi genişletmek istediğimde bunu değiştirecek işlemler nelerdir? Mesela ikili minimum yığında. Klasik öncelik sırası? Kim heap’leri yani yığınları hatırlıyor? Yığınlardaki operasyonlar ya da işlemler nedir? İşte bu güzel bir final sorusu olur. Ev sınavı ise fazla dert etmeyin. Finalde çıkarsa bunu dert edinmelisiniz. Yığındaki işlemler nedir? Buna “Books time 24”de veya adı her neyse bakın, değil mi? “AnswerMan”? AnswerMan bu konuda ne diyecek?

Ve? Eğer bir minimum yığınsa, tipik operasyonlar “minimumu çekme” ve “araya yerleştirme gibi işlemlerdir. Bunların arasında hangisi değiştiricidir? Araya yerleştirme ve minimumu çekme, tamam mı, yani “minimum bul” değil;mini bulmak sorun değildir çünkü bu sadece bir sorgulamadır. Yani bir dinamik veri yapısını değiştiren işlemlerle, değiştirmeyen işlemleri birbirlerinden ayırmayı istersiniz çünkü yapıyı değiştirmeyen işlemler veri yapısına uygundur; çünkü herhangi bir bilgiyi yok etmezler. Sorgulamalarda bunlar kolaydır. Ama veri yapısını değiştiren işlemler konusunda dikkatli olmamız lazım ve eski yapıyı korumaya özen göstermemiz lazım. Bu durumda araya yerleştirme ve silme işleriyle ilgili stratejimiz araya yerleştirme veya silme yaparken alt ağaç boyutlarını güncellemektir.

Örneğin ben k elemanını araya yerleştirdiğim zaman ne olduğuna bir bakalım; (k) anahtarını. Ben bunu şuraya yerleştirmek istiyorum, tamam mı? Bunu buraya yerleştirdiğimde alt ağacın boyutuna ne olacak? Bu 10’na çıkacak. Ondan sonra ben sola gideceğim. Bu 6’ya çıkacak. Buradaki de 4’ e çıkacak. Burada 2 olacak. Ve ondan sonra ben k’yı şuraya 1yazarak koyacağım. Böylece aşağıya doğru bir güncelleme yaptım. Oldukça kolaydı.

Öyle mi? Ama artık bu “kırmızı siyah” ağaç değil. Şimdi bunu yeniden dengelemeniz lazım. Bu nedenle yeniden dengeleme işlemine başlamanız gerekir. Bu insanların sık sık unuttukları bir şey ve bende hatırlamalarına yardımcı olmak için, bu tip şekilleri gördüğümde bu şeklin ne olduğunu hemen açıklıyorum ki ileride kendi çalışmalarınızda bu tuzağa düşmeyin. İnsanlar siyah beyaz ağaçlarda araya yerleştirme yaparlarken, araya yerleştirme kısmını hatırlarlar ama siyah beyaz araya yerleştirme yani RB araya yerleştirme sürecinin aslında iki bölümden oluştuğunu unuturlar. Önce ağaca araya yerleştirme yaparsınız, sonrada bunu dengelemeniz gerekir. Bu nedenle RB araya yerleştirmesinin tüm işlemlerini yaptığınızdan emin olmalısınız.

Sadece ağaçta araya yerleştirme işini yapmak yeterli değildir. Biraz önce ağaca araya yerleştirme kısmını yaptık; bu kolaydı. Şimdi dengeleme işini de halletmemiz gerekiyor. Bizim dert edineceğimiz iki tip şey var: Birincisi kırmızı siyah renk değişiklikleri. Bunların alt ağaç boyutlarına bir etkisi olmaz. Eğer öğelerin renklerini değiştirirsem, bunun etkisi yoktur ve problem yaratmaz. Ama ilginç olan şey rotasyonlardır. Rotasyonlar aslında halletmesi çok zor olan işlemler değildir. Çünkü ben bir rotasyonu yaparken, ardıllara bağlı olan düğümlerde güncellemede yapabilirim. Bunu size göstereceğim. Bu olayda ardıllara bakın ve bu örnekte,O(1) zamanında bir rotasyonla bu işi halledin.

Örnek olarak benim ağacımın bir parçasının şöyle göründüğünü hayal edin: Diyelim ki 7, 3, 4 bu alt ağaçların boyutları olsun ama buraya başka değerler yazmayacağım. Ve ben şu kenarda bunları öteki yöne çevirmek için bir sağ rotasyon yaptım. Bunun sonucunda bu elemanlar şu şekilde sıralandılar. Her zaman üç ardıl üç ardıl olarak kalır. Bu nedenle şu elemanı buraya gönderirim ve bu elemanı da ötekinin atası olarak atarım.

Ve buradaki bu elemanı basitçe güncellerim. Bu 8 olur; yani 3+4+1 formülümü kullanarak bunun boyutunu bulurum. Ve şimdi bu 8+7+1, yani 16 olacak.ve bununla ilgili düşündüğümde eski değerinde kalacak, çünkü bu alt ağaçta alt ağacın boyutunu bir rotasyon yaparak değiştirmedim. Bu kenarın altındaki her şey zaten bu kenarın altında kalacaktır. Böylece bunu bir defada düzeltmiş oldum. Bazen başka tipte operasyonlar olur ve bu değer böyle çıkmaz. Eğer alt ağaç boyutları yerine alt ağacın başka bir özelliği ile ilgili bir işlem yapsaydım, bu değer 16 olarak kalmazdı. O zamanda ben bu işlemi yukarıya, köke doğru yönelecek şekilde yapmak zorunda kalırdım.

Kitapta yeniden dengelemenin çok bir şeye mal olmayacağı durumları gösteren güzel bir Lemma / önkuram var. Bu oldukça iyiydi. Araya yerleştirme ve çıkarma işlemleri rotasyonlarda yaptığımız işlemlerdir ve bu nedenle de hala log n düzeyinde zaman alırlar. Çünkü “kırmızı siyah” ağaçlarda sadece birinci düzey rotasyonlar yapılır. Bunlar normalde sabit zaman mı alır? Evet, sabit zaman alırlar. Ama genelde bu sabit biraz daha büyüktür. Sonuçta bu önemli veri yapısını kurabildik ve bu veri yapısı dinamik sıra istatistik sorgulamalarını yapabiliyor ve bunu yaparken (log n) düzeyinde zamanda araya yerleştirme silme ve başka sorgulamaları halledebiliyor. OS-select gibi. Burada bir eleman için de arama yapabilirim.

Temel bir veri yapısı aldım ve bunun içine yeni bir takım işlemler kattım. Burada yaptığımızla ilgili herhangi bir soru var mı? Konu yeterince anlaşıldı mı? Öyleyse genelleme yapalım ve bu her zaman tehlikeli bir şeydir.

Veri yapılarını genişletmek. Burada yapmak istediğim şey, bir şeyleri unutup bunu güvenli bir şekilde yapamamanız durumda size bir metodoloji vermektir. Burada en çok yapılan hata. aslında ev sınavlarında ya da finalde bir geliştirme problemi çıkarsa, size garanti ederim ki bu sınıfın dörtte biri genişletilmiş kırmızı siyah ağaçta rotasyonları unutacaktır.

Size bunu garanti ediyorum. Bu konuda kendinizi kontrol etmeniz için küçük bir metodoloji yani yöntem veriyorum. Belirttiğim gibi, bunun önemli olmasının sebebi pratikte sizin bu hataları sıkça yapmanızdır. Bir veri yapısını sadece verildiği şekliyle kullanmayın. Bir veri yapısı alın. “Benim kendi operasyonlarım ya da işlemlerim var deyin ve bunu bunun içinde katmanlamak istiyorum” deyin. Şimdi size bir yöntem verilecek ve bunu açıklamak için şuradaki OS-trees yani sıra istatistikleri ağaçları örneğinden yararlanacağım. Bu dört adımdan oluşur.

Birinci adım altta çalışacak bir veri yapısını seçmektir.

Sıra istatistikleri ağacı durumunda bu neydi? “Kırmızı siyah” ağaç.

İkinci yapmamız gereken şey bu veri yapısında hangi ek bilgilerin korunması gerektiğini belirlemektir. Bu durumda bu nedir? Alt ağaç boyutlarıdır. Bu örnekte korumamız gereken alt ağaç boyutlarıdır. Ve bunu yaparken de hata yapabiliriz, değil mi? Diyebiliriz ki,“ha tamam rankı koruyalım”. Bununla oynamaya başlarız ve bunu yapabileceğimizi keşfederiz ama bu sadece gerçekten yavaş olur. Korumak istediğiniz bilgilerin hangileri olduğu, bu sırada da istediğiniz diğer özellikleri korumayı hesaplamak biraz yaratıcılık gerektirir.

Üçüncü adım hangi bilgilerin o veri yapısı üzerindeki değiştirici işlemler sırasında korunabileceğidir. Örneğimizde OS-trees değiştiren işlemler araya yerleştirme ve silmeydi. Ve tabii, rotasyonlarla da ilgilenmemiz gerektiğinden emin olmalıydık. Çünkü rotasyonlar olmasa biz bu ağaçta araya yerleştirme ağaçtan silme ve rotasyon işlemlerini yapamazdık. Ve bunu da yaptıktan sonra her şey iyi oldu. Elimizdeki bu problemde renk değişiklikleriyle ilgilenmek zorunda kalmadık. Ama bazı durumlarda karşınıza bu sorun olarak çıkabilir. Bir sebeple, renk değişikliğe neden olabilir; ama genelde olmaz.

Ve dördüncü adımda yeni işlemler geliştirmektir. Bu işlemler teorik olarak yeni depoladığınız bilgiyle ilgili olur. Ve bunlar örneğimizde OS-select ve OS-rankıydı; biz bunları yapmadık ama oradaydılar. Ayrıca OS-rankının nasıl yapılandıracağı sizin kendi kendinize çözmeniz gereken hoş bir bilmecedir. Çok zor bir kod parçası değildir. Ama bu yöntem aslında bunu yapmanızın yolu değildir. Bu, bir tür bir kontrol listesi olacaktır ve bunun sonucunda elinizde doğruların olup olmadığını anlayacaksınız.

Belki bu işi uygulamada yaparken önce yeni işlemleri geliştirirsiniz. Burada depoladığınız bilgileri kontrol ederken yeni operasyonları da akılda tutmanız gerekir. Belki sonradan geri dönersiniz ve bu olguyu yeniden tarayıp gözden geçirirsiniz. Buradaki olay bir kontrol listesidir ve işiniz bittikten sonra bunu nasıl yazacağınızla ilgili bir yönergedir. Elinizde bir kontrol listesi var. Benim altta bulunan veri yapım burada. Burada da ihtiyacım olan ek bilgiler var. Değişim getiren işlemleri uygulayacağınız veri yapısını hala destekleyebiliyorsunuz ve burada da yeni işlemler var; bunların ne olduğunu görebilirsiniz. Bu gerçekten de bir kontrol listesidir. Yani sizin işlerinizi hangi sırada yapacağınızı gösteren bir reçete değildir. Bu adımların hepsini gerçekleştirmeniz gerekir ama bu sırada yapmanız şart değildir. Bu sizin dokümantasyonunuz için bir kılavuzdur. Size herhangi bir veri yapısını genişletmeniz konusunda istekte bulunduğumuzda, genelde size bu dört adımın ne olduğunu bize söylemenizi isteriz. Bu sizin işlerinizi organize etmeye yarar.

Aynı zamanda siz bu yolda ilerlerken bir adımı unutmamanız konusunda yardımcı olur. Ben ek bilgileri ekleyen ve yeni işlemler geliştiren insanlar gördüm ama bunlar mevcut bilginin korunması gerektiğini tamamen unutmuşlardı. Yani siz bütün bunları yaptığınızdan emin olmalısınız. Genelde adımlar arasındaki etkileşimlerle ilgilenmeniz gerekiyor. Bu iş sadece “bunu yap, bunu yap, bunu yap” değildir.

Şimdi daha karmaşık bir veri yapısını işleyeceğiz. O kadar da karmaşık değil ama bunun doğruluğu insanı bayağı zorlar.

Ve bu çok pratik ve faydalı bir veri yapısıdır. İnsanları çok yavaş kod yazarken gördüğümde bu tip yararlı veri yapılarının olduğundan haberleri olmaması beni çok şaşırtır. Şimdi yapacağımız örnek interval-trees yani aralık ağaçlarıyla ilgili olacak. Ve buradaki fikir bir takım aralıkları korumak istememizle ilgilidir. Örneğin zaman aralıklarını. Elimde korumaya çalıştığım kocaman bir zaman aralıkları “veri tabanı” var. Örneği burada yapalım. Bu 7’den 10’a, 5’den 11’e ve 4‘ten 8’e kadar. Bunlar 15’den 18’e, 17’den 19’a ve 21’den 23’e kadar. Bun bir aralıklar setidir. Ve elimizde i aralığı olsun; bu i aralığı7 virgül 10 şeklinde gösterilsin. Bu son noktaya i’nin düşük son noktası diyeceğiz ve şuna da i’nin yüksek son noktası diyeceğiz. Burada düşük ve yüksek sözcüklerini sol ve sağın yerinde kullandım, çünkü bizim bir ağacımız olacak ve bu ağaçta bir sol alt ağaç ve birde sağ alt ağaç olacaktır. Yani eğer aralıklar için sol ve sağ terimlerini kullansaydım ve bunu aynı zamanda ağaçlar için kullansaydım belki bu bir karışıklık yaratırdı.

Bu aynı zamanda bir ipucudur. Kodlama yaptığınız zaman bazı durumlarda sözcüklerle ilgili iyi düşünmeniz gerekir. Çünkü sol ve sağ gibi sözcükler program yazımı sırasında o kadar çok kullanırlar ki burada karışıklık çıkabilir. Değişik durumlar için kod yazımında, iyi anlaşılır olması bakımından zengin bir eşanlam dağarcığınızın olması iyi fikirdir ve anlatmak istediğinizi daha kolay anlatırsınız. Örneğin burada aralıklar için ve ağaç için farklı kullanımlarda olduğu gibi..

Ve burada araya yerleştirme ve silme işlemlerini aralık ağacına uygulayacağız. Ve bir sorgulamamız olacak; bu yeni bir işlem olacak. Bunu geliştireceğiz ve bununla kümenin içinde sorgulama için verilen aralıkla çakışan bir aralık bulmaya çalışacağız. Yani ben size bir aralık sorgulaması verdiğimde, örneğin 6 - 14 dediğimde, şunu ve bunu yanıt olarak çıkarabilirsiniz, şunu da çıkarabilirsiniz; diğerlerini çıkaramazsınız çünkü onlar 14’ den küçük.

Sonuçta bunlardan herhangi birini yanıt olarak çıkaramam; sadece bir tanesini sonuç olarak almam gerekiyor. Bunlardan birisinin tam olarak çakıştığını bakıp onu bulmam gerekiyor. Burada kuracağımız şeyle ilgili herhangi bir soru var mı?

Tamam, yöntemimiz ilk olarak birinci adımı seçmektir. Metodolojimiz şu olacak: Birinci adımda mevcut veri yapısını seçeceğiz. Burada aralık ağaçlarını destekleyecek ne tip bir veri yapısı kullanmamız gerektiği hakkında bir önerisi olan var mı?

Burada aralık ağaçlarını desteklemek için hangi veri yapısından başlamamız gerekir? Herhangi birinin bir fikri var mı? Bir “kırmızı siyah” ağaç. Bir ikili arama ağacı. “Kırmızı siyah” ağaç. Evet bir “kırmızı siyah” ağaç kullanacağız. Ama bunun neyin üzerine anahtarlandığını söylemem lazım. Benim kırmızı siyah ağacımın anahtarı ne olacaktır? Her aralık için anahtar olarak ne kullanmalıyım? Bu noktada birkaç seçeneğimiz var değil mi? Fikirlerinizi duymak istiyorum. Dallanmak her zaman budamaktan iyidir. Daha sonra budama işlemine girebilirsiniz ama önce dallamazsanız sonra budama şansınızda olmaz.

Evet fikirleri üretmek. Buna kuramlama evresinde ve ev sınavınızda ihtiyacınız olacak. Evet? Buna düşük son nokta diyoruz. Evet, düşük son noktadan başlayabilirsiniz. Başka hangi fikirler var? Yüksek son nokta. Şimdi artık düşük son noktaya da yüksek son noktaya da bakabilirsiniz. Pekiyi, düşükle yüksek arasında hangisi daha iyidir? Bu çok fark etmeyecek değil mi? Düşüğü yada yükseği almak çok önemli değil gibi görünüyor ama başka bir doğal konu var ki bunu da düşünmek gerekiyor. Bu ortanca noktası yani orta noktasıdır. En azından bu simetriktir. Ne düşünürsünüz? Başka ne kullanabilirim? Aralık uzunluğu?

Uzunluk bana çok verimli olmayacak gibi geliyor. Ama bu tamamen sezgisel bir durum. Çok verimli değil gibi geliyor, çünkü uzunluğu bilsem bile yerini tahmin ettiğimde sorgulama sırasında nerede olduğunu bilmediğimden bilgiyi korumak zor olacak gibi geliyor. Sonuç olarak biz soldaki düşük son noktayı kullanacağız; ama bana öyle geliyor ki siz daha çok ortadakini kullanmayı düşünürdünüz; ve bunu kullanmak sizin için bir sürpriz oldu.

Çünkü siz son noktalar arasında tercihler yapıyorsunuz. Aslında şaşırtıcı olarak buda doğru bir yaklaşımdır. O başka bir strateji olabilir. Gerçekte başka tip bir ağaç daha vardır ve buna segment tree yani bölüt ağacı denir. Burada yapılan sol ve sağ son noktaları ağacın içinde ayrı ayrı depolamaktır. Sonra da öyle bir veri yapısı koruması yaparsınız ki, çizgi parçaları bir ağaçtan ötekine yukarıdan dolaşarak geçer.

Bu konuda yapabileceğiniz çok şey var ama biz şuanda düşük son noktaya kilitleneceğiz. Bazı bakımlardan bu daha akıllı bir veri yapısı olacak. Şimdi bu daha zordur bu nedenle daha akıllıdır. Neyin nerede depolayacağımıza gelince; bana göre bu fikirlerin hepsi, bakmak ve ondan sonra vazgeçmek için iyidir. Siz bunların hangisinin işlevsel olacağını bunlarla oynamadan bilemezsiniz. Ama bana göre bu elimizdeki, tahmin edilmesi daha zor bir şeydir. En büyük değeri, ki ben buna m diyeceğim, bir düğümde depolayacaksınız ve bu da o düğümün alt ağacının kökünde olacak.

Biz şimdi bu düğümü şöyle çizelim. Aralığı buraya koyalım ve m değerini de şuraya koyalım. Bir şekil çizelim. Tekrar ediyorum NİL’leri çizmiyorum. Ve umuyorum ki bu arama ağacı soldaki düşük son noktaya anahtarlanmış olsun. 4, 5, 7, 15, 17, 21.Anahtar soldaki düşük son noktada olacak. Eğer bu bir “kırmızı siyah” ağaçsa bir pratik daha yapalım. Bu ağacı yasal bir “kırmızı siyah” ağaç olacak şekilde nasıl boyayabilirim? Bu şu anda yaptığımız işle çok da ilgili değil.

Ama bazen küçük bir egzersizin zararı olmaz. Unutmayın NİL’ler orada yok ve bunların hepside siyahtır. Kök de siyahtır. Size bu kadarını söyleyeceğim. İyi, bu çalışacaktır.

Burada sanki küçük bir bilmece çözersiniz. Bir mantık bilmecesi. Bu oldukça kısa, umarım ki içinde kırmızılar olmaz. Bunun siyah olması lazımdır. Şimdi yüksekliği dengeleyeceksem, burada bir siyah katmana ihtiyacım olur. Bu şu olamaz. Şunların ikisi olmak durumundadır. İyi, şimdi bunların her biri için m değerini hesaplayalım. Bu değer o düğümde köklenmiş alt ağaç içindeki en büyük değerdir.

Şu düğümde kökü olan alt ağacın içindeki en büyük değer nedir? 10. Peki bunun içindeki? 18. Şunun içindeki? 8. Bu 18. Şuradakinin 23 ve buda 23. Genelde m bu 3 olası değerin en büyüğü olacaktır. Ya x aralığının yüksek değeri, ya x’in solundakinin m’si ya dax’in sağındakinin m’si olacaktır. Bunu herkes görüyor mu? Bu x her düğüm için x’in m’si olacaktır. Yapmam gereken her düğümde buradaki maksimum nedir, buradaki maksimum nedir diye bakmak ve aralığın yüksek noktasının ne olduğunu bilmektir. Bunlardan hangisi en büyük ise o alt ağaç için en büyük değer odur.

Değiştirme işlemleri. Önce araya yerleştirmeyi yapalım. Burada nasıl araya yerleştirme yapabilirim? Ortada 2 kısım var. Bu işlemlerden birincisi “ağaç araya yerleştirmesi” yapmaktır. Yani bir ikili arama ağacına normal yerleştirme yapmaktır. Burada ne yaparım? Yeni bir aralık mı araya sokarım? Buraya bir yeni aralık mı yerleştirmeliyim? Bu durumda m’leri nasıl düzeltebilirim? Evet ,doğru. Ağaçta aşağıya doğru gidersiniz ve şu andaki aralığıma bakarsınız. Ve bu değer daha büyükse, o zaman o alt ağacın içine girecektir. Eğer bunun yüksek son noktası mevcut maksimumdan daha büyükse o zaman mevcut maksimumu güncellersiniz. Bu araya yerleştirmeyi yaparken bu işi de yapacağım. Hangi alt ağaçta çalışıyorsam orada ve aşağıya doğru giderken karşılaştığım her düğümde bunu yapacağım.

Bunu nereye gelirse gelsin maksimum olarak güncelleyeceğim. Tamam mı?. Yani aşağıya doğru giderken düzeltmeleri de yaparsınız. Ama biz öteki işlemi de yapmak zorundayız. Yani rotasyonları yada dönmeleri de göz önüne almalıyız. Burada bir örnekle rotasyonları nasıl yapacağımıza bakalım: Diyelim ki bu 11, 15, 30’dur. Yine diyelim ki sağa rotasyon yapıyorum. Bu bir yerlerden gelmiş. Şu düşüyor. Bu hala ardıl olarak kalacak ve içinde 30 var. Ayrıca 14 ve 19var. Şimdi bu yöne doğru döndük; böylece bu 11-15 ve şu da 6-20 oldu. Bunun için ben sadece formülümü kullandım.

Buraya sadece bakarım ve bunlardan hangisinin en büyük olduğunu söylerim; yani 14, 15 ve 19’un arasında. 19. Sonra buraya bakarım. Hangisi en büyüktür? 30, 19 ve 20? 30. Bir kez daha genelde çıkan sonucu göstermek çok zor değildir. Genelde orada olan neyse o kalır. Çünkü biz o alt ağaçta olan en büyük değere bakıyoruz. Ve rotasyonu yaptığımız zaman alt ağacın içindeki elemanlar değişmez. Bunu yapmak benim O(1) zamanımı aldı.

Rotasyon sırasında m’leri düzeltmek O(1) zaman alır. Bu nedenle toplam araya yerleştirme süresi O(logn)’dir. Bu bilginin doğru olduğunu hesapladıktan sonra, tabii daha bunu hangi amaçla kullanacağımızı bilmiyoruz. Ama bu bilgiye bir kez sahip olduktan sonra bazı sürekli silme işlemlerinin de log n düzeyinde zaman alacağını göstermek kolaydır. Şimdi silme biraz daha şaşırtıcıdır ama benzer olduğunu söyleyebilirim. Çünkü silme işleminde siz buralardan geçersiniz ve bir şeyi bulursunuz; tabii bu işi yaparken bütün yolu da kat etmeniz, bazen değiştirmeniz gerekebilir.

Eğer bu bir dahili düğümse, bunu atasıyla yada ardılıyla değiştirmeniz gerekebilir. Yani burada uğraşmanız gereken işler var ama bu işlerin hepsi bu kuralları uygulayarak bilginin güncellenmesinde kullanılabilir. Ve bütün bunlar temelde yerel değişikliklerdir. Çünkü bu bilgiyi güncellerken aslında yaptığınız şey kökten yukarıya doğru giden yolda çalışmaktır. Ve ağacın bütünü sizi hiçbir zaman ilgilenmezsiniz. Bu konuyu sizin kendiniz çözmeniz için size bırakıyorum.

Eğer kopya çekmek isterseniz bu kitapta da var ama bu iyi bir egzersizdir. İlk 3 adım hakkında herhangi bir soru var mı? Dördüncü adım yeni operasyonlar yeni işlemler olacak. i’nin aralık araması, i intervali yani aralığı ile çakışacak bir aralık bulacak. Burada i bir aralıktır. 2 tane koordinatı vardır. Ve bunu yazarken, aslında burada özyinelemeli işlemler olacak ama özyineleme kullanmak yerine biz bunu bir WHILE döngüsü(iken döngüsü) olarak yazacağız. İsterseniz özyineleme şeklinde de yazabilirsiniz. Bir önce yazdığımızı da bir WHILE döngüsü olarak yazabilirdik. Ve özyineleme işlemi olmazdı. Burada başlayacağımız nokta x’in kökte olması durumudur.

Ondan sonra WHILE yazacağız. Bu kodudur. Nasıl çalıştığına bir bakalım. Bu ağaçta14-16 aralığını arayalım. Bu bize x kökte başlıyor diyor. Ve WHILE x yani kök NIL olamayacağı için buda NIL değil. Bu ne yapıyor? Birisi bana bu kodun ne yaptığını söyleyebilir mi? Yani burada ne yapıyor? Bu i ile int(x)aralığı arasında bir şeyi test ediyor. İnt(x) x’de depolanmış olan aralıktır. Bu neyi test ediyor?

Doğru yaptığımı sanıyorum. Neyi test ediyor? Evet? Üstte mi altta mı? Sadece basit sözcükler istiyorum. Çakışmalar için test. Özellikle bunlar çakışıyor mu, çakışmıyor mu testi? Yapıyor mu? Yapmıyor mu? Bu noktaya geldiğim takdirde i ve int(x)’in aralığıyla ilgili ne biliyorum? Çakışmıyorlar. Çakışmıyorlar, çünkü birisinin üst değeri ötekinin alt değerinden daha küçük. Birisinin üst değeri ötekinin alt değerinden daha küçük olduğundan bu şekilde çakışamazlar. Öteki türlü çakışabilirler mi? Hayır, çünkü aynı zamanda biz bir tanesinin düşük değerinin ötekinin yüksek değerinden daha büyük olup olmadığını da test ediyoruz. Yani deniliyor ki bu ya böyledir, yada şöyledir. Bu bir burada “çakışma yok” testidir. Bu işi daha kolaylaştırıyor. Ben 14-16’yı ararken burayı kontrol ederim.

Burada derim ki “bunlar çakışıyor mu?” Ve cevabı bir sürü aritmetik hesaba girmeden “hayır bunlar çakışmıyor” şeklinde buluruz. Eğer çakışsalardı o zaman aradığımı bulmuş olurdum. Bu durumda ne olacak?

Bu durumda While döngüsünden vazgeçeceğim ve x’i döndüreceğim. Çünkü çakışan bir şeyi döndürmek benim hedefimdir. Burada gördüm ki bunlar çakışmıyor. Bu durumda ben derim ki eğer x in solu NIL değilse, başka bir deyimle bir sol ardılım varsa ve i’nin düşük değeri x’in solundaki m’ye küçük eşitse, o zaman sola giderim. Bu durumda ben 14-16 aralığını ararken ne olur? i’nin düşük değeri x’in solundaki m’ye küçük eşit midir? i’nin düşük değeri 14 dür.

Ve aramaya devam ediyorum. Bu 18 den küçük müdür? Evet. Böylece ne yaparım? Sola giderim ve x’in bu elemana işaret yönlendirmesini yaparım. Şimdi kontrol edelim. Bu çakışıyor mu? Hayır. Soldaki elemana bakarım. Bu 8. Ben 8 ile 14 ü karşılaştırırım değil mi? Bu düşük müdür? Hayır. O zaman sağa giderim. Şimdi burada bir çakışma olduğunu keşfederim ve bu bir çakışmadır. Bu durumda 15-18 aralığı çakışan bir aralık olarak döndürürüm.

Eğer, 12-14 aralığını arıyorsam; Bu durumda yukarıya doğru giderim ve bakarım ki 12-14 burada çakışmıyor. O zaman 18’e bakarım ve bunun büyük olduğunu görerek sola giderim. Sonra buraya bakarım. Çakışıyor mu? Hayır. Pekiyi, bu durumda ne olur? Sola bakarım. O derki “sağa git”. Ben buraya bakarım. Sonra oraya giderim ve sola bakarım. O derki hayır “sağa git”. Buraya gelirim bu NIL’dır. Ben NIL’ ı döndürürüm. Ve 12-14 bu setin içinde herhangi bir şey ile çakışıyor mu? Hayır. Yani bu durumda gördüğünüz gibi bu algoritma her zaman çalışır.

Tamam mı? Haydi tamam diyelim. Birazdan algoritmanın doğruluğunu kontrol edeceğiz ama doğruluk biraz şaşırtıcı olacağı için önce çözümlememizi yapalım. Süre eşittir O(logn).Çünkü tüm yaptığım şey ağaç boyunca aşağıya inmektir. Buda ağacın yüksekliğine orantılı bir zaman alır. Bu işin kolay kısmıdır. Tüm çakışmaları listelemek istediğimde bunu ne kadar çabuk yapabilirim? Birisi çakışmaları listelemek için alt yordam olarak kullanabileceğim bir öneride bulunabilir mi?

Varsayalım ki elimde k çakışma var ve sorgulama aralığımdaki k çakışmanın hepsini listelemek istersem bunu ne kadar hızlı yapabilirim? Bunu nasıl yapabilirim? Evet, bunu nasıl yapabilirim? İkinci defa arama yaparsam aynı değeri elde edebilirim. Evet, işte doğru cevaba doğru gidiyorsunuz. Ne yapılır? Bulduğunuz zaman onu silersiniz. Bir kenara koyarsınız. Ondan sonrakini bulursunuz onu da silersiniz, işin sonunda hiç bir şey kalmayana dek. Sonrada eğer veri yapısını bozmak istemiyorsam bütün bunları tekrar araya yerleştiririm. Eğer k çakışma varsa bu bana k log n’ ye mal olur. Buna aslında output sensitive yani çıkışa hassas algoritma denir.

Çünkü bunun yürütüm süresi ne kadar çıkış vereceğine bağlıdır. Bu nedenle çıkışa hassastır. Bugüne kadar bu problemde elde edilen en iyi sonuç listelemenin O(k+logn) süresinde yapıldığıdır ama başka bir veri yapısı kullanılır. Aslında bu bir süreliğine bir açık problem olarak var olmuştu. Tamam, şimdi doğruluğa gelelim. Bu algoritma neden her zaman doğru olarak çalışır? Doğruluğu sağlayan ana konu gitmek istediğim, yolu sol veya sağ olarak seçmemdir. Ve bu aynı alt ağacın içinde kaldığım sürece çok iyi bir özelliktir.

Ama hangi yola gideceğimi seçtiğimde, örneğin sola giderken cevabın sağ alt ağaçta olduğunu ve benim yanlış yolda gittiğimi nasıl bilip karar vereceğim? Veya tersine sağa giderken yanlışlıkla sol tarafta bir şeyi unutmadığımı nasıl bileceğim? Biz her zaman sadece tek yönde gidiyoruz. Bu kodun akıllılığı da buradadır. Bunun teoremi şöyledir. L’yi x düğümünün solundaki i üssü aralıkları olarak tanımlayın. Ve R’de x’in sağındaki iüssü’ler olsun. Ve şimdi göstereceğim iki bölüm var. Eğer arama sağa gidiyorsa, L’nin içindeki i üssü kümesi öyle olur ki ile çakışan i üssü boş küme olarak alınır.

Bu yaptığım ilk şey olur. Eğer sağa gidiyorsa sol alt ağaçta bununla çakışacak hiçbir şey yoktur. Eğer kod iyi işliyorsa hiçbir zaman problem olmaz. Çünkü sol alt ağaçta bulunabilecek bir şey yoktur. Bunun ne olduğunu herkes anlayabiliyor mu? Biz bunu kanıtlayacağız ama ben ayrıca herkesin bunu anlamasını istiyorum. Çünkü bundan sonraki konu daha zor olacak ve bu birincisini anladığınızdan emin olmalısınız. Bunlar hakkında herhangi bir soru var mı? Tamam.

Eğer arama sola giderse, L’nin içindeki i üssü kümesi öyledir ki, i,i üssü ile çakışırsa, bu boş küme olur!!. Tamam. Bu ne diyor. Eğer sola gider de orada bulunacak hiç bir şey olmadığını keşfederseniz, yani bulunacak hiçbir çakışma aralığı yoksa,bu uygundur, çünkü bu durumda beni sağa yönlendirmesinde yarar yoktur. Çünkü sağda da bulunacak hiçbir şey yoktur.

Bu solda bir şeyin bulunamayacağını garanti etmez ama, eğer solda hiçbir şey yoksa bu olabilir ama zaten sağda da bulunabilecek hiçbir şey yoktur. Bu ikincinin söylediği şeydir. Her iki durumda da siz o yola gidebilirsiniz. Şimdi kanıta geçelim. Herkes bu kanıtın ne anlama geldiğini anlıyor mu? Kanıtı anlamak oldukça zordur. Bu mantıktır ve mantık şaşırtıcıdır. Önce, birinciyi yaptığımızı varsayalım. Arama sağa gidiyor.

Eğer x’in solu NILise, işimiz bitti. Çünkü kanıtlamak istediğimizi kanıtladık. Sağa gittiğimizde 2 seçenek vardır. Ya x’in solu NILdir. Veya x’in solu NIL değildir. Şimdi eğer x NIL’se gene işimiz bitmiştir. Çünkü dedik ki sağa gidildiği zaman soldaki alt ağaçta çakışma durumunu yaratacak bir şey olmaz. Eğer orada hiçbir şey yoksa zaten çakışacak bir şey olmaz. Aksi takdirde i’nin düşük değeri x in solundaki m’den daha büyüktür.

Buradaki x’e baktığımda, bu while komutunun altında x ya NIL olur ya da bu doğrudur. Biz bunun NIL olmadığını söyledik onun için buna bir bakalım. Ah af edersiniz, yanlış satırdayım. Ben bu döngünün içindeyim. x’in solu NIL değildi ve i’nin düşük değeri buydu. Buradan hangi yola gidiyorum? Sağa gidiyorum.

Bu nedenle bu doğru değildi. Yani ya x’in solu NIL değildi ki ilk durum böyleydi. Veya i’nin düşük değeri x’in solundaki m’den daha büyüktü ve ben bu nedenle sağa gidiyordum. Eğer sağa gidiyorsam, bu ikisinden bir tanesi doğru olmak zorunda. Birincisi kolaydı. Aksi takdirde biz i’nin düşük değerinin x’in solundaki m’den daha büyük olduğunu görürdük.

Şimdi bu şu değer olmak zorundadır. x’in solundaki m sağdaki son nokta yani o alt ağaçtaki bir aralığın yüksek son noktası olmak durumundadır. Buda L’nin içindeki bir j için, j’nin yüksek değerine eşit olur. Yani x’in solundaki m biz m’leri böyle seçtiğimiz için bir son noktanın yüksek değerine eşit olur; sol alt ağaçtaki herhangi bir j değeri için. Ve L’deki başka bir aralığın daha büyük bir yüksek son noktası yoktur; j’nin yüksek değerinden başka. Buraya bir şekil çizecek olursam burada i var ve bu da i’nin düşük değeri. Ve burada da j var. Ve diyoruz ki j’nin yüksek son değeri, i’nin düşük değerinden daha küçüktür. Bu j ve buradan nereye kadar gittiğini de bilmiyorum.

Ve buda j’nin yüksek değeridir, ve sol alt ağaçtaki en yüksek değerdir. Başka hiçbir elemanın sağ son noktasının değeri bundan yüksek değildir. Bu alt ağaçta başka hiçbir şey i ile çakışamaz. Çünkü bütün bunlar şu noktadan önce bir yerde sona erer. Bu nokta bir alt ağaçtaki en yüksek değerdir. Bu nedenle L’deki i üssü öyle olur ki, i-üssü’nün çakıştığı küme bir boş kümedir. Şimdi zor duruma geliyoruz. Herkes bir gerinsin. Zor durum. Herkes bunu takip edebiliyor mu? Buradaki dikkat edilecek nokta bu eleman en yüksek değerde olduğu için her şeyin bunun solunda olması lazımdır. Ve eğer biz en yüksek değerli elemanla çakışma yaratamadıysak o zaman hiçbir şeyle çakışamayız.

Aramanın sola doğru devam ettiğini varsayalım ve sol ağaçta da çakışacak hiçbir şey olmadığını düşünelim. Burada sola gittim ama herhangi bir şey bulamayacağım. Şimdi burada kanıtlayacağım şey, eğer bunu yapmasaydım sağa gitmek bana yardımcı olmayacaktı. Buradaki teoremin temelde söylediği şey budur. Yani şunu varsayarsam sağa gitmenin bana bir yararı olmayacak. Ben sağdaki alt ağaçta bir şeyin olmadığını gösterdim, bu nedenle sola gitmek doğruydu. Zira, zaten orada bir şey bulamayacaktım. Benzer şekilde benzer bir çözümlemeyi yapacağız. i’nin düşük değeri, x’in solundaki m’ye küçük eşit olma durumuna baktığımızda, bu kez bu L içindeki bir j’nin yüksek değerine eşittir.

Burada sadece şunu söylüyoruz. Eğer sola gidersem, bunlar doğrudur. Sola gittim. j L’nin içinde olduğu için i ile çakışmaz. Çünkü i ile çakışan şeylerin seti bir boş settir. j i ile çakışmadığı için bu i’nin yüksek değerinin, j’nin düşük değerinden daha az olduğunu ima eder. j L’nin içinde olduğu için ve i ile çakışmadığı için buradaki olasılıklar nelerdir? Burada bir şekil çizersem, elimizde j ve L var. Ve burada da i var. Buradaki husus çakışma olmadığından bunun solda olması gerektiği, çünkü bunun düşük uç noktasının bundan küçük olduğudur. Ama onunla çakışmadığı için bunun yüksek uç noktası, bunun düşüğünün solunda olmak durumundadır.

Şimdi burada ikili arama ağacı özelliğini kullanacağız. Buna göre, R içindeki bütün i-üssü değerleri için, yani sağ alt ağaçtaki her şeyde, j’nin düşük değerinin i-üssünün düşük değerine küçük eşit olma durumunun olduğudur. Biz düşük son noktalarda sıralanmış durumundayız. Sağ alt ağaçta olan her şeyin bir düşük alt noktası olmak zorunda ve buda j’nin düşük alt noktasının sağında olmak zorundadır; çünkü j soldaki alt ağaçtadır. Ve tüm ağaçtaki her şey düşük alt noktalarla sıralandığından, sağ alt ağaçta da iş buradan başlamak zorundadır. Diğerleri başka şeylerdir. Bunlar R’nin içindeki i-üssü’lerdir. Biz bunların kaç tane olduğunu bilmiyoruz ama bunların hepsinin başlangıcı bu noktanın sağındadır.

Bu nedenle bunlar da i ile çakışamazlar. Böylece ortada bir şey yoktur. R’nin içindeki i-üssü’lerde aslında kayda değer değillerdir. Bunu tekrarlayalım. Buradaki temel fikir, eğer bu eleman soldaki elemanlarla çakışmıyorsa ve sağda olanların hepsi daha da sağda olacaksa, sola gittiğimde ve oradaki şeyi bulamadığımda bu iyidir. Çünkü burada da herhangi bir şey bulamayacağım. Bunlarda çakışmayacak.

Veri yapısı genişletilmesi, çok önemli bir konudur. Bu size bir sürü zengin veri yapısı verecektir ve bu veri yapıları sizin şu ana kadar öğrendiğiniz kıyım tabloları, yığınlar, ikili arama ağaçları ve böylelerine uygun olacaktır.