red-black tree

• 2-3-4 tree'nin 4lü ve 3lü nodelarının kırmızı ile gösterildiği aslen binary search tree olan data structure.
• http://en.wikipedia.org/wiki/red_black_tree adresinde implementasyonunun neredeyse tum detaylari (ki hakikaten cok var) gayet acik ve duzenli bir sekilde anlatilmis. yalniz root'u degistirmenizi gerektirebilecek durumlarda kontrolunu yapip, gerekiyorsa rootu degistirmeyi unutmayin; bundan hic bahsetmiyor wikipedia.
• bir binary search tree'yi balanced hale getirmek için kullanılan veri yapısı. buna göre:
  -her node ya siyahtır, ya da kırmızıdır.
  -root her zaman siyahtır.
  -her leaf nullile gösterilir ve siyahtır.
  -eğer bir node kırmızıysa her iki çocuğu da siyahtır. (yani asla root'dan leaf'e giden herhangi bir yolda üstüste iki kırmızı bulunamaz.)
  -her node için, leaf'e giden yollar üzerinde aynı sayıda siyah node vardır. (bu sayı=black height)
  
  bir node insert edilirken ya da silinirken saydığım özellikler bozulmamaya çalışılır. bu sayede tree balanced kalır.
• ikili arama ağacının^* dengeli^* olma problemine çözüm olarak önerilmiş veri yapısı, ekstra kısıtları olan bir çeşit ikili arama ağacı. burada dengeli olmaktan kasıt, bir değer ağaç içinde aranırken, aramanın zaman karmaşıklığının^* belli bir üst sınırın^*altında kalmasını garantilemek. ikili arama ağaçlarında bu karmaşıklık o(logn)'dir (büyük o). sıradan ikili arama ağaçlarında, problem şudur, eklenecek her bir eleman için aranan tek kısıt, ebeveynine ve atalarına göre doğru yönde olmasıdır. yani kendinden büyük olanların solunda, küçük olanların sağındadır. en kötü durumda, n adet eleman içeren bir ikili arama ağacı n derinliğinde olabilir. bu da bir aramanın o(n) karmaşıklığında olmasına yol açar. kırmızı-siyah ağaç ise, her eleman eklendiğinde, belli kurallara göre ağacın yapısını değiştirdiğinden, ağaç sürekli dengelidir ve bu yüzden aramalar o(logn)'den daha karmaşık olamazlar. tabi bunun bedeli, ekleme çıkarma karmaşıklığının artmasıdır. ortada böyle bir alış veriş varken, bu ağaca her koşulda ikili arama ağacından daha iyidir muamelesi yapmak doğru değil. eleman ekleme çıkarma sayısının arama sayısı oranına yakın olduğu problemlerde, kırmızı-siyah ağaç kullanmak, maliyeti arttırdığından gereksiz yere ekleme masrafını yükseltir. ekleme çıkarma sayısının arama sayısına oranının çok düşük olduğu problem örneklerinde, ikili arama ağacı yerine kırmızı-siyah ağaç kullanmak yerinde olur.
  
  daha detaylı bilgi için: (bkz: introduction to algorithms)
• hastası olduğum ağaçtır.
• ağaca ekleme işlemi yapılırken(insert) ebeveynin ve çocuğun üst üste siyah olması, red black tree için sağlanması gereken 5 şartı bozmamaktadır.
  ekleme(insert) ve silme(deletion) işlemlerinde şayet şartlar zedeleniyorsa bu durumda koşulların tekrar sağlanması için düğümlerin(node) renkleri şartlara uygun şekilde değiştirilir. bu tüm şartları sağlamazsa (özellikle root-leaf arasındaki mesafenin eşitliğinin bozulması) bu kez kaydırma işlemi yapılarak(uzun bölgeyi kısaltmak ya da kısa bölgeyi uzatmak için) şartlar yeniden sağlanır.
  
  şartları için bkz. #17493775