Treap

Treap ya da tree heap (ağaç öbeği), arama, ekleme, silme gibi temel işlemler için log(n) zamanı garanti eden dinamik bir ikili arama ağacıdır. İkili arama ağacına sıralı şekilde ekleme yapılırsa binary arama ağacı bağlantılı listeye dönüşür ve arama ancak O(n) zamanda yapılabilir. Bu durumu ortadan kaldırmak için treap her düğümde binary arama ağacında kullanılan asıl değere ek olarak bir de rastgele olusturulmus bir anahtar tutar. Treap veri yapısı hem asıl değere göre veri ağacının kurallarına uyularak hem de rastgele anahtar ata düğümden küçük olacak şekilde kurulur.Treap ilk defa  Cecilia R. Aragon ve Raimund Seidel tarafından 1989 yılında önerilmistir. Treap adı İngilizce ağaç anlamına gelen "tree" ve öbek anlamına gelen "heap"  sözcüklerinin birleştirilmesinden oluşmuştur. Treap oluşturulurken ağaç yapısını bozmayacak şekilde işlemler icra edilir ardından treap'in heap yapısını bozmamak adına gerekli düzeltmeler sağa veya sola döndürme (right or left rotate) işlemleri ile yapılır.Treap değerlerin rastgele anahtarlara göre sıralı olarak eklenmesi şeklinde de düzeltme işlemleri yapılmadan oluşturulabilir.Bütün değerleri rastgele bir sirayla eklenmis bir ağaçta rastgele secilen bir elemana uzaklik O(log n)'dir. Kok dugumden secilen herhangi bir baska elemanagidilirken su an bulundugumuz elemanin altinda n elaman oldugunu varsayalim. Su anki elamanin bizim aradigimiz elaman olma olasiligi n elaman rastgelebicimde dagildigindan 1/n'dir.Sol alt agac p-1 eleman barindirdigindan ayni mantikla gitmek istegimiz elemanin orada olma olasiligi p-1/n'dir. Ayni sekildesag alt agac n-p dugum barindirdigindan olasilik n-p/n'dir. Bir adimda gelinecek alt agac buyuklugunun beklenen degeri (p-1)·(p-1)/n + (n-p)·(n-p)/n + (1·1/n)olarak ortaya cikar. P'nin butun degerleri 1 ile n arasinda esit olasılıkla dagildigindan her adımda ziyaret edilecek agac buyuklugude ayni sekilde dagilir.(1/n)∑ (p-1)2/n + (n-p)2/n + 1  =  (1/n)((2/3)n2 - n + 4/3) = (2/3)n + O(1/n) seklinde ortaya cikar.Bu ifadeninde gosterdigi gibi, O(log 3/2n) adimda istenilen noktaya ulasilmasi beklenir. Bu sebepten ekleme, silme ya da arama islemlerinin O(log n) zamandaBir x degerini agaca eklemek icin rastgele olacak sekilde bir p anahtar degeri uretilir. Agaca ikili arama yapildiktan sonra uygun dugumde yeni biryaprak dugum olusturulur.Bu noktadan sonra p degeri dugumun atasindan kucuk olana kadar saga ya da sola dondurme islemi dugum uzerinde uygulanir. Boylece hem agac yapisi hem deBir x degerini agactan silmek icin once ikili arama yapilarak dugumun yeri tespit edilir. Eger dugum bir yaprak dugumse silinir. Eger degilse tek cocugu varsa aralarindadondurme islemi uygulanarak dugum yaprak dugum haline getirilir. Eger birden fazla çocuk varsa p degerine gore uygun olan çocuk secilerek dondurme islemi uygulanir. Bu islemlerBir Treap istenilen bir noktadan iki ayri treap'e bolunmek istendiginde iki farkli durum ortaya cikar. Bolunmenin istendigi deger treapte mevcut degilseo deger en yuksek anahtar degeriyle treap'e eklenerek degerin kok dugum olmasi saglanir. Ardindan dugumun sol cocugu ve sag cocugu iki ayri treap olarak kok dugumden baglantilarikoparilir. Deger Treapin icinde ise degerin bulunmasina mutakip deger uygun dondurme islemleriyle kok dugum yapılır. Kok dugumun sol ya da sag cocugunun kok ile baglantisikoparilarak ayri bir treap olarak kullanilabilir. Bu islem basitce bir ekleme islemi yapmakla ayni zamanda yani O(log n) zamanda tamamlanir.Iki treap birlestirilirken on sart olarak bir treap'teki en buyuk degerin obur treapteki en kucuk degerden kucuk oldugu kabul edilir.Ilk treapteki en buyuk elemandan buyuk diger treapteki en kucuk elemandan kucuk olacak sekilde bir x degeri agaca en kucuk anahtar degeriyle eklenir (sol çocuk ve sag çocuk treap kok dugumleri olacak sekilde). Ekleme isleminden sonrabu dugum yaprak dugum olacagindan kolayca silinir ve elimizde birlesmis bir treap kalir. Bu islemde bolunme islemi gibi ekleme islemi kadar yani O(log n) zamanda tamamlanir.Ikili arama agaclarinda kullanilan lokal bir degiskeni ekleme basarili oldugunda arttirmak ve silme islemi basarili oldugunda azaltmak bolunme ve birlesmeislemleri sonrasi treap icin hatali sonuc verir. Bu yaklasimin yerine her dugumde sag ve sol çocuk sayilari tutulmali ve bu sayilar dondurme islemleri sonunda guncellenmelidir.Bu yontemle hatasiz bir bicimde treapin eleman sayisi bolunme ve birlesme islemleri sonucu O(1) zamanda ogrenilebilir.c++ treap implementasyonu https://web.archive.org/web/20120203153554/http://www.cplusplus.happycodings.com/Data-Structures-and-Algorithm-Analysis-in-C++/code105.html