mizikci

  • 38
  • 1
  • 0
  • 0
  • geçen ay

red-black tree

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)

devamını okuyayım »
27.06.2015 07:21