Treap veri yapısı ikili arama ağacı ile yığını birleştiriyor
Öne çıkanlar
- Treap, anahtara göre ikili arama ağacı, önceliğe göre ikili yığın kuralını uyguluyor.
- Rastgele üretilen öncelikler ağacın O(log N) karmaşıklığında dengeli kalmasını sağlıyor.
- Tüm ana işlemler temel Split ve Merge özyinelemeli fonksiyonları üzerinden yürütülüyor.
- Örtük Treap yapısı aralık güncelleme ve ters çevirme operasyonlarını logaritmik sürede çözüyor.
İkili arama ağacı ile ikili yığın yapılarını harmanlayan Treap veri yapısı, arama ve sıralama işlemlerinde verimlilik sağlıyor. İlk kez 1989 yılında Raimund Siedel ve Cecilia Aragon tarafından önerilen bu Kartezyen ağaç modeli, düğümlerde anahtar ve rastgele öncelik değerlerini birlikte saklıyor. Rastgele belirlenen öncelikler ağacın yozlaşmasını engelleyerek dengeli kalmasını temin ediyor ve temel operasyonların karmaşıklığını logaritmik seviyede tutuyor.
Yapının tüm ana operasyonları Split ve Merge adındaki iki temel özyinelemeli fonksiyon üzerine kuruluyor. Ekleme, silme ve arama gibi işlemler O(log N) karmaşıklığında yürütülürken, sıralı anahtarlar üzerinden O(N) sürede çevrimdışı inşa süreci işletilebiliyor. Düğümlerde alt ağaç boyutlarının tutulması sayesinde k-inci en büyük elemanı bulma gibi indeks tabanlı sorgular da doğrudan gerçekleştirilebiliyor.
Örtük Treap uyarlaması ise diziler üzerindeki dinamik işlemleri yüksek performansla çözmeye olanak tanıyor. Dizi indekslerinin açıkça tutulmadığı bu varyantta, aralık toplamı hesaplama, toplu güncelleme ve aralık ters çevirme gibi işlemler O(log N) karmaşıklığında tamamlanıyor. Gecikmeli yayılım teknikleri sayesinde karmaşık aralık modifikasyonları tutarlı biçimde yönetiliyor.
Bu özet yapay zekâ ile hazırlanmıştır; ayrıntılar ve doğrulama için orijinal kaynağa başvurun.