"Merhaba, Amigo!"
"Merhaba Rishi!"
"Orada eski notlarımı buldum ve sizin için bazı ilginç materyaller hazırladım. Duymakla ilgileneceğinizi düşünüyorum."
"Dinleyelim. Her zaman daha sonra çok yararlı olduğu ortaya çıkan ilginç bir şey bulursun."
"Tamam. Bugün size ağaçlardan bahsetmek istiyorum , bu yüzden grafiklerle başlayacağım ."
" Grafik , noktalar ve onları birbirine bağlayan çizgilerden oluşan bir sistemdir. Noktalara grafiğin köşeleri, çizgilere grafiğin kenarları denir. Örneğin:"
"Bir grafiğin, gerçek dünyadaki çeşitli süreçler ve görevler için matematiksel bir model olarak kullanılması çok uygundur. Grafikler için birçok farklı görev ve algoritma icat edilmiştir, bu nedenle bunlar oldukça sık kullanılmaktadır."
"Örneğin, köşelerin şehir olduğunu ve kenarların yol olduğunu varsayalım. O zaman şehirler arasındaki en kısa yolu aramak, «bir grafik verildiğinde, iki köşe arasındaki en kısa yolu bul» olur .
"Fakat A'dan B'ye giden yol her zaman B'den A'ya giden yolla aynı değildir. Bu nedenle bazen iki farklı çizginin olması tercih edilir. Bunu yapmak için çizgiler (grafın kenarları) oklarla değiştirilir. başka bir deyişle, grafiğin iki oku olabilir: biri A'dan B'ye, diğeri B'den A'ya."
"Grafik okları kullanıyorsa, buna yönlendirilmiş grafik denir ; sadece çizgileri varsa, yönlendirilmemiş grafik olarak adlandırılır ."
"Her tepe noktasının kendi sayıda kenarı olabilir. Bir tepe noktasının hiç kenarı olmayabilir. Tersine, bir tepe noktası kenarlarla diğer tüm tepe noktalarına bağlanabilir. Bir grafikteki her bir köşe çifti bir kenarla bağlıysa, o zaman buna tam grafik denir. "
"Bir grafikteki her köşeye ulaşmak için kenarları kullanabiliyorsanız, buna bağlantılı grafik denir. Üç ayrı köşesi olan ve hiç kenarı olmayan bir grafik yine de bir grafiktir, ancak biz buna bağlantısız grafik diyoruz."
"N köşeden bağlantılı bir grafik oluşturmak için en az N-1 kenara ihtiyacınız var. Bu tür grafiğe ağaç denir."
"Ayrıca, genellikle bir köşe ağacın kökü olarak seçilir ve geri kalanı dal olarak bildirilir. Kendi dalları olmayan ağaç dallarına yaprak denir . Örneğin:"
"Ağacın her elemanının iki çocuğu varsa buna ikili ağaç denir . Yani 0 veya 2 dal olabilir. Sağ üstte bir ikili ağaç görebilirsiniz ."
" Her dalın 2 çocuğu olduğunda ve tüm yapraklar (çocuksuz köşeler) aynı sırada olduğunda, bir ağaç tam bir ikili ağaç olarak adlandırılır ."
"Örneğin:"
"Bu ağaçlara neden ihtiyaç var?"
"Ah, ağaçlar pek çok yerde kullanılıyor. Genel olarak, ikili ağaçlar sıralanmış yapılandırılmış verilerdir."
"Bu da ne?"
"Evet, çok basit. Her köşede belirli bir değer depolarız. Ve her öğe bir kurala uyar: sağ alt öğede depolanan değer, köşede depolanan değerden büyük olmalıdır ve sol alt öğede depolanan değer, köşede saklanan değerden daha az olması. Bu sıralama, ağacın ihtiyacınız olan öğelerini hızlı bir şekilde bulmanızı mümkün kılar."
"Bunun ne anlama geldiğini açıklayabilir misin?"
"Ağaç elemanları genellikle eklenerek sıralanır. Diyelim ki 7 elemanımız var: 13, 5, 4, 16, 8, 11, 10"
"Öğeler ağaca şu şekilde eklenir."
"Bu ağaçta 7 sayısını arıyorsak, arama böyle gidecek"
"0) Kökten başla."
"1a) 7, 13'e eşit mi? Hayır"
"1b) 7, 13'ten büyük mü? Hayır, bu yüzden sol alt ağaca geçiyoruz."
"2a) 7, 5'e eşit mi? Hayır."
"2b) 7, 5'ten büyük mü? Evet, sağ alt ağaca geçiyoruz."
"3a) 7, 8'e eşit mi? Hayır"
"3b) 7, 8'den büyük mü? Hayır, bu yüzden sol alt ağaca geçiyoruz."
"4a) Sol alt ağaç yok, yani 7 sayısı ağaçta yok."
"Ah. Başka bir deyişle, kökten istenen sayının sözde konumuna giden yolun köşelerini kontrol etmemiz yeterli. Evet, bu gerçekten hızlı."
"Ayrıca, ağaç dengeliyse, bir milyon öğeyi aramak için yalnızca yaklaşık 20 köşeden geçmeniz gerekir."
"Katılıyorum - bu çok fazla değil."
"Dengeli ağaç derken neyi kastediyorsun?"
"Bozulmamış, yani uzun dalları olmayan bir ağaç. Örneğin biz ağacı kurarken elementler zaten sıralanmış olsaydı o zaman tek daldan oluşan çok uzun bir ağaç yapardık. "
"Hmm. Haklısın. Peki ne yapacağız?"
"Muhtemelen tahmin ettiğiniz gibi, en verimli ağacın yaklaşık olarak aynı uzunlukta dalları vardır. O zaman her karşılaştırma, kalan alt ağacın en büyük kısmını çıkarır."
"Yani, ağacı yeniden inşa etmemiz mi gerekiyor?"
"Evet. Tam bir ikili ağaca olabildiğince yakın hale getirilmesi için "dengelenmesi" gerekiyor."
"Bu sorunu çözmek için, kendi kendini dengeleyen ağaçlar icat edildi. Bir öğe eklendikten sonra ağaç bozulursa, her şeyin yolunda gitmesi için öğeleri biraz yeniden sıralar. İşte bir dengeleme örneği:"
"Bu ağaçlardan bazıları kırmızı -siyah ağaçlar olarak biliniyor ."
"Neden kırmızı-siyah diyorlar?"
"Mucitleri iki renk kullanarak tüm köşeleri çizdi. Bir renk kırmızı, diğeri siyahtı. Farklı köşeler farklı kurallara uyar. Bu, dengeleme prosedürünün tüm temelini oluşturur."
"Örneğin:"
"Peki nedir bu kurallar?"
"1) Kırmızı bir tepe noktası, kırmızı bir tepe noktasının çocuğu olamaz."
"2) Her yaprağın siyah derinliği aynıdır (siyah derinlik, kökten gelen yoldaki siyah köşelerin sayısını ifade eder)."
"3) Ağacın kökü siyahtır."
"Bunun nasıl çalıştığını açıklamayacağım - muhtemelen kafan çoktan patlıyor."
"Evet. İşlemcim biraz duman çıkarıyor."
"İşte senin için bir bağlantı. Eğer istersen, bununla ilgili daha fazla bilgiyi buradan okuyabilirsin."
"Ve şimdi, git biraz ara ver."
GO TO FULL VERSION